6. előadás Faktorizációs technikák közepes méretű osztókra

Számítástudomány

Széchenyi István Egyetem

6. előadás Faktorizációs technikák „közepes méretű” osztókra

Dr. Kallós Gábor

2016–2017 11



Tartalom Fermat algoritmusa A Pollard-ró algoritmus Pollard (p – 1) algoritmusa Feladatok, megjegyzések Irodalom

2



Fermat algoritmusa Eml.: Próbaosztásos algoritmus (teljes felbontás) 14-18 jegyű számokig használható jól (gyors gépen esetleg valamivel tovább) Efelett reménytelenül lelassul

Ötlet: Túl sokat akarunk egyben! (Szerényebb cél is elég lenne) Döntés: a szám nem prím (biztosan tudjuk) Bontsuk szét két valódi osztója szorzatára! (És ezekkel dolgozunk majd tovább)

Fermat algoritmusa Feltételezés: n a négyzetgyökéhez viszonylag közeli két faktorra bomlik Az algoritmus a négyzetgyök közeléből indulva keres valódi osztót

Alapötlet: Ha n = x2 – y2, akkor n = (x – y) ⋅ (x + y), és a felbontásunk sikeres Az is igaz, hogy ha n ptlan, akkor n minden felbontása előáll ily módon Legyen ugyanis n = a ⋅ b, ahol n, a és b ptlanok. Legyen x = (a + b)/2, y = (a – b)/2. Ekkor x2 – y2 = (a2 + 2⋅a⋅b + b2 – a2 + 2⋅a⋅b – b2)/4 = a ⋅ b = n. Az algoritmus működése: Bekérünk egy ptlan n-et, és keresünk olyan x-et, y-t, amire n = x2 – y2. Kezdetben legyen x =  n, y pedig 0, és növeljük y-t addig, amíg x2 – y2 ≤ n lesz. Ha =, akkor kész vagyunk, ha <, akkor x-et növeljük, és iterálunk. Addig folytatjuk ezt, amíg sikeresek nem leszünk. Mostani megvalósítás: u = 2x + 1 és v = 2y + 1-et választunk, x és y eggyel való növelése u és v 2-vel való növelését jelenti 3



Fermat algoritmusa Feladat: Nézzük meg az algoritmus működését n = 21-re! Lépések: gy := 5, u := 11, … Csináljuk meg ugyanezt 51 = 3 ⋅ 17-re!

Az algoritmus előnyei Nincs benne osztási és szorzási művelet, extrém gyorsan végrehajtható egy ciklus Ha valóban a szám négyzetgyöke körül van faktor, akkor igen hatékony

Hátrányok Kedvezőtlen esetekben nagyon sok lépés kellhet Pl. 1 783 647 329 = 84 449 ⋅ 21 121 felbontásához 10 551 x_loop és 31 664 y_loop

Ha n prím, akkor ez az algoritmus nagyon rossz választás…

Javítási lehetőség: Ha x2 – n nem teljes négyzet, akkor úgysem találhatunk jó y-t! (x eldobható) Ez az algo. nagyon sikeres modern módszerek alapja Kraitchik ötlete (20. sz.): Keressünk „véletlen” x és y számokat, amelyekre x2 ≡ y2 (mod n). Ekkor n | (x2 – y2) és lnko(n, x – y) jó eséllyel valódi osztó. Hogyan keressük őket? (Lánctört algoritmus – Morrison-Brillhart módszer, kvadratikus szita)

4



A Pollard-ró algoritmus Cél: Általánosan használható jó algoritmus, amely határozottan túllép a próbaosztásos algoritmus nagyságrendjén, és talál faktort (107–1015 környékén) (A lánctört algoritmus és a kvadratikus szita inkább még nagyobb faktorok leválasztására jó)

Alapötlet: Legyen n összetett, és d egy ismeretlen valódi osztója. Legyen f(x) egyszerű irreducibilis polinom. (A gyakorlatban pl. x2 + 1 jól használható.) Induljunk egy x0 egésztől, és készítsük el az xi = f (xi – 1) mod n sorozatot. [Pl. x0 = 2, f(x) = x2 + 1, n = 1133-ra: x0 = 2, x1 = 5, x2 = 26, x3 = 677, x4 = 598, x5 = 710, stb.] Legyen yi = xi mod d. [Esetünkben d = 11-gyel: y0 = 2, y1 = 5, y2 = 4, y3 = 6, y4 = 4, y5 = 6, y6 = 4, stb.] Mivel xi ≡ f (xi – 1) (mod n), ezért yi ≡ f (yi – 1) (mod d). Csak véges sok mod d ekv.osztály van (d darab), ezért előbb-utóbb yi = yj lesz, i ≠ j-re. Ezután már ciklizálni fogunk a továbbiakban (yi + t = yj + t lesz, ∀ poz. t-re). (Az yi-k/xi-k sorozatának rajzáról kapta a nevét az algoritmus.) Ha yi = yj, akkor xi ≡ xj (mod d), azaz d | (xi – xj). Szinte biztosan xi ≠ xj, és ekkor lnko(n, xi – xj) az n egy valódi osztója. 5



