Pollard rho algoritmusa

A moduláris aritmetika , a Rho Pollard algoritmus egy algoritmus a törzstényezős bomlásterméke konkrét amely csak akkor hatásos, faktoring egész kis tényezők. John M. Pollard tervezte 1975-ben.

A kriptológiában használják . A rho algoritmus legfigyelemreméltóbb sikere a nyolcadik Fermat-szám Pollard és Brent faktorizálása volt . Az algoritmus módosított változatát használták, amely korábban ismeretlen prímtényezőt talált. A teljes faktorizációja F 8 került, összesen, 2 órán át egy Univac 1100-1142 .

Algoritmus

Matematikai elv

Legyen összetett egész szám, ahol van egy ismeretlen nem triviális tényező, amelyet az algoritmus megpróbál meghatározni. Magunkba helyezzük magunkat ; más szóval benne vagyunk, és a számításokat modulo módon hajtjuk végre . ${\ displaystyle n = pq}$ $o$ ${\ displaystyle S = \ mathbb {Z} / n \ mathbb {Z}}$ ${\ displaystyle \ {0, \ pontok, n-1 \}}$ $nem$

Javítsunk ki például egy függvényt . A függvénynek gyorsan kiszámíthatónak és ál-véletlenszerűnek kell lennie . Ezután meghatározzák a szekvenciát által , ahol a véletlenszerűen kiválasztott. Mivel a sorozat véges számú értéket vesz fel, végül megismétli önmagát. Ez az oka az algoritmus nevének: a ciklikus szekvencia grafikus ábrázolása úgy néz ki, mint a görög ρ betű, lásd a szemközti ábrát. ${\ displaystyle f: S \ - S}$ ${\ displaystyle f: x \ mapsto x ^ {2} +1}$ $(x_ {n})$ ${\ displaystyle x_ {n + 1} = f (x_ {n})}$ ${\ displaystyle x_ {0} \ in S}$ $(x_ {n})$

Vizsgáljuk meg most az értékek sorrendjét . Mint ismeretlen, ez a szekvencia nem számítható ki kifejezetten. Tudjuk, hogy megismétli önmagát is. A születésnapi paradoxon miatt ismétlődési ideje gyakran szigorúan kisebb, mint a folytatásé . Ha igen, két mutató van , például mais . ${\ displaystyle x_ {n} {\ text {mod}} p}$ $o$ $x_ {n}$ $i <j$ ${\ displaystyle x_ {i} \ equiv x_ {j} {\ pmod {p}}}$ ${\ displaystyle x_ {i} \ not \ equiv x_ {j} {\ pmod {n}}}$

Tehát oszd meg, de . Vagyis nem triviális tényező . $o$ ${\ displaystyle \ mathrm {pgcd} (x_ {j} -x_ {i}, n)}$ ${\ displaystyle \ mathrm {pgcd} (x_ {j} -x_ {i}, n) \ neq n}$ ${\ displaystyle \ mathrm {pgcd} (x_ {j} -x_ {i}, n)}$ $nem$

Annak megállapításához, az indexek és használjuk Floyd algoritmusa , hogy megtalálja a ciklus . Ezután elegendő (for ) számolni, amíg nem triviális tényezőt nem kapunk , vagy meg nem kapjuk a faktort . Valójában ez azt jelzi, hogy ezért megvan , hogy befejeztük a . Ezután kezdhetjük újra a vagy a függvény értékének megváltoztatásával . $én$ $j$ ${\ displaystyle \ mathrm {pgcd} (x_ {2k} -x_ {k}, n)}$ $k \ geq 1$ $nem$ $nem$ ${\ displaystyle x_ {k} = x_ {2k}}$ $(x_ {k})$ $x_ {0}$ $g$

Algoritmus

Itt adjuk meg az álkódot, mint a.

entrée : un entier n composé, qui n'est pas une puissance d'un nombre premier sortie : un facteur non trivial de n, ou alors une erreur Pollard-Rho(n) (a, b) := (2, 2) # dans , ils prennent x0 = 2 répéter (a, b) = ( f(a), f(f(b)) ) d := pgcd(a-b, n) si 1 < d < n retourner d si d = n erreur

Példa

Legyen n = 8 051 és f (x) = x 2 + 1 mod 8 051. Vesszük x 0 = 2.

én	x i	x 2 i	gcd ( x i - x 2 i , 8051)
1	5.	26.	1
2	26.	7474	1
3	677	871	97

