Souvislost dobrých aproximací s řetězovými zlomky Předpokládejme, že fleK-^Za definuj me celá čísla p„, qn pro n > 0 a an pro n > 1 jako ve větě o dobrých aproximacích. Pro každé n > 1 ještě označme /i _ \q„8-p„\ U" ~ \qn-l9-pn-i\- Rekurentní vztahy z věty zaručují, že pro každé n > 1 platí \qn-id ~ Pn-i\ = an\qn6 - pn\ + \qn+16 - p„+i|, a tedy é?^1 = an + #n+i, odkud A — i p" - an+e„+i ' což spolu s #1 = (#) dává 0 = [0] + = [9] + _L_ = [0] + 1 , = [9] + —± Příklad: spočítejme několik dobrých aproximací čísla a/Í5 Je tedy po = 1, qo = 0, pi = W 15] = 3, qi = 1 a platí i -s/15- f3 _ i i VÍŠ-3 31 = 1, Víš -3 15- 9 - 1 1 6 ' 6 6(^+3) _ = 6 + ( 7Í5- 3), 32 = 6, Víš -3 15 -9 Os1 = or 33 = = 31 = 1, 34 = 32 = 6, atd. Posloupnost an je periodická. Výpočet čísel p„, q nje výhodné uspořádat do tabulky: n 0 1 2 3 4 5 6 7 8 9 10 Pn i 3 4 27 31 213 244 1677 1921 13203 15124 qn 0 1 1 7 8 55 63 433 496 3409 3905 1 6 1 6 1 6 1 6 1 6 Protože 3i = 1, dostáváme dobré aproximace čísla \/l5 až pro n > 2, jsou to čísla 27 31 213 244 1677 1921 13203 15124 T' ~8~' 1F' "63"' ^33~' ^96~' 3409 ' 3905 ' "' Další moderní metody hledání netriviálního dělitele Nej účinnější metody: Lenstrova metoda eliptických křivek, ► metoda kvadratického síta, ► metoda síta v číselném tělese. Základní myšlenka kvadratického síta i síta v číselném tělese je stejná jako základní myšlenka metody řetězových zlomků, která je historicky první metodou subexponenciálního času a byla na konci 60-tých let a v 70-tých letech hlavní používanou metodou. Nechť N je (velké) složené přirozené číslo, které není dělitelné žádnými „malými" prvočísly (tj. prvočísly < B) a které není mocninou prvočísla. Hledáme netriviálního dělitele čísla N. Budeme hledat x, y G Z, aby platilo x2 = y2 (mod N) a přitom x ^ ±y (mod N). Protože x2 — y2 = (x — y)(x + y), je jasné, že pak největší společný dělitel (x + y, N) bude netriviální dělitel čísla N. Jak hledat x, y G Z, x2 e y2 (mod N), x ^ ±y (mod N) Hledáme kongruence tvaru x2 = {_irokp^kp^ . . . pe„k (mod ^ kde p,-jsou „malá" prvočísla a G {0,1}. Nalezneme-li dostatečně mnoho takových kongruencí (tj. alespoň n > m + 2), můžeme Gaussovou eliminací nad F2 v m + 1-rozměrném prostoru F™+1 najít lineární závislost mezi n vektory (eo/c, ei^,..., em^), (ztotožňujeme {0,1} s F2), tj. najít ei,... ,en G F2, ne všechna nulová, pro která je Y2k=i ek(eok, eik, ■ ■ ■ > emk) nulový vektor. Budeme-li nyní ei,... ,en považovat za celá čísla, pak pro každé / G {0,1,..., m} je číslo v, = \ J2k=i £k^ik £ Z, protože Ylk=i £keik 'ez' v jádře homomorfismu okruhů Z —> ¥2-Pak pro x = nLi 4"< Y = P1P2 ■ ■ ■ Pm> Platí n n x2=n xi£k=n {{-^eokPiikp? ■ ■ ■ pemmkYk=y2 (mod n), k=l k=l což nám dá netriviálního dělitele čísla n, pokud x ^ y (mod A/). Jak hledat x, y G Z, x2 e y2 (mod N), x ^ ±y (mod N) V případě, že liché N je dělitelné právě r prvočísly, je pravděpodobnost, že nastane x = ±y (mod A/) za předpokladu, že platí x2 = y2 (mod A/) a (A/, xy) = 1, rovna 21_r. Proto je vhodné volit n o něco větší než m + 2, abychom Gaussovou eliminací našli více závislostí. Množina {pi,...,pm} se nazývá báze faktorizace. Způsoby, jak ji zvolit optimálně a jak hledat potřebné kongruence x2 = (-l^p^p^ • • • p^ (mod N), se u jednotlivých metod liší. Vždy však je mezi exponenty na pravé straně kongruence jen několik jedniček. Matice takové soustavy má tedy v každém řádku jen několik jedniček a zbytek tvoří nuly. Uložit celou tuto obrovskou „řídkou" matici do paměti se nám patrně nepodaří. Proto je třeba Gaussovu eliminaci provádět jinak, než u malých matic. Gaussova eliminace „řídké" matice Nemáme uloženou celou matici, ale pro každý řádek máme uloženy jen informace o poloze jedniček v tomto řádku. Při provádění eliminace se rozlišuje mezi „řídkými" a „hustými" sloupci: hodnoty v „hustých" sloupcích se neuchovávají, místo nich se uchovává pro každý řádek informace o tom, jak byl odvozen z původní matice (tj. kterých řádků původní matice je součtem). Eliminace se provádí tak, že hledáme řádek, který má pouze jednu jedničku v „řídkých" sloupcích. Ten pak přičteme ke všem řádkům, které v tomto sloupci mají jedničku. Poté už tento řádek nebudeme potřebovat. V případě, že žádný řádek, který by měl pouze jednu jedničku v „řídkých" sloupcích, neexistuje, vybereme ten, který má jedniček co nejméně. Vybereme v něm jednu jedničku a sloupce, ve kterých jsou ostatní jedničky tohoto řádku, prohlásíme za husté. Skončíme v okamžiku, kdy už nemáme žádný řídký sloupec. Pomocí informací o odvozování řádků nyní sestavíme mnohem menší „hustou" matici, v níž se provede Gaussova eliminace obvyklým způsobem. Metoda řetězových zlomku Potřebujeme hledat kongruence tvaru x2 = {_ir0kp^kpe2k . . . pe„k (mod N^ kde p; jsou pevně zvolená prvočísla a e-^ G {0,1}. Budeme vycházet z toho, že pokud zvolíme do naší báze faktorizace všechna prvočísla pi,... ,pm menší než nějaká hranice a najdeme-li kongruenci x2 = t (mod N) s „malým" |r|, je reálná šance, že v rozkladu čísla |r| se nevyskytují jiná prvočísla než Pi,... ,pm a tedy že získáme kongruenci požadovaného tvaru. Metoda řetězových zlomků - základní myšlenka Nechť £ je dobrá aproximace čísla v/c/V, kde k je nějaké nepříliš velké přirozené číslo nedělitelné druhou mocninou prvočísla. Pak fkN-Z Označme t = p2 — kNq2. Pak p2 = t (mod N). Nalezněme odhad pro |r|. Pak < V? p < Přičtením p, umocněním a odečtením p2 dostaneme .2p,J_<_ř<2pj_ q + q2 < f < q + q2 , odkud vzhledem k V/č/V > 2 —K plyne q q2 v y Číslo |t| tedy opravdu není „velké" a šance na získání užitečné kongruence hledaného tvaru je. Metoda řetězových zlomků - postup Metoda řetězových zlomků tedy dává následující algoritmus: postupně za k volíme přirozená čísla nedělitelná druhou mocninou prvočísla a pro každé takové k počítáme jistý počet dobrých aproximací £. Pro každou dobrou aproximaci zkoušíme rozložit číslo |r| = |p2 — kNq2\ pomocí prvočísel z báze faktorizace. Jestliže se to podaří, získáme kongruenci požadovaného tvaru. Pokud |r| není možné rozložit pomocí prvočísel z báze faktorizace, avšak platí \ t\ = F • U, kde F se pomocí prvočísel z báze faktorizace rozkládá a U je (asi) prvočíslo podle testu Millera a Rabina, je vhodné uložit i trojici (p, ŕ, U). Získáme-li totiž později ještě jinou trojici (p', ť, U) se stejným U, pak z p2 = t (mod N) a (p')2 = ť (mod N) získáme kongruenci požadovaného tvaru x2 = j- (mod A/), kde x je řešení kongruence Ux = pp' (mod N). Lepší metoda: metoda kvadratického síta Jiným způsobem budeme opět hledat kongruence tvaru x2 = (_l)^pi^p2^ . . . pejk (mod N^ kde p; jsou pevně zvolená prvočísla a e-^ G {0,1}. Označme d = [VŇ] a uvažme kvadratický polynom Q(x) = (x + d)2 - N. Je jasné, že Q(a) = (a + d)2 (mod N) a že |(?(a)| nebude „velké" pro celá čísla a s „malou" absolutní hodnotou. Ačkoli je to jednodušší metoda generování „malých" kvadrátů modulo N než metoda řetězových zlomků, zatím není příliš zajímavá. Rozhodující důvod, proč je tato metoda rychlejší než metoda řetězových zlomků, je tento: není nutné rozkládat „malé" kvadráty modulo N. Vzhledem k tomu, že většinu z nich rozložit nad zvolenou bází faktorizace nelze, znamená toto marné rozkládání plýtvání časem. Metoda kvadratického síta - postup prosívání Předpokládejme, že pro nějaké n G N víme, že n | Q(a). Pak ovšem pro každé k G Z platí n | Q(a + /cn). Hledat takové a znamená řešit kongruenci x2 = N (mod n) a vzít a = x — d. Přitom řešení této kongruence pro malé n není tak obtížné (pro prvočíslo n existuje Shanksův algoritmus časové náročnosti 0(ln4n)). Jak budeme čísla prosívat: pro každé celé číslo a z velmi dlouhého intervalu uložíme do vektoru indexovaného a přibližnou hodnotu log2|(?(a)| (stačí \ plus řád první jedničky binárního zápisu, pak je chyba menší než ^). Pak pro všechny mocniny prvočísel pk < B pro zvolené B odečteme log2p od všech prvků v našem vektoru, jejichž index a je kongruentní modulo pk s předem vypočteným řešením kongruence Q(a) = 0 (mod pk), tj. (a + d)2 = N (mod pk). Protože předpokládáme, že p \ N, má pro lichá p tato kongruence dvě řešení, je-li N kvadratický zbytek modulo p, a žádné, jestliže je N kvadratický nezbytek modulo p - do báze faktorizace tedy dáváme kromě 2 jen ta prvočísla, pro která je N kvadratický zbytek. Metoda kvadratického síta - vyhodnocení prosívání Po ukončení prosívání zjistíme, pro která a není Q(a) dělitelné mocninou prvočísla větší než B. Pro tato a je totiž prvek ve vektoru indexovaný a malý (kdyby logaritmy byly přesné, byla by to nula). V opačném případě zde musí být číslo větší než log2 B (odhlédneme-li od nepřesnosti logaritmů). Odhadněme potřebnou přesnost e výpočtu log2p. Označme k největší číslo ve vektoru před započetím prosívání. Pak každé číslo |(?(a)| má nejvýše k činitelů. Je-li Q(a) rozložitelné pomocí naší báze faktorizace, je po provedení odčítání logaritmů ve vektoru s indexem a číslo menší než ^ + ks. Naproti tomu pro nerozložitelné Q(a) dostaneme číslo větší než (log2 B) - \ - (k + \ - log2 B)e. Stačí tedy e < j^P^- Pak pro všechna a, pro které jsme dostali ve vektoru číslo menší než ^ + ks, spočítáme znovu Q(a) a rozložíme, čímž získáme kongruenci požadovaného tvaru. Máme-li dost místa v paměti, ukládáme v průběhu prosívání u každé položky a několik největších prvočísel, jejichž logaritmy odčítáme, což pak urychlí rozkládání. Metoda kvadratického síta - možnosti vylepšení Podobně jako u metody řetězových zlomků i v tomto případě můžeme hledat kongruence x2 = F ■ U (mod N), kde F se pomocí prvočísel z báze faktorizace rozkládá a U je „nepříliš velké" číslo. V tom případě rozkládáme Q(a) pro všechna a, pro které po prosívání zůstalo ve vektoru číslo menší než nějaká předem daná mez a nerozložitelný faktor spolu s a uchováváme pro případ, že by se týž faktor objevil ještě jednou. Nevýhodou je, že na dlouhém intervalu prosívání hodnoty polynomu Q(x) značně rostou a s tím i klesají naše šance na úspěšné rozložení. Mohli bychom proto vzít ještě další polynom a prosívat i jeho hodnoty, například Q(x) = (x + [VIŇ])2 — £N pro nějaké přirozené číslo í nedělitelné druhou mocninou prvočísla. V tom případě bychom však museli doplnit naši bázi faktorizace: máme v ní pouze ta prvočísla p, pro která je N kvadratický zbytek modulo p, kdežto nyní potřebujeme ta, pro která je IN kvadratický zbytek modulo p. Ovšem zvětšení báze faktorizace znamená potřebu více kongruenci a také Gaussovu eliminaci větší matice.