Algorisme ro de Pollard

En teoria de nombres i en aritmètica modular, l'algorisme ro de Pollard és un algorisme de descomposició en producte de factors primers específic que només és efectiu per factoritzar els enters amb factors petits. Va ser concebut per John M. Pollard el 1975.

Es fa servir en criptografia.

Definició formal

Sigui

f:S\to S

una funció aleatòria, i S un conjunt finit de cardinal n, on n és l'enter a factoritzar. Es pren la successió:

x_{0},x_{1},\ldots

Definida com:

x_{i+1}=f(x_{i}){\hbox{ mod }}n,\,x_{0}=2.

Aquí, (mod) designa la congruència sobre els enters. Com que s és un conjunt finit, la successió tard o d'hora ha de repetir-se. Aquesta és la raó del nom de l'algorisme: la successió cíclica s'assembla a la lletra grega ro. L'objectiu és de trobar _a i x_b tals que

x_{a}\equiv x_{b}{\pmod {p}}

on p. és un factor no trivial de n. Això voldrà dir que el Mcd(x_a − x_b, p) = p. Com que no es coneix p, s'efectuen aquestes comparacions i aquests càlculs mòdul n.

La cerca de x_a i x_b és una modificació de l'algorisme de cerca de cicles de Floyd. S'executem dues successions definides per la funció aleatòria f, però una s'executa dues vegades més de pressa que l'altre. En cada etapa, es calcula Mcd(|x_a-x_b|, n) per verificar si es té un factor. Si el Mcd és més gran que 1 i més petit que n, llavors se n'ha trobat un.

Prestacions

L'algorisme és molt ràpid per als nombres amb factors petits. Per exemple, sobre una estació de treball a 733 MHz, una implementació de l'algorisme ro, sense cap optimització, troba el factor 274177 del sisè nombre de Fermat en un mig-segon. El sisè nombre de Fermat és 18446744073709551617 (20 xifres (decimals). No obstant això, per a un nombre semi-primer d'igual mida, la mateixa estació de treball necessita aproximadament 9 segons per trobar un factor de 10023859281455311421 (el producte de 2 nombres primers a 10 xifres)

Tria de f

Per f, es tria un polinomi amb coeficients enters. Els més comuns són de la forma:

f(x)=x^{2}+c{\hbox{ mod }}n,\,c\neq 0,-2.

Per a certs f, l'algorisme no trobarà cap factor. Si Mcd(|x_a − x_b|, n) = n, l'algorisme fracassarà, perquè x_a = x_b el que vol dir que la successió té un bucle i continuarà repetint el treball precedent. Canviant c o f, es pot augmentar l'oportunitat d'èxit. Aquesta situació de fracàs es pot donar per a tots els nombres primers i també per a certs nombres compostos.

Exemple

Heus aquí un exemple. Sigui n = 8 051 i f(x) = x² + 1 mod 8 051.

i	x_i	x_2i	pgcd(\|x_i − x_2i\|, 8051)
1	5	26	1
2	26	7474	1
3	677	871	97

97 és un factor no trivial de 8 051. Altres valors de c poden donar el factor 83 en comptes del 97.

L'èxit més destacable de l'algorisme ro ha estat la factorització del vuitè nombre de Fermat per Pollard i Richard Brent. Varen fer servir una versió modificada de l'algorisme, que ha trobat un factorr primer desconegut anteriorment. La factorització completa de F₈ pren, en total, 2 hores sobre un Univac 1100/42.

Variant

L'algorisme pot ser utilitzat per a cerques de col·lisions, en particular en les funcions de hash. Sigui $H(M_{1})~$ l'empremta del missatge $M_{1}~$ . Es busca un segon missatge $M_{2}~$ , diferent de $M_{1}~$ , tal que $H(M_{1})=H(M_{2})~$ . Gràcies a la paradoxa dels aniversaris i amb l'ajuda de l'algorisme de Pollard, es pot fer això sense consumir una quantitat enorme de memòria. Una implementació ingènua de la paradoxa dels aniversaris requeriria emmagatzemar totes les empremtes generades i comparar-les. L'algorisme ro permet alliberar-se d'aquesta restricció.

Per aconseguir-ho, es crea un missatge aleatori $x~$ la talla mida del qual és igual a l'empremta. S'itera la funció de hash calculant $H(x)~$ , $H(H(x))~$ , $H(x)~$ , $H(H(x))~$ i així successivament. Sent finit el nombre d'estats, aquesta iteració entrarà per força en un cicle que es pot detectar amb els algorismes vistos damunt. Una vegada el cicle detectat, cal trobar els dos missatges diferents que xoquen. Quan s'ha detectat el cicle, s'està en presència de l'empremta $y~$ . Es reprèn el missatge inicial $x~$ i s'efectuen llavors iteracions en paral·lel sobre les dues empremtes:

$H(x)~$ , $H(H(x))~$ , $H(H(H(x)))~$ , etc.
$H(y)~$ , $H(H(y))~$ , $H(H(H(y)))~$ , etc.

S'itera fins a obtenir dues sortides idèntiques, signe d'una col·lisió entre dos missatges diferents. A la pràctica, no es considera més que una part de la sortida de la funció de hash per evitar temps de càlcul massa longituds. Una variant per al càlcul distribuït ha estat utilitzada en el marc del projecte MD5Crk que buscava trobar una col·lisió completa (128 bits, complexitat de 2⁶⁴ operacions) sobre la funció de hash criptogràfic MD5. Amb una bona implementació executada sobre un sol PC, és possible trobar col·lisions sobre 69 bits consecutius de SHA-1 en alguns dies (SHA-1 té una empremta de 160 bits).

Enllaços externs

(anglès) Page de John Pollard Arxivat 2008-04-27 a Wayback Machine.