A 97 nem triviális 8051 tényező. A c egyéb értékei 97 helyett a 83 tényezőt adhatják.

Beszélgetések

Teljesítmény

Az algoritmus nagyon gyors a kis tényezőkkel rendelkező számok esetén. Például egy 733 MHz-es munkaállomáson az rho algoritmus optimalizálás nélküli megvalósítása fél másodperc alatt megtalálja a hatodik Fermat-szám 274 177-es tényezőjét . A hatodik Fermat- szám 18 446 744 073 709 552 000 (20 tizedesjegy ). Ugyanakkor egy azonos méretű félprím szám esetén ugyanaz a munkaállomás körülbelül 9 másodpercet vesz igénybe, hogy 10 023 859 281 455 310 000 tényezőt találjon (két tízjegyű prím szorzata).

F választása

Mert f , úgy döntünk, egy egész együtthatós polinom. A leggyakoribbak a következők:

f (x) = x ^ {2} + c, \ quad c \ notin \ {0, -2 \}.

Néhány f esetén az algoritmus nem talál tényezőt. Ha pgcd (| x a - x b |, n ) = n , akkor az algoritmus meghiúsul, mert x a = x b , ami azt jelenti, hogy a szekvenciát hurkolták, és addig folytatódik, amíg az előző munkát megismételik. A c vagy f megváltoztatásával növelhetjük a siker esélyét. Ez a kudarchelyzet minden prímszámnál előfordulhat, egyes összetett számoknál is előfordulhat.

Változat

Az algoritmus ütközési keresésekhez használható , különösen hash függvényekben . Vagy a lenyomata az üzenet keresünk egy második üzenetet eltér , mint Hála a paradoxon születésnapra és segítségével Pollard algoritmus, akkor ezt nem fogyaszt sok memóriát. A születésnapi paradoxon naiv megvalósításához az összes előállított ujjlenyomat tárolása és összehasonlítása szükséges. A Rho algoritmus legyőzi ezt a korlátot. $H (M_ {1})$ $M_ {1}.$ $M_ {2},$ $M_ {1},$ $H (M_ {1}) = H (M_ {2}).$

Ennek elérése érdekében létrehozunk egy véletlenszerű üzenetet, amelynek mérete megegyezik az ujjlenyomattal. Az első számítással iteráljuk a kivonatot és így tovább. A véges állapotok száma miatt ez az iteráció szükségszerűen belép egy olyan ciklusba, amely a fent látható algoritmusokkal detektálható. A ciklus észlelése után meg kell találni a két különálló üzenetet, amelyek ütköznek. A ciklus észlelésekor az ujjlenyomat jelen van. A kezdeti üzenetet újra elkészítjük, majd az iterációkat párhuzamosan hajtjuk végre a két ujjlenyomaton: $x$ $H (x), H (H (x))$ $y.$ $x$

$H (x), H (H (x)), H (H (H (x))),$ stb.
$H (y), H (H (y)), H (H (H (y))),$ stb.

Addig iterálunk, amíg két azonos kimenetet nem kapunk, ami két különálló üzenet ütközésének jele. A gyakorlatban a hash függvény kimenetének csak egy részét veszik figyelembe a túl hosszú számítási idők elkerülése érdekében. Az elosztott számítástechnika alternatíváját alkalmazták az MD5CRK (in) projektben, amelynek célja az MD5 titkosítási hash függvény teljes ütközésének (128 bites komplexitás 2 64 művelet) megtalálása . Az egyetlen PC-n futó jó megvalósítással napokon belül megtalálhatók az SHA-1 egymást követő 69 bites ütközései (az SHA-1 160 bites lábnyommal rendelkezik).

Megjegyzések és hivatkozások

(fr) Ez a cikk részben vagy egészben az angol Wikipedia " Pollard's rho algoritmusa " című cikkéből származik ( lásd a szerzők felsorolását ) .

(en) JM Pollard , " A monte carlo módszer a faktorizáláshoz " , BIT Numerical Mathematics , vol. 15, n o 3,1 st szeptember 1975, P. 331–334 ( ISSN 1572-9125 , DOI 10.1007 / BF01933667 , online olvasás , hozzáférés : 2019. október 11. )
Az alkalmazott kriptográfia kézikönyve, szerző : Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, p. 125 , leírja ezt az algoritmust és másokat

Lásd is