58
5. Aplikace teorie čísel
5.1. Výpočetní aspekty teorie čísel. V mnoha praktických úlohách využívajících výsledky teorie čísel je zapotřebí umět rychle provést jeden či více z následujících výpočtů:
(1) běžné aritmetické operace (součet, součin, dělení se zbytkem) na celých číslech,
(2) zbytek mocniny celého čísla a na přirozené číslo n po dělení daným m.
(3) inverzi celého čísla a modulo m G N,
(4) největší společný dělitel dvou celých čísel (a případně koeficienty do Bezoutovy rovnosti),
(5) rozhodnout o daném čísle, je-li prvočíslo nebo složené,
(6) v případě složenosti rozložit dané číslo na součin prvočísel.
Základní aritmetické operace se i na velkých číslech obvykle provádějí obdobně jako jsme se to učili na základní a střední škole, kdy umíme sčítat v lineárním, násobit a dělit se zbytkem v kvadratickém čase. Pro násobení, které je základem mnoha dalších operací, existují asymptoticky rychlejší algoritmy (typu rozděl a panuj) - např. první takový Karatsubův (1960) časové náročnosti @(nlog23) nebo algoritmus Schonhage-Strassenův (1971) časové náročnosti ©(n log n log log n), který využívá tzv. Fast Fourier Transform. Ten je ale přes svou asymptotickou převahu výhodný až pro násobení čísel majících alespoň desítky tisíc cifer (a používá se tak např. v GIMPS).
Pěkný přehled je např. na http: //en. wikipedia. org/wiki/Computat ional complexity_of_mathematical_operations
GCD a modulární inverze. Jak už jsme ukazovali dříve, výpočet řešení kongruence a ■ x = 1 (mod m) s neznámou x lze snadno (díky Bezoutově větě) převést na výpočet největšího společného dělitele čísel a a m a na hledání koeficientů k, l do Bezoutovy rovnosti k-a + l-m = 1 (nalezené A; je pak onou hledanou inverzí a modulo m).
function  extended_gcd (a , m) i f m = 0
return (1, 0)
e 1 s e
(q,   r) :=  divide   (a, m)
(k,   1) :=  extended.gcd(m, r)
return (1,  k — q *  1)
Podrobná analýza (viz např. [Knuth] nebo [Wiki]) ukazuje, že tento algoritmus je kvadratické časové složitosti.
Modulární umocňování je, jak jsme již viděli dříve, velmi využívaná operace mj. při ověřování, zdaje dané číslo prvočíslo nebo číslo složené.
59
Jedním z efektivních algoritmů je tzv. modulární umocňování zprava doleva:
function  modular_pow (base ,   exponent, modulus) result   := 1 while  exponent > 0
if   (exponent mod 2 = 1):
result   :=  (result  * base) mod modulus exponent  := exponent » 1 base = (base * base) mod modulus return result
Algoritmus modulárního umocňování je založen na myšlence, že např. při počítání 264 (mod 1000)
• není třeba nejprve počítat 264 a poté jej vydělit se zbytkem číslem 1000, ale lépe je postupně násobit „dvojky" a kdykoliv je výsledek větší než 1000, provést redukci modulo 1000,
• ale zejména, že není třeba provádět takové množství násobení (v tomto případě 63 naivních násobení je možné nahradit pouze šesti umocněními na druhou, neboť
264 = ((((^2)2)2)2)2)2^
příklad (Ukázka průběhu algoritmu). Vypočtěme 2560 (mod 561). Protože 560 = (1000110000)2, dostaneme uvedeným algoritmem
exponent	base	result	exp's last digit
560	2	1	0
280	4	1	0
140	16	1	0
70	256	1	0
35	460	1	1
17	103	460	1
8	511	256	0
4	256	256	0
2	460	256	0
1	103	256	1
0	511	1	0
A tedy 2560 = 1 (mod 561).
V průběhu algoritmu se pro každou binární číslici exponentu provede umocnění základu na druhou modulo n (což je operace proveditelná v nejhůře kvadratickém čase), a pro každou „jedničku" v binárním zápisu navíc provede jedno násobení. Celkově jsme tedy schopni provést modulární umocňování nejhůře v kubickém čase.
60
5.2. Testy na složenost. Přestože platí základní věta aritmetiky, která nám garantuje, že každé přirozené číslo se dá jednoznačným způsobem rozložit na součin prvočísel, praktické nalezení tohoto rozkladu je obvykle velmi výpočetně náročná operace, obvykle prováděná v několika krocích:
(1) nalezení všech dělitelů nepřevyšujících určitou hranici (metodou pokusného dělení všemi prvočísly až do této hranice, typicky je touto hranicí cca 106)
(2) otestování zbylého faktoru na složenosti (tzv. test na složenost, testující některou nutnou podmínku prvočíselnosti)
a) pokud test složenosti prohlásil, že zkoumané číslo je asi prvočíslo, pak testem na prvočíselnost ověřit, že je to opravdu prvočíslo.
b) pokud test složenosti prohlásil, že zkoumané číslo je složené, pak nalézt netriviálního dělitele.
Takto je posloupnost kroků prováděna z toho důvodu, že jednotlivé algoritmy mají postupně (výrazně) rostoucí časovou složitost. V roce 2002 Agrawal, Kayal a Saxena publikovali algoritmus, který testuje prvočíselnost v polynomiálním čase, prakticky je ale zatím stále efektivnější používat výše uvedený postup.
Takzvané testy na složenost testují některou nutnou podmínku prvočíselnosti. Nej jednodušší takovou podmínkou je Malá Fermatova věta.
tvrzení 5.1. Fermatův test Existuje-li pro dané N nějaké a ^ 0 (mod N) takové, že aN~ľ ^ 1 (mod N), pak N není prvočíslo.
Bohužel nemusí být pro dané složené N snadné najít takové a, že Fermatův test odhalí složenost N; pro některá výjimečná N dokonce jediná taková a jsou ta soudělná s N; jejich nalezení je tedy ekvivalentní s nalezením dělitele, a tedy i s rozkladem N na prvočísla.
Carmichaelova čísla. Skutečně existují taková nehezká (nebo extrémně hezká?) složená čísla N, která splňují, že pro libovolné a nesoudělné s N platí aN~ľ = 1 (mod N). Taková čísla se nazývají Carmichaelova, nejmenší z nich je 561 = 3 • 11 • 17 a teprve v roce 1992 se podařilo dokázat, že jich je dokonce nekonečně mnoho (v OEIS jde o posloupnost A002997: 561,1105,1729, 2465, 2821,...).
61
příklad. Dokážeme, že 561 je Carmichaelovo, tj. že pro každé a g N, které je nesoudělné s 3 • 11 • 17, platí a560 = 1 (mod 561).
Z vlastností kongruencí víme, že stačí dokázat tuto kongruenci mo-dulo 3,11 i 17. To ale dostaneme přímo z Malé Fermatovy věty, protože takové a splňuje a2 = 1 (mod 3), a10 = 1 (mod 11), a16 = 1 (mod 17), přičemž 2,10 i 16 dělí 560 (viz též Korseltovo kritérium).
VĚTA 36 (Korseltovo kritérium). Složené číslo n je Carmichae-lovým číslem, právě když je nedělitelné čtvercem (square-free) a pro všechna prvočísla p dělící n platí p — 1 | n — 1.
příklad. Dokažte, že čísla 2465 a 2821 jsou Carmichaelova.
Eulerův test (též Euler-Jacobi, Solovay-Strassen). Fermatův test lze zlepšit s využitím kvadratických zbytků na Eulerův test, ale výše zmíněný problém se ani tak zcela neodstraní.
tvrzení 5.2 (Eulerův test). Je-li N prvočíslo a a g Z, N \ a, pak
N-l ,
a~ = (a/N)   (mod N).
příklad. Uvažme3 a = 5: Pak 5280 = 1 (mod 3),5280 = 1 (mod 11), přitom 5280 = — 1 (mod 17), proto určitě 5280 ^ ±1 (mod 561). Zde
N — l
došlo k tomu, že neplatilo a~^~ = ±1 (mod N), proto ani nebylo třeba testovat hodnotu Jacobiho symbolu, často ale právě Eulerův test může odhalit složené číslo i v případě, kdy tato mocnina je rovna ±1.
přiklad. Test, zda a~^~ = ±1 (mod N), 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 nesoudělná s N platí a~^~ = 1 (mod N).
Přitom ale pro a = 11 dostaneme (p^g) = — 1 a Eulerův test tedy složenost čísla 1729 odhalí.
Poznamenejme, že hodnotu Legendreova nebo Jacobiho symbolu (£) lze díky zákonu kvadratické reciprocity spočítat v lepším než kubickém čase.
Definice (Pseudoprvočísla). Složené číslo n se nazývá pseudo-prvočíslo, pokud projde testem na složenost a není jím odhaleno jako složené. Máme tak
(1) Fermatova pseudoprvočísla o základu a
(2) Eulerova pseudoprvočísla
(3) silná (strong) pseudoprvočísla o základu a, pokud projdou následujícím testem na složenost.
Testování by selhalo už pro a = 3, ale to je dělitel, my chceme ukázat, že test může uspět i bez nalezení dělitele.
62
TVRZENÍ 5.3 (Test na složenost - zesílení Malé Fermatovy věty). Nechť p je liché prvočíslo. Píš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í a2'°q = — 1 (mod p)).
Ukazuje se, že tento snadný test výrazně zesiluje schopnost rozpoznávat složená čísla. Nej menší silné pseudoprvočíslo o základu 2 je 2047 (přitom nej menší Fermatovo o základu 2 bylo již 341) a při otestování základů 2, 3 a 5 dostaneme nejmenší pseudoprvočíslo 25326001. Jinými slovy, pokud nám stačí testovat pouze čísla do 2 • 107, pak stačí tento test na složenost provést pouze pro základy 2, 3 a 5. Pokud číslo není odhaleno jako složené, pak je určitě prvočíslem.
Na druhou stranu, bylo dokázáno, že žádná konečná báze není dostatečná.
Test Millera a Rabina je praktickou aplikací předchozího testu, kdy jsme navíc schopni omezit pravděpodobnost neúspěchu.
VĚTA 37. Nechť N > 10 je liché složené číslo. Pišme N—l =2t -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í
a2eq = -l (modiV).
V praktických implementacích se obvykle testuje cca 20 náhodných základů (příp. nejmenších prvočíselných základů). V takovém případě dostáváme z předchozí věty, že pravděpodobnost neodhalení složeného čísla je menší než 2~40.
Časová náročnost algoritmu je asymptoticky stejná jako složitost modulárního umocňování, tedy nejhůře kubická. Je ale třeba si uvědomit, že test je nedeterministický a spolehlivost jeho deterministické verze závisí na tzv. zobecněné Riemannově hypotéze (GRH).
63
5.3. Testy na prvočíselnost. Testy na prvočíselnost přicházejí na řadu obvykle ve chvíli, kdy testy na složenost prohlásí, že jde pravdepodobne o prvočíslo, případně se provádějí rovnou u speciálních typů čísel. Uveďme nejprve přehled nejznámějších testů.
(1) AKS (2002) - obecný polynomiální test na prvočísla
(2) Pocklington-Lehmerův test - test na prvočíselnost subexpo-nenciální složitosti
(3) Lucas-Lehmerův test - test prvočíselnosti pro Mersenneho čísla
(4) Pépinův test (1877) - test prvočíselnosti pro Fermatova čísla
(5) ECPP - test prvočíselnosti založený na tzv. eliptických křivkách
Speciální testy — Mersenneho čísla.
tvrzení 5.4 (Lucas-Lehmerův test). Definujme posloupnost (sn)^Lc :urzívně předpisem s$ = 4, sn+i =     — 2.
Pak je číslo Mp = 2P — 1 prvočíslo, právě tehdy, když Mp děli sp_2-
// Determine   i f Mp = 2P — 1  is prime Lucas—Lehmer (p)
var s = 4
var M = 2p - 1
repeat p — 2 times : s = s2 - 2 (mod M)
if s = 0 return PRIME else  return COMPOSLTE
Časová složitost testuje asymptoticky stejná jako v případě Miller-Rabinova testu, v konkrétních případech je ale efektivnější.
Speciální testy — Fermatova čísla. Fermatova čísla jsou čísla tvaru Fn = 22" + 1. Pierre de Fermat v 17. století vyslovil hypotézu, že všechna čísla tohoto tvaru jsou prvočísly (zřejmě veden snahou zobecnit pozorování pro F0 = 3,F1 = 5, F2 = 17, F3 = 257 a FA = 65537. V 18. století ale Leonhard Euler zjistil, že F^ = 641 x 6700417 a dodnes se nepodařilo nalézt žádné další Fermatovo prvočíslo. Vzhledem k rychle rostoucí velikosti těchto čísel je počítání s nimi velmi časově náročné (a ani následující test tak není příliš používán). V současné době nej menší netestované Fermatovo číslo je F33, které má 2 585 827973 číslic, a je tak výrazně větší než největší dosud nalezené prvočíslo.
tvrzení 5.5 (Pépinův test). Označme Fn = 22" + 1 tzv. n-té Fermatovo číslo. Pak Fn je prvočíslo, právě když
3^ = -1   (mod Fn).
Vidíme, že jde o velmi jednoduchý test, který je vlastně pouze malou částí Eulerova testu na složenost.
64
důkaz korektnosti pépinova testu. Platí-li 3^2^ = -1 (mod Fn je nutně Fn — 1 řádem čísla 3 modulo Fn, proto je Fn prvočíslo.
Obráceně, nechť je Fn prvočíslo. Z Eulerova kritéria dostáváme, že 3^2" = (JQ (mod Fn), tj. stačí nám určit hodnotu (jr-). To je ale snadné, protože Fn = 2 (mod 3) a tedy (jjfy = —1. Dále Fn = 1 (mod 4), proto díky zákonu kvadratické reciprocity dostáváme (Jr) = -1. " □
Pocklington-Lehmerův test. Na závěr uveďme i obecný test na prvočíselnost, který použijeme, pokud chceme vysokou pravděpodobnost Miller-Rabínova algoritmu proměnit v jistotu (ta jistota je ale relativní - udává se, že pravděpodobnost selhání Miller-Rabínova algoritmu je nižší než HW chyba během výpočtu).
věta 38. Nechť N je přirozené číslo, N > 1. Nechť p je prvočíslo dělicí N — 1. Předpokládejme dále, že existuje ap g Z tak, že
í — \
aNp-1 = 1   (modiV)   a     a/ -l,iVl=i.
Nechť pap je nejvyšší mocnina p dělící N — 1. Pak pro každý kladný dělitel d čísla N platí
d=l   (mod pap).
důkaz věty pocklingtona a Lehmera. 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),
N-l N-l
neboť (ap,N) = 1. Protože {app  — l,iV) = 1, platí app   ^ 1 (mod d).
Označme e řád ap modulo d. Pak platí e \ d — 1, e \ N — 1 a e •
Kdyby pap \ e, z e | N — 1 by plynulo e |        spor. Je tedy pap \ e
N-l P
P
a tedy i pap \ d — 1. □
Užití věty Pocklingtona a Lehmera.
tvrzení 5.6. Nechť N g n, N > 1. Předpokládejme, že můžeme psát N — 1 = F - U, kde (F, U) = 1 a F > y/Ň, 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 z předchozí věty, pak je N prvočíslo;
• je-li N prvočíslo, pak pro libovolné prvočíslo p | N — 1 existuje ap g Z s požadovanými vlastnostmi.
důkaz, ad 1. Podle Věty je d = 1 (mod pro všechny prvočíselné faktory F, proto je d = 1 (mod F), a tedy d > y/Ň.
ad 2. Stačí za ap zvolit primitivní kořen modulo prvočíslo N (nezávisle nap). □
65
poznámka. Předchozí test v sobě zahrnuje Papinův test (totiž pro N = Fn máme p = 2, kterému vyhovuje svědek prvočíselnosti ap = 3).
5.4. Hledání dělitele. Máme-li testem na složenost potvrzeno, že jde o číslo složené, obvykle chceme najít netriviálního dělitele. Jde ale o výrazně obtížnější úkol (což je na druhé straně výhodné pro RSA a podobné protokoly), proto si k tématu uvedeme jen stručný přehled používaných metod.
(1) Pokusné dělení - v krajním případě je možné testovat potenciální (prvočíselné) dělitele až do y/n, tedy v nej horším případě vykonáme až 0(y/n) dělení.
(2) Pollardova p-metoda
(3) Pollardova p — 1 metoda
(4) faktorizace pomocí eliptických křivek
(5) Metoda kvadratického síta (QS)
(6) Metoda síta v číselném tělesa (NFS)
Podrobnosti viz předmět M8190 Algoritmy teorie čísel.
5.5. Kryptografie s veřejným klíčem. Dva hlavní úkoly pro kryptografie s veřejným klíčem (PKC - public key cryptography) jsou zajistit
• šifrování, kdy zprávu zašifrovanou veřejným klíčem příjemce není schopen rozšifrovat nikdo kromě něj (resp. držitele jeho soukromého klíče)
• podepisování, kdy integrita zprávy podepsané soukromým klíčem odesílatele může být ověřena kýmkoliv s přístupem k veřejnému klíči odesílatele
Nejčastěji používané systémy PKC:
• RSA (šifrování) a odvozený systém pro podepisování zpráv
• Digital signatuře algorithm (DSA) a varianta založená na eliptických křivkách (ECDSA)
• Rabínův kryptosystém (a podepisování)
• ElGamal kryptosystém (a podepisování)
• Kryptografie eliptických křivek (ECC)
• Diffie-Hellmanův protokol na výměnu klíčů (DH)
Princip digitálního podpisu. Proces podepisování a ověření podpisu zprávy M probíhá obvykle v následujících krocích.
Podepisování
(1) Vygeneruje se otisk (hash) H m zprávy pevně stanovené délky (např. 160 nebo 256 bitů).
(2) Podpis zprávy Sa{Hm) je vytvořen (pomocí dešifrování) z tohoto hashe s nutností znalosti soukromého klíče podepisujícího.
(3) Zpráva M (případně zašifrovaná veřejným klíčem příjemce) je spolu s podpisem odeslána.
66
Ověření podpisu
(1) K přijaté zprávě M se (po jejím případném dešifrování) vygeneruje otisk H'M
(2) S pomocí veřejného klíče (deklarovaného) odesílatele zprávy se rekonstruuje původní otisk zprávy Va{Sa{Hm)) = Hm-
(3) Oba otisky se porovnají H m = H'M1.
RSA Ron Rívest, Adi Shamir, Leonard Adleman (1977; C. Cocks, GCHQ - 1973)
• každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a
• generování klíčů: zvolí dvě velká prvočísla p, q, vypočte n = pq, f(n) = (p — l)(g — 1) [n je veřejné, ale íp{n) nelze snadno spočítat ]
• zvolí veřejný klíč e a ověří, že (e, f(n)) = 1
• např. pomocí Euklidova algoritmu spočítá tajný klíč d tak, aby e • d = 1 (mod f (n))
• zašifrování numerického kódu zprávy M: C = Ce(M) = Me (mod n)
• dešifrování šifry C: OT = D^C) = Cd (mod n)
Rabínův kryptosystém je prvním veřejným kryptosystémem, k jehož prolomení je prokazatelně potřeba faktorizovat modul. Uvedeme si jej ve zjednodušené verzi:
• každý účastník A potřebuje dvojici klíčů - veřejný V a a soukromý S a
• generování klíčů: A zvolí dvě podobně velká prvočísla p, q = 3 (mod 4), vypočte n = pq.
• V a = n, SA = (p, q)
• zašifrování numerického kódu zprávy M: C = Ce(M) = M2 (mod n)
• dešifrování šifry C: vypočtou se (čtyři) odmocniny z C modulo n a snadno se otestuje, která z nich byla původní zprávou.
Výpočet druhé odmocniny z C modulo n = pq,
kde p = q = 3 (mod 4) .
• vypočti r = C*(p+1)/4 (mod p) a s = C^1^4 (mod q)
• vypočti a, b tak, že ap + bq = 1
• polož4 x = (aps + bqr) (mod n), y = (aps — bqr) (mod n)
• druhými odmocninami z C modulo n jsou ±x, ±y.
příklad. V Rabínově kryptosystému Alice zvolila za svůj soukromý klíč p = 23, q = 31, veřejným klíčem je pak n = pq = 713. Zašifrujte zprávu m = 327 pro Alici a ukažte, jak bude Alice tuto zprávu dešifrovat.
4Uvědomte si, že jde vlastně o aplikaci Čínské zbytkové věty!
67
Řešení, c = 692, kandidáti původní zprávy jsou ±4-23-14±3-31-18 (mod 713).
Diffie-Hellman key exchange. Whítfield Diffie, Martin Hellman (1976; M. Williamson, GCHQ - 1974)
Výměna klíčů pro symetrickou kryptografii bez předchozího kontaktu (tj. náhrada jednorázových klíčů, kurýrů s kufříky, ...).
• Dohoda stran na prvočísle p a primitivním kořenu g modulo p (veřejné)
• Alice vybere náhodné a a pošle ga (mod p)
• Bob vybere náhodné b a pošle gb (mod p)
• Společným klíčem pro komunikaci je gab (mod p).
Kryptosystém ElGamal. Z protokolu DH na výměnu klíčů je odvozen šifrovací algoritmus ElGamal:
• Alice zvolí prvočíslo p spolu s primitivním kořenem g
• Alice zvolí tajný klíč x, spočítá h = gx (mod p) a zveřejní veřejný klíč (p,g,h)
• šifrování zprávy M: Bob zvolí náhodné y a vypočte C\ = gy (mod p) a C*2 = M ■ hy (mod p) a pošle (Ci, C2)
• dešifrování zprávy: OT = C^/Cf
poznámka. Analogicky jako v případě RSA lze odvodit podepisování.
Eliptické křivky jsou rovinné křivky o rovnici tvaru y2 = x3 + ax + b a zajímavé jsou tím, že na jejich bodech lze definovat operace tak, že výslednou strukturou bude komutativní grupa.
Přitom uvedené operace lze efektivně provádět a navíc se ukazuje, že mají (nejen) pro kryprografii zajímavé vlastnosti - srovnatelné bezpečnosti jako RSA lze dosáhnout již s podstatně kratšími klíči. Výhodou je rovněž velké množství použitelných eliptických křivek (a tedy grup různé struktury) podle volby parametru a, b .
Některé protokoly:
• ECDH - přímá varianta DH na eliptické křivce (jen místo generátoru se vybere vhodný bod na křivce)
• ECDSA - digitální podpis pomocí eliptických křivek.
poznámka. Problém diskrétního logaritmu (ECDLP). Navíc se ukazuje, že eliptické křivky jsou velmi dobře použitelné při faktorizaci prvočísel.
6. Diofantické rovnice
Už ve třetím století našeho letopočtu se řecký matematik Diofan-tos zabýval řešením rovnic, ve kterých za řešení připouštěl jen celá