A Pollard-ró algoritmus Probléma: Mivel d-t nem ismerjük, ezért az yi-ket (és yi = yj-ket) nem tudjuk meghatározni De (eml.): yi + t = yj + t végtelen sok esetben teljesül, így a végtelen sok párból kellene egyet megtalálni… Ha a ciklus c hosszú, akkor a „farok” elhagyása után már bármelyik (i, j) pár jó, amire c | (j – i)

A megoldás így az, hogy rengeteg (i, j) párt megnézünk (akár: egy jó stratégiával), és mindegyikre kiszámítjuk lnko(n, xi – xj)-t Javaslat (R. Brent, 1980): Ne kelljen tárolni nagyon sok xi értéket, vizsgáljuk csak a következő különbségeket: x1 – x3, x3 – x6, x3 – x7, x7 – x12, x7 – x12, x7 – x13, x7 – x15, … általánosan: x2n −1 − x j , és 2 n +1 − 2n −1 ≤ j ≤ 2 n+1 − 1 Fontos: A koordináták közti különbség mindig csak eggyel nő A kis indexektől haladunk a nagyok felé (előbb-utóbb elhagyjuk a „farkot”)

Mivel tipikusan nagyon sok lnko számítást kell elvégezni (akár: tízezreket), ezért célszerű több, pl. 10 egymás utáni (xi – xj) (mod n) szorzatát venni, és erre végezni az lnko számítást Ha n | szorzat, akkor általában egy tényező osztója, ilyenkor válasszunk másik alappolinomot 6



A Pollard-ró algoritmus Az algoritmus nem talál biztosan megoldást, ill. lehet, hogy nagyonnagyon sokára talál csak osztót! Célszerűen: leállítási/kilépési lehetőség biztosítása (pl. 10000 vagy 100000 ciklusonként)

Prímszámokra tilos futtatni! Feladat: Elemzés (próbafuttatás) kis n-re, pl. n = 253-ra (= 11⋅23)

7



A Pollard-ró algoritmus Az algoritmus működése n = 253-ra (= 11⋅23) c=1 x1 = 2, x2 = 5 range = 1 # compute diff # ciklus 1-től 1-ig x2 = 5 ⋅ 5 + 1 = 26 # x3 pr = (2 – 26) mod 253 = 229 lnko(253, 229) → 1 # reset x1 = 26 range = 2 # ciklus 1-től 2-ig x2 = 26 ⋅ 26 + 1 mod 253 = 171 # x4 x2 = 171 ⋅ 171 + 1 mod 253 = 147 # x5 # compute diff # ciklus 1-től 2-ig x2 = 147 ⋅ 147 + 1 mod 253 = 105 # x6 pr = (26 – 105) mod 253 = 174 lnko(253, 174) → 1 x2 = 105 ⋅ 105 + 1 mod 253 = 147 # x7 pr = (26 – 147) mod 253 = 132 lnko(253, 132) → 11 (kész a felbontás) *Feladat (Maple): Keressünk olyan összetett számokat, amelyekre a 'pollard' opció gyorsabb felbontást ad, mint az alapértelmezett módszer!

8



A Pollard-ró algoritmus Hatékonysági elemzés (összehasonlítás a próbaosztásos módszerrel) Kis prímosztókra a Pollard-ró algoritmus kevéssé hatékony Kisebb egészekre (öt-hétjegyű számok) nem érdemes még bevetni

*Vizsgálat: Hány iteráció (m(p)) alatt találja meg a Pollard-ró algoritmus a következő prímosztókat (p)? (legnagyobb hatjegyű prímek)

Eredmény (Knuth): m(p) várható értéke kb. 2 p , és m(p) soha nem lépi túl a 12 p -t, ha p < 106 *A próbaosztásos algoritmus futási ideje arányos max( pt −1 , pt )-vel, ahol pt az n szám

legnagyobb prímosztója

Ha egy prímtesztet is bevetünk a felbontás előtt, akkor pt–1-gyel arányos

*A Pollard-ró algoritmus futási ideje arányos pt −1 -gyel, végeredményben a lépésszám általában jóval n1/4 alatt van Konklúzió: A Pollard-ró algoritmus majdnem minden 12 jegyű számot kevesebb mint 2000 iterációval tényezőkre bont, ezzel szemben a próbaosztásos algoritmusnak ehhez mintegy 100.000 osztást kell elvégezni 9



Pollard (p – 1) algoritmusa Alapötlet: Fermat kis tételét használjuk, miszerint: 2p – 1 ≡ 1 (mod p). Tegyük fel, hogy a felbontandó n számnak van egy olyan tulajdonságú p prímfaktora, hogy p – 1 minden prímosztója kicsi, pl. kisebb mint 10000. Konkrétan azzal a megkötéssel dolgozunk, hogy p – 1 | 10000!. Mivel a hatványozás modulo n gyors művelet, ki tudjuk számolni m = 210000! mod n-t meglehetősen gyorsan: 210000! = (…(((21)2)3)4 …)10000 . Mivel p – 1 | 10000!, ezért 2p – 1 ≡ 1 (mod p) miatt m ≡ 1 (mod p) is igaz, azaz p | (m – 1). Nagyon jó esélyünk van arra, hogy n§(m – 1), azaz g = lnko(m – 1, n) az n szám valódi osztója lesz. Nem kell 2-nek lenni az alapnak, választható más c szám is lnko(c, n) = 1-gyel

