Algorisme rho de Pollard

De Viquipèdia
Dreceres ràpides: navegació, cerca

En teoria de nombres i en aritmètica modular, l'algorisme Rho 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 | modifica el codi]

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. L'objectiu és de trobar a i xb tals que

x_a \equiv x_b \pmod{p}

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 | modifica el codi]

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 rho, 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 | modifica el codi]

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\neq0,-2.

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 | modifica el codi]

Heus aquí un exemple. Sigui n = 8 051 i f(x) = x2 + 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 rho 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 F8 pren, en total, 2 hores sobre un Univac 1100/42.

Variant[modifica | modifica el codi]

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 Rho 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 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 | modifica el codi]