Algorisme ro de Pollard

(S'ha redirigit des de: Algorisme rho 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 modifica

Sigui

 

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

 

Definida com:

 

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 xb tals que

 

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

La cerca de xa i xb é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(|xa-xb|, 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 modifica

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 modifica

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

 

Per a certs f, l'algorisme no trobarà cap factor. Si Mcd(|xaxb|, n) = n, l'algorisme fracassarà, perquè xa = xb 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 modifica

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

i xi x2i pgcd(|xix2i|, 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 modifica

L'algorisme pot ser utilitzat per a cerques de col·lisions, en particular en les funcions de hash. Sigui   l'empremta del missatge  . Es busca un segon missatge  , diferent de  , tal que  . 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   la talla mida del qual és igual a l'empremta. S'itera la funció de hash calculant  ,  ,  ,   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  . Es reprèn el missatge inicial   i s'efectuen llavors iteracions en paral·lel sobre les dues empremtes:

  •  ,  ,  , etc.
  •  ,  ,  , 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 264 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 modifica