Rozklad přirozeného čísla na součin prvočísel
Připomeňme, že hledáme co nej rychlejší algoritmus, který dané přirozené číslo N rozloží na součin prvočísel. Rozdělme náš problém na tři úkoly:
1. Test na složenost: Pro dané N G N rychle rozhodnout, zda N splňuje nějakou podmínku, která je splněna každým prvočíslem, a tedy rozhodnout, zda je to určitě číslo složené anebo zda je to asi prvočíslo.
2. Test na prvočíselnost: Je-li N asi prvočíslo, dokázat, že N skutečně prvočíslem je, nebo to vyvrátit.
3. Nalezení dělitele: Je-li N složené, nalézt netriviálního dělitele d čísla N.
Celé rozkládání je pak rekurzivní proces: máme-li dělitele d čísla N, který splňuje 1 < d < N, opakujeme celý postup pro čísla d a ^.
Metoda pokusného dělení
Zkoušíme dělit N postupně všemi prvočísly 2, 3, 5, 7, 11, ... až do jisté hranice. Pokud jsme schopni to provést pro všechna prvočísla p < \//V, provedeme tím všechny tři úkoly současně. V případě, kdy N je natolik velké, že dělení N všemi prvočísly p < \//V by bylo příliš zdlouhavé, můžeme N dělit všemi prvočísly až do jisté hranice, abychom se zbavili malých faktorů (čím je prvočíslo menší, tím větší je pravděpodobnost, že dělí náhodně zvolené přirozené číslo).
Budeme předpokládat, že máme uloženu tabulku prvočísel p[l] = 2, p[2] = 3, p[3] = 5, p[4] =7, ..., p[k]. Po vyčerpání této tabulky budeme pokračovat v dělení N čísly z jistých zbytkových tříd (např. čísly dávajícími zbytek 1 nebo 5 po dělení 6, resp. čísly dávajícími zbytek 1, 7, 11, 13, 17, 19, 23 nebo 29 po dělení 30 apod.). Tím sice některá dělení provedeme zbytečně, ale výsledek bude stále správný (testovat, zda číslo, kterým hodláme dělit, je prvočíslo, nemá smysl).
Zvolme horní hranici B, v níž přestaneme dělit, abychom algoritmem neztratili příliš mnoho času.
Algoritmus (Pokusné dělení). Je dána tabulka prvočísel p[l] = 2, p[2] = 3, p[3] = 5, p[4] =7, ..., p[/c] (kde k > 3), číslo B > p[k], vektor t = [6,4, 2,4, 2,4, 6, 2], číslo j tak, že j = 0 (resp. 1, 2, 3, 4, 5, 6, 7), právě když p[k] = 1 (mod30) (resp. 7, 11, 13, 17, 19, 23, 29). Pro dané N G N algoritmus hledá rozklad čísla N. Jen největší činitel tohoto rozkladu nemusí být prvočíslo, ale v tom případě může být dělitelný jen prvočísly většími než B.
1. [Inicializace] Je-li N < 5, pak vytiskni odpovídající rozklad N a skonči. Jinak polož i i--1, m <— 0.
2. [Další prvočíslo] Polož m <— m + 1. Je-li m > k, polož /<—_/ — 1 a jdi na 5, jinak polož d <— p[m].
3. [Zkus dělit] Současně spočítej r <— N mod d, q -í— [-jj]. Je-li r = 0, vytiskni d jako činitele v hledaném rozkladu a polož N <r- ^ a opakuj krok 3.
4. [Prvočíslo?] Je-li d > q, vytiskni N jako posledního činitele a zprávu, že rozklad je úplný a skonči. Jinak, je-li i < 0, jdi na 2.
5. [Další dělitel] Polož i <- (/' + 1) mod 8, d <- d + ŕ[/]. Je-li
d > B, vytiskni N jako posledního činitele a zprávu, že poslední činitel v rozkladu nemusí být prvočíselný a skonči. Jinak jdi na 3.
Metoda pokusného dělení
Jestliže v kroku 4 nastane d > q, už víme, že N není dělitelné žádným prvočíslem p < d. Navíc
N = qd + r < (q + l)d < (d + a tedy \//V < d + 1. Proto už musí být N prvočíslo.
Pro úplný rozklad N se metoda pokusného dělení hodí jen pro malá N (řekněme N < 108), protože pro větší N existují lepší metody. Každopádně je užitečná pro odstranění malých faktorů.
Vhodnou tabulkou prvočísel by mohla být tabulka prvočísel menších než 500 000, máme-li na ni dost místa v paměti (je to 41538 prvočísel). Vhodnější než uložení vlastních prvočísel může být uložení diferencí mezi nimi nebo dokonce poloviny diferencí (diferenci p[k] — p[k — 1] můžeme uložit do jednoho bytu pro p[k] < 1872 851947, její polovinu dokonce pro p[k\ < 1999 066 711391).
Obsahuje-li naše tabulka prvočísla aspoň do 500 000, je asi lepší po vyčerpání tabulky v dělení nepokračovat, ale užít jinou metodu.
Testy na složenost
Zvolme nějakou podmínku, které vyhovuje každé prvočíslo a které složená čísla většinou nevyhovují, přičemž je třeba, aby bylo možné podmínku pro dané přirozené číslo rychle ověřit.
Na první pohled se zdá být vhodnou podmínkou Wilsonova věta:
Vn > 1 :       n je prvočíslo 44> (n — 1)! = —1 (mod n)
To je dokonce nutná a dostatečná podmínku prvočíselnosti a byla by tedy nejen testem na složenost, ale také testem na prvočíselnost. Avšak nikdo neví, jak spočítat pro velká N dostatečně rychle číslo (/V — 1)! mod N.
Výhodnější podmínku dává Fermatova věta, neboť je možné rychle počítat mocniny prvků v libovolné grupě.
Předpokládejme, že je dána grupa (G,-) s neutrálním prvkem 1 a že umíme prvky této grupy uchovávat v paměti a také s nimi počítat (násobit je a počítat jejich inverzní prvky).
Výpočet mocniny v grupě
Algoritmus (Binární umocňování zprava doleva).  Pro dané g G G a dané celé číslo n algoritmus počíta g" v grupe (G,-). Proměnné y a z slouží k uchovávaní prvků grupy G.
1. [Inicializace] Polož y -í— 1. Je-li n = 0, pak vytiskni y a skonči.
Je-li n < 0, polož N i--n, z -í— g^1. Jinak polož N -í— n,
z^g-
2. [Násob?] Je-li N liché, polož y ^— z • y.
3. [Poloviční N] Polož N <-       Je-//' N = 0, vytiskni y a skonči. Jinak polož z -í— z • z a jdi na 2.
Důkaz správnosti algoritmu. Vždy před započetím kroku 2 platí y ■ zN = gn. Jistě to platilo při prvním vstupu na krok 2. Označme N', y' a z' nové hodnoty proměnných N, y a z po provedení kroků 2 a 3.
Je-li N sudé, pak y' = y, N' = f, z' = z2, tedy
/   / /\A/' 2-ž- N
y • (z j   =y-z 2 =y-z . Je-li N liché, pak y' = y • z, N' = ^1, z' = z2, tedy
y • (z J    = y • z • z   2   = y • z .
Odhad časové náročnosti algoritmu
Grupové násobení se provádí a + b — 1 krát, kde a je počet cifer ve dvojkovém zápise čísla n a b je počet jedniček v tomto zápise. Jistě platí a + b - 1 < 2[log2     + 1.
Je-1i například G = (Z/mZ)x, je jedno násobení časové náročnosti 0(ln2m), proto celý algoritmus je časové náročnosti 0(ln2mln |n|).
V předchozím algoritmu jsme procházeli cifry dvojkového zápisu čísla n zprava doleva. Zcela analogicky můžeme tyto cifry procházet ovšem zleva doprava. Musíme však znát polohu „nejlevější" jedničky v tomto zápise, tj. znát e G Z s vlastností 2e < lni < 2e+1.
Algoritmus (Binární umocňování zleva doprava).  Pro dané g G G a dané celé číslo n algoritmus počítá gn v grupě (G, •). Je-li /? / 0, musí být dáno e G Z s vlastností 2e < \n\ < 2e+1.
1. [Inicializace] Je-li n = 0, pak vytiskni 1 a skonči. Je-li n < 0,
polož Ni--n, z 4— g^1. Jinak polož N <— n, z <— g. Konečně
(tj. v obou případech) polož y ^— z, E ^— 2e, N ^— N — E.
2. [Konec?] Je-li E = 1, vytiskni y a skonči. Jinak polož E <— -|.
3. [Násob] Polož y <- y • y. Je-//' N > E, polož N <- /V - E, y -í— y • z. Jc// na 2.
Důkaz správnosti algoritmu. Vždy před započetím kroku 2 platí yE ■ zN = gn. Jistě to platilo při prvním vstupu na krok 2, kdy y£ • zN = zT ■ zN-T =zN = g".
Označme E', N' a y' nové hodnoty proměnných E, N a y po provedení kroků 2 a 3.
Je-li N < E', pak E' = f, y' = y2, A/' = /V, tedy
{yif ■ zN' = {y2ý ■ zN = yE ■ zN. Je-li /V > E', pak E1 = f, y' = y2 • z, N1 = N - E', tedy
(y')E'-zw' = (y2-z)f .zw-f =y£-zA/. Vždy před krokem 2 je 0 < N < E. Proto při skončení je N = 0.
Porovnání obou algoritmů
Nevýhody oproti předchozímu algoritmu: je třeba předem spočítat e, to však (je-li základ naší poziční soustavy pro uchovávání „velkých" čísel mocnina 2) je velmi rychlé. Patrně totiž budeme znát pozici nejvyšší nenulové cifry v naší poziční soustavě a pak určení e zabere čas ohraničený konstantou. Zdánlivou nevýhodou je i uchovávání velkého čísla E a výpočet rozdílu N — E. Avšak při implementaci budeme uchovávat e a test N > E i výpočet N — E provedeme manipulací s bitem obsahujícím e-tou dvojkovou cifru čísla N (zde je podstatné, aby skutečně byl základ naší poziční soustavy mocnina 2).
Výhoda: jedno ze dvou násobení, které se provádí v kroku 3, je vždy proměnnou z, ve které je v průběhu celého výpočtu g (nebo g^1 je-li n < 0). Je-li tedy například G = (Z/mZ)x, v případě, že g = a + mZ pro \a\ ohraničené konstantou (třeba základem naší poziční soustavy), je násobení g pouze lineárního času a ne kvadratického. Pak se tedy v kroku 3 provede jedno násobení řádu 0(ln2m) a nejvýše jedno řádu O(lnm). Celý algoritmus je sice stále časové náročnosti 0(ln2 m In       ale s menší O-konstantou.
Využití umocňování pro test na složenost
Pro test na složenost užijeme malou Fermatovu větu: máme tedy
dáno přirozené číslo N, o kterém chceme vědět, zda je to číslo
složené. Budeme to vědět jistě, nalezneme-li celé číslo a,
1 < a < N, pro které platí aN^ ^ 1 (mod N).
Takové a se nazývá svědek složenosti čísla N. Pokud však pro
takové a platí a^-1 = 1 (mod A/), nemůžeme z toho usoudit nic.
Celý algoritmus tedy bude vypadat takto: budeme náhodně volit 3éZ, 1 < a < N, a počítat a^-1 mod N. Pokud pro některé a bude splněno aN^ ^ 1 (mod A/), jsme hotovi a víme, že N je opravdu složené číslo (zmíněné a si můžeme zapamatovat pro případ, že bychom chtěli přesvědčit někoho dalšího o složenosti N). Pokud pro všechna a budeme dostávat a^-1 = 1 (mod N), po jistém počtu pokusů algoritmus ukončíme a usoudíme, že patrně je N prvočíslo. Jestli je však opravdu N prvočíslo, takto zjistit nemůžeme.
Nevýhodou popsaného algoritmu je, že téměř jistě neodhalí jistý typ složených čísel, nazývaných Carmichaelova čísla.
Carmichaelova čísla
Definice. Složené číslo N se nazývá Carmichaelovo číslo, jestliže pro všechna celá čísla a, která jsou nesoudělná s N, platí aN-1 = 1 (mod/V).
Carmichaelovo číslo by náš algoritmus označil za složené pouze tehdy, kdyby za a zvolil číslo soudělné s N, což je však velmi nepravděpodobné. Přitom platí:
Věta (Alford, Granville, Pomeranče). Existuje nekonečně mnoho Carmichaelových čísel.
Příklad. N = 561 = 3 • 11 • 17 je Carmichaelovo číslo.
Důkaz. Pro libovolné celé číslo a nesoudělné s 561 z Fermatovy věty dostáváme a2 = 1 (mod3), a10 = 1 (mod 11) a a16 = 1 (mod 17). Protože 2, 10 i 16 jsou dělitelé čísla 560, je 561 Carmichaelovo číslo.
Výhodnější než testovat Fermatovu větu je proto testování následujícího zesílení Fermatovy věty.
Využití zesílení malé Fermatovy věty
Věta. Pro libovolné liché prvočíslo p a libovolné celé číslo a nedělitelné p platí
a^~ = ±1 (mod p).
Důkaz. Z Fermatovy věty
p\ (aP-1 - 1) = (aV - 1) • {a^ + 1). Protože je p prvočíslo, musí dělit některého z uvedených činitelů.
W-l
Příklad. Test, zda a 2   = ±1 (mod N), by mohl vyloučit i 561, neboť
5280 = 516.17+8 = 58 = 254 = g4 = lg3 = (_1)3 = _j (mod 1?)
a zároveň
5280 = (52)140 = l(mod3), a proto 5280 není kongruentní modulo 561 ani s 1 ani s —1.
Další zesílení malé Fermatovy věty
W-l
Příklad. Test, zda a 2   = ±1 (mod A/J, neodhalí například
N = 1729 = 7-13-19, neboť ^ = 864 = 25 • 33 je dělitelné 6,
12 i 18 a tedy z Fermatovy věty plyne, že pro všechna celá čísla a
N-l
nesoudělná s N platí a 2   =1 (mod A/J.
Věta. Nechť p je liché prvočíslo. Pišme p — 1 = 2ř • q, kde t je přirozené číslo a q je liché. Pak pro každé celé číslo a nedělitelné p bud platí aq = 1 (mod p) nebo existuje e G {0,1,..., t — 1} splňujícíaTq = — 1 (mod p).
Důkaz. Z Fermatovy věty
t-i
pi (3"-i-i)=(aí'-i)-n(a2eq+i).
Protože je p prvočíslo, musí dělit některého z uvedených činitelů.
Teoretický základ testu Millera a Rabina
Věta. Nechť N > 10 je liché složené číslo. Pišme N — 1 = 2ř • q, kde t je přirozené číslo a q je liché. Pak nejvýše čtvrtina z čísel množiny {a G Z; 1 < a < N, (a, N) = 1} splňuje následující podmínku:
aq = 1 (mod N)
nebo existuje e G {0,1,..., t — 1} splňující
a2Sq = -1 (mod N).
Pro dané N algoritmus otestuje podmínku věty pro 20 náhodně zvolených a. Pokud pro některé takové a není podmínka splněna, vytiskne zprávu, že N je složené. Pokud je splněna podmínka pro každé takové a, vytiskne zprávu, že N je asi prvočíslo.
Podle předchozí věty je pravděpodobnost, že bude vytištěna tato zpráva, ačkoli je N složené, menší než 4~20.
Algoritmus Millera a Rabina
Algoritmus (Miller - Rabin).  Pro dané liché N > 3 algoritmus s vysokou pravděpodobností objeví, že N je složené. Pokud se mu to nepodaří, vytiskne zprávu, že N je asi prvočíslo.
1. [Inicializace] Polož q <— N — 1, t -í— 0. Dokud je q sudé, opakuj q <- f, t <- ŕ + 1. Po/oz c <- 20.
2. /ZVo/ a/ Pomoci generátoru náhodných čísel zvol náhodně a G Z, 1 < a < A/. Pa/c po/oz e <- 0, b <- aq mod A/. Je-//' b = 1, jc// na 4.
3. [Umocňuj na druhou] Dokud je b ^ N — 1 a e < t — 2, opakuj b -í— b2 mod N, e -í— e + 1. Je-// b ^ N — 1, vytiskni zprávu, že N je složené a vytiskni svědka složenosti a. Skonči.
4. /í/z proběhlo 20 pokusů?] Polož c -í— c — 1. Je-// c > 0, jc// na 2. J/na/c vytiskni zprávu, že N je asi prvočíslo a skonči.
Odhad časové náročnosti. Algoritmus je řádově stejné časové náročnosti jako umocňování v něm použité (předpokládáme, že generování nového a je řádově rychlejší), proto jde o kubickou časovou náročnost.
Testy na prvočíselnost
Víme, že N je asi prvočíslo (například prošlo testem Millera a Rabina).
Chceme dokázat, že N skutečně prvočíslem je, nebo to vyvrátit. Na následující větě je založen N — 1 test Pocklingtona a Lehmera.
Věta. Nechť N je přirozené číslo, N > 1. Nechť p je prvočíslo dělící N — 1. Předpokládejme dále, že existuje 3pěZ tak, že
N-l
a^1 = 1 (mod/V)   a   (app  - 1, N) = 1.
Nechť pap je nejvyšší mocnina p dělící N — 1. Pa/c pro každý kladný dělitel d čísla N platí
d = 1 (modpa").
Důkaz věty Pocklingtona a Lehmera
Věta. Nechť N je přirozené číslo, N > 1. Nechť p je prvočíslo dělící N — 1. Předpokládejme dále, že existuje 3pěZ tak, že
N-l
3p _1 = 1 (mod N)   a   (app  - 1, N) = 1.
Nechť pap je nejvyšší mocnina p dělící N — 1. Pa/c pro každý kladný dělitel d čísla N platí d = 1 (mod pap).
Důkaz. Každý kladný dělitel d čísla N je součinem prvočíselných dělitelů čísla N, větu dokažme pouze pro d prvočíslo. Podle Fermatovy věty platí a^1 = 1 (mod d), neboť (ap, N) = 1.
W-l W-l
Protože (app  - 1, A/) = 1, platí app  ^1 (mod d). Pro e = min{n G N; a£ = 1 (mod d)} platí e|c/-l, e | /V - 1 a e\^. Kdyby p°p f e, z e | /V - 1 by plynulo e |        spor. Je tedy pap | e, a tedy i pap \ d — 1.
Užití věty Pocklingtona a Lehmera
Věta. Nechť N je přirozené číslo, N > 1. Nechť p je prvočíslo dělící N — 1. Předpokládejme dále, že existuje 3pěZ tak, že
Nechť pap je nejvyšší mocnina p dělící N — 1. Pak pro každý kladný dělitel d čísla N platí d = 1 (mod pap).
Důsledek. Necht N G N, N > 1. Předpokládejme, že můžeme psát N — 1 = F ■ U, kde (F, U) = 1 a F > \//V, přičemž známe rozklad čísla F na prvočinitele. Pak platí:
► jestliže pro každé prvočíslo p | F můžeme najít ap G Z splňující (1) z předchozí věty, pak je A/ prvočíslo;
► je-li N prvočíslo, pak pro libovolné prvočíslo p | N — 1 existuje ap É Z splňující (1).
1 (mod N) a
(1)
Zesílení užití věty Pocklingtona a Lehmera
Důsledek. Nechť N G N, N > 1. Předpokládejme, že můžeme psát
N — 1 = F ■ U, kde (F, U) = 1, přičemž známe rozklad čísla F na
prvočinitele. Dále předpokládejme, že všechna prvočísla dělící U
jsou větší než B £ N a ze platí B ■ F > V~Ň.
Pak platí: jestliže pro každé prvočíslo p | F můžeme najít ap G Z
splňující (1) z předchozí věty a jestliže navíc existuje 3y e Z
splňující
a^1 = 1 (mod N)   a   (a£-l,/V) = l, pa/c je N prvočíslo.
Je-li naopak N prvočíslo a U > 1, pa/c požadovaná ap, 3y e Z existují.
Důkaz. Pro každé prvočíslo c/ | /V vime, že c/ = 1 (mod F). Protože (au, N) = 1, existuje e = min{n G N; anu = 1 (mod c/)}. Odtud e | J - 1, e|/V-lae|F. Kdyby (e, U) = 1, z e | /V - 1 = FU by plynulo e | F. Je tedy (e, í/) > 1 a protože U je dělitelné pouze prvočísly většími než B, platí (e, U) > B. Protože (F, U) = 1, z c/ = 1 (mod e) a d = 1 (mod F) plyne c/ = 1 (mod F • (e, í/)) a tedy d > F ■ (e, U) > FB > vTV.
Príklad užití věty Pocklingtona a Lehmera - Pépinův test
Pro k G Z, k > 0, se F^ = 22k + 1 nazýva /c-té Fermatovo číslo. Pépinův test: F^ je prvočíslo, právě když S^-1)/2 = —1 (mod F^).
Důkaz. „<í=" z důsledku věty Pocklingtona a Lehmera.
„=^" z kvadratického zákona reciprocity:   s^-1)/2 = (J.) =
= (f)-(-i)¥¥ = (f) = (f) = -iHFt).
► F0 = 3, Fl = 5, F2 = 17, F3 = 257, F4 = 65537 jsou prvočísla.
► Rozklad čísla F^ na prvočinitele je znám jen pro k < 11.
► Fk jsou složená pro každé k = 5, 6,..., 32 (ačkoli u F20 ani F24 není znám žádný prvočíselný dělitel).
► Největší Fk, pro které je znám prvočíselný dělitel, je F2543548 dělitelné prvočíslem 9 • 22543551 + 1 (objeveno 22. 6. 2011).
► Otevřené problémy: Existuje nekonečně mnoho složených Fermatových čísel? Existuje nekonečně mnoho Fermatových čísel, která jsou prvočísla?
Implementace algoritmu (tzv. N —1 test)
Vstupem je číslo N, které již prošlo testem Millera - Rabina, tedy číslo, o kterém s vysokou pravděpodobností platí, že je to prvočíslo. Je třeba to však dokázat.
V první části algoritmu rozkládáme číslo N — 1 na součin F ■ U a to tak, že podrobíme N — 1 algoritmu pokusného dělení, ukládáme získané dělitele a skončíme, až platí BF > V/V, nebo až je B „dost velké", abychom si byli jisti zastavením v „rozumném" čase (zde B, F, U značí totéž, co v předchozí větě). Pak náhodně volíme celá čísla ap v intervalu 1 < ap < N a
W-l
počítáme bp = app  mod N a cp = bp mod N do té doby, než cp = 1 (mod N) a (bp - 1, N) = 1.
Je-li N opravdu prvočíslo, podmínku (bp — 1, N) = 1 splňuje většina z čísel ap, přesněji právě ^-^(N — 1) čísel z N — 1 čísel 1, 2, ..., N — 1. Můžeme tedy očekávat, že takové ap brzy najdeme. Pokud by však N bylo „velké" Carmichaelovo číslo, algoritmus by se s velkou pravděpodobností nezastavil (zastaví se jen když náhodně volené ap bude soudělné s N).
Časová náročnost algoritmu
Není-li N prvočíslo, algoritmus se nemusí zastavit.
Ani pro prvočísla nelze stanovit odhad: záleží na tom, jak snadno lze rozkládat číslo N — 1. Následné hledání čísel ap je velmi rychlé (kontrola, zda zvolené ap splňuje podmínku (1) je kvadratické časové náročnosti, navíc lze volit ap „malá").
Je možné nerozloženou část U podrobit testu Millera a Rabina a v případě, že test zjistí, že U je asi prvočíslo, dokázat nejprve prvočíselnost U (a tedy pracovat rekurzivně).
Zobecnění algoritmu
Je-li N prvočíslo, pak existuje těleso ¥N2 o N2 prvcích. Jeho multiplikativní grupa je cyklická řádu N2 — 1 = (A/ — 1)(/V + 1). Existuje tedy a G ¥N2 řádu N + 1, tj. splňující aN+1 = 1, avšak
a p      1 pro libovolné prvočíslo p dělící N + 1.
Tuto myšlenku je možno využít pro tzv. N + 1 test analogický
N — 1 testu. V něm vystupuje faktorizace čísla N + 1 místo N — 1.
Pro důkaz prvočíselnosti čísla A/ lze pak využít informace o dělitelích čísla N, získané z obou testů.
Podobně lze využít těleso Fw3 (a tedy faktorizovat
ig^L = /v2 + n + 1), těleso FW4 (a faktorizovat        = A/2 + 1)
nebo těleso FW6 (a faktorizovat (/v3-^íXAŕ+i) =     — ^ + !)■
Vždy nám však už vycházejí čísla podstatně větší než N a tedy pravděpodobně obtížně rozložitelná.