Mivel nem tudjuk, hogy a 10000-et mennyire kell megközelítenünk ahhoz, hogy megtaláljuk n első (vagy: összes szükséges) prímosztóját, ezért rendszeresen ellenőrizzük lnko(ck! – 1, n)-t. Ha ez 1, akkor folytatjuk; ha ez n, akkor minden osztót „felkaptunk egyszerre”, ezért vagy visszalépés kell, vagy más c alap, vagy más algoritmus. Ha erre 1 < lnko < n, akkor megvan a keresett osztó.

10



Pollard (p – 1) algoritmusa Alkalmazás előtt: Mint a Pollard-ró algoritmusnál, n-ről tudnunk kell már, hogy nem prím, és ellenőriztük, hogy nincs kis prímosztója Ha p – 1-nek csak nagy prímosztói vannak, akkor az algoritmus kudarcot vall!

11



Pollard (p – 1) algoritmusa Feladat: Elemzés (próbafuttatás) kis n-re, pl. n = 253-ra (= 11⋅23) m=2 # ciklus 1-től …-ig m = 21 mod 253 = 2 lnko(1, 253) = 1 m = 22 mod 253 = 4 lnko(3, 253) = 1 m = 8; lnko(7, 253) = 1 További elemzés m = 16; lnko(15, 253) = 1 Kis prímekre az algoritmus „pazarló”, m = 32; lnko(31, 253) = 1 ezeket sokkal magasabb hatványon m = 64; lnko(63, 253) = 1 vesszük figyelembe, mint szükséges Ezt javítva kb. 8-szoros gyorsítás érhető el m = 27 mod 253 = 128 lnko(127, 253) = 1 # a 127 prím Ha p az n legkisebb prímosztója, akkor az algoritmusnak átlagosan p – 1 legnagyobb m = 28 mod 253 = 256 mod 253 = 3 prímosztója db ciklust kell megtennie lnko(2, 253) = 1 (Eml.: n0,63 átlagosan…) m = 29 mod 253 = 6 Ezért max = 10000-rel 2 millió körülig lnko(5, 253) = 1 általában minden osztót megtalálunk m = 210 mod 253 = 12 Néha jóval nagyobbakat is lnko(11, 253) = 11 Ez az algoritmus az oka, hogy az RSA-nál kellett a megkötés p – 1-re és q – 1-re 12



Feladatok, megjegyzések Megjegyzés az algoritmusokhoz A korábbi algoritmusok (Fermat eljárása is) teljesen pontosan előre leírható, determinisztikus működésűek A most megismertek (Pollard eljárásai) véletlenszerűséget visznek a rendszerbe, nem lehetünk biztosak benne, hogy adott idő alatt valóban találunk osztót (valószínűségi algoritmusok) Az első (ókori) algoritmusok még alkalmasak voltak prímtesztre és faktorizációra is, a továbbiakban a két feladat teljesen szétválik Feladatok Bontsuk fel (beépített v. saját) Pollard-ró és Pollard (p – 1) algoritmussal a következő számokat: 785.994.771.137 950.161.333.249 2.506.741.191.739 227.793.195.071.137 Hasonlítsuk össze a futási időket! Válasszunk 100 db egymást követő számot 500 és 2000 között, ezek lesznek az n-ek. Minden n-re készítsük el az y0 = 2, y1 = (22 + 1) mod n, …, (y2i+1 + 1) mod n sorozatot, egészen addig, amíg az értékek nem ismétlődnek. Milyen összefüggést tapasztalunk a ciklusok hossza és n négyzetgyöke között? Határozzuk meg, hogy kb. hány jegye van 10000!-nak! Melyik 2-nek az a legnagyobb hatványa, ami osztja a 10000! számot? 13



Ajánlott irodalom David M. Bressoud: Factorization and Primality Testing, Springer, New York, 1989 Joachim Gathen, Jürgen Gerhard: Modern Computer Algebra (3rd ed.), Cambridge Univ. Press, 2013 Donald E. Knuth: A számítógép-programozás művészete 2. (2. kiadás), Műszaki Könyvkiadó, Budapest, 1994 Katona Gyula, Recski András, Szabó Csaba: A számítástudomány alapjai, Typotex Kiadó, Budapest, 2003 Maple User Manual, Maplesoft, 2013 Matlab Symbolic Math Toolbox User’s Guide, MathWorks, 2013 Iványi Antal (szerk.): Informatikai algoritmusok 1., ELTE Eötvös Kiadó, Budapest, 2004

14

6. előadás Faktorizációs technikák közepes méretű osztókra

Recommend Documents