´ centrum mezina ´ rodn´ı Jihomoravske mobility
T-exkurze
Teorie ˇ c´ısel, aneb elektronick´ y podpis a ˇ sifrov´ an´ı
Brno 2013
Petr Pup´ık
Obsah
Obsah ˇ 2 Sifrovac´ ı algoritmy RSA a ElGamal 12 2.1 Algoritmus RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2 ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Z´ avˇ er
19
Literatura
20
ˇ Kapitola 2. Sifrovac´ ı algoritmy RSA a ElGamal
Kapitola 2 ˇ Sifrovac´ ı algoritmy RSA a ElGamal Pˇredstavme si, ˇze chceme poslat nˇejakou zpr´avu. Potˇrebujeme vˇsak, aby ji nepˇreˇcetl nikdo jin´ y, neˇz adres´at. Je tˇreba ji tedy nˇejak´ ym zp˚ usobem zaˇsifrovat. M´ame nˇekolik moˇznost´ı. Jedna z nich je, ˇze se s adres´atem dopˇredu sejdeme, domluv´ıme si, jak´ ym zp˚ usobem budeme ˇsifrovat, pot´e se rozejdeme a n´aslednˇe si m˚ uˇzeme pos´ılat zaˇsifrovan´e zpr´avy. Protoˇze jsme se jiˇz seˇsli, v´ıme, jak danou zpr´avu deˇsifrovat. Ne vˇzdy vˇsak m´ame moˇznost se s adres´atem sej´ıt, nebo si s n´ım domluvit, jak´ ym zp˚ usobem budeme danou zpr´avu ˇsifrovat. Mus´ıme tedy zpr´avu ˇsifrovat jin´ ym zp˚ usobem. My si v tomto textu uk´aˇzeme algoritmy RSA a ElGamal.
2.1
Algoritmus RSA
Algoritmus RSA publikovali poprv´e matematici Ron Rivest, Adi Shamir a Leonard Adleman v roce 1977. Sv˚ uj n´azev dostal podle prvn´ıch p´ısmen pˇr´ıjmen´ı sv´ ych objevitel˚ u. RSA algrotimus vyuˇz´ıv´a nemoˇznosti“ rozloˇzit dan´e ˇc´ıslo na souˇcin prvoˇc´ısel. Pojd’me si nyn´ı ” tento algoritmus popsat. Pˇredstavme si, ˇze Bob chce poslat zpr´avu Alici. Zpr´avou je vˇzdy nˇejak´e pˇrirozen´e ˇc´ıslo. Pojd’me si tedy ˇr´ıci, co mus´ı oba udˇelat. Dejme tomu, ˇze Bob chce Alici poslat zpr´avu m ∈ N. Zaˇc´ıt“ vˇsak mus´ı Alice: ” 1. Alice si zvol´ı dvˇe velk´a“ prvoˇc´ısla p, q. ” 2. Alice spoˇc´ıt´a n = p · q. 3. Alice spoˇc´ıt´a ϕ(n) = (p − 1) · (q − 1). 4. Alice zvol´ı pˇrirozen´e ˇc´ıslo e takov´e, ˇze je s ϕ(n) nesoudˇeln´e. 5. Alice urˇc´ı pˇrirozen´e ˇc´ıslo d takov´e, ˇze e · d ≡ 1 (mod ϕ(n)). 6. Alice odeˇsle neˇsifrovanˇe Bobovi takzvan´ y veˇrejn´ y kl´ıˇc (n, e).
12
ˇ Kapitola 2. Sifrovac´ ı algoritmy RSA a ElGamal
Bob tedy nyn´ı zn´a ˇc´ısla n a e. Tato ˇc´ısla zn´a i kdokoliv jin´ y, protoˇze byly odesl´any neˇsifrovanˇe. Co vˇsak nev´ı nikdo kromˇe Alice je, jak vzniklo ˇc´ıslo n, nikdo tedy kromˇe Alice nezn´a ϕ(n) a koneˇcnˇe, nikdo kromˇe Alice nezn´a ˇc´ıslo d. Pojd’me si jeˇstˇe vysvˇetlit, jak´ ym zp˚ usobem Alice z´ısk´a jednotliv´a ˇc´ısla. Hodnotu ϕ(n) ˇ ıslo e, kter´e je s zjist´ı snadno podle tvrzen´ı ??, protoˇze zn´a prvoˇc´ıseln´ y rozklad ˇc´ısla n. C´ ϕ(n) nesoudˇeln´e zvol´ı Alice snadno. Trochu obt´ıˇznˇejˇs´ı to bude s ˇc´ıslem d. Pro pˇrirozen´e ˇc´ıslo d m´a platit, ˇze e · d ≡ 1 (mod ϕ(n)). My jsme vˇsak ˇc´ıslo e volili tak, ˇze je s ϕ(n) nesoudˇeln´e. Plat´ı tedy, ˇze (e, ϕ(n)) = 1. Podle Bezoutovy identity ?? vˇsak existuj´ı cel´a ˇc´ısla x, y takov´a, ˇze 1 = e · x + ϕ(n) · y. To v ˇreˇci kongruenc´ı znamen´a, ˇze e · x ≡ 1 (mod ϕ(n)). Poloˇzme tedy d = x, kde x jsme dostali jako koeficient u ˇc´ısla e v Bezoutovˇe identitˇe. Nyn´ı se pod´ıvejme, co provede Bob, aby poslal zpr´avu m. 1. Bob obdrˇz´ı od Alice veˇrejn´ y kl´ıˇc (n, e). 2. Bob spoˇc´ıt´a, jak´ y zbytek d´av´a me po dˇelen´ı n. Oznaˇcme ho c, tj. c ≡ me
(mod n).
3. Bob poˇsle neˇsifrovanˇe Alici zpˇet ˇc´ıslo c. Pokud nyn´ı nˇekdo sleduje konverzaci mezi Alic´ı a Bobem, m´a moment´alnˇe u sebe ˇc´ısla n, e a c. Zaj´ımav´e je tak´e to, ˇze pokud Bob zaˇsifruje zpr´avu m, jiˇz tuto zpr´avu takt´eˇz nedok´aˇze deˇsifrovat, stejnˇe jako ostatn´ı (kromˇe Alice). Pojd’me se tedy pod´ıvat na to, jak Alice deˇsifruje zpr´avu c, kterou obdrˇzela od Boba. 1. Alice obdrˇzela od Boba zpr´avu c od Boba. 2. Alice spoˇc´ıt´a, jak´ y zbytek d´av´a cd po dˇelen´ı ˇc´ıslem n a dostane t´ım zpr´avu m. Jistˇe v´as nyn´ı napadne, jak je moˇzn´e, ˇze skuteˇcnˇe dostala zpr´avu m. Pojd’me si to hned dok´azat. Bob vytvoˇril ˇc´ıslo c tak, ˇze c ≡ me
(mod n). Plat´ı proto, ˇze
cd ≡ (me )d ≡ me·d
(mod n).
Protoˇze ed ≡ 1 (mod n), podle 5, je i ed ≡ 1 (mod p − 1). To podle definice kongruence znamen´a, ˇze existuje cel´e ˇc´ıslo k takov´e, ˇze ed = 1 + k · (p − 1). Dosad’me cd ≡ me·d ≡ m1+k·(p−1) ≡ m · (mp−1 )k
(mod p).
Nyn´ı vyuˇzijeme Mal´e Fermatovy vˇety ?? cd ≡ me·d ≡ m1+k·(p−1) ≡ m · (mp−1 )k ≡ m · 1k ≡ m (mod p). To znamen´a, ˇze cd ≡ (mod p). Obdobnˇe se odvod´ı, ˇze cd ≡ m (mod q). Podle ˇ ınsk´e zbytkov´e vˇety ?? tak dost´av´ame, ˇze cd ≡ m (mod p · q), tj. C´ cd ≡ m (mod n). 13
ˇ Kapitola 2. Sifrovac´ ı algoritmy RSA a ElGamal
Algoritmus RSA je tedy zaloˇzen na nemoˇznosti urˇcen´ı ˇc´ısla ϕ(n). To bychom zjistili, pokud bychom umˇeli rozloˇzit ˇc´ıslo n na souˇcin prvoˇc´ısel. To vˇsak um´ı jen Alice. Zaj´ımav´e je, ˇze pokud Bob zaˇsifruje zpr´avu a zapomene ji, tak se mu ji nepodaˇr´ı rozˇsifrovat. Pojd’me si nyn´ı uk´azat konkr´etnˇe zaˇsifrov´an´ı nˇejak´e zpr´avy pomoc´ı RSA algoritmu. Volme vˇsak mal´a“ ˇc´ısla, abychom zvl´adli sledovat, co se v algoritmu dˇeje. ” Pˇ r´ıklad 2.1.1. Bob chce Alici odeslat zpr´avu m = 12. Alice si zvol´ı p = 23, q = 31. Urˇcete, jak Bob zaˇsifruje zpr´avu a d´ale tuto zpr´avu deˇsifrujte. ˇ sen´ı. Pojd’me postupovat pˇresnˇe tak, jak jsme si tento algoritmus pˇredstavili: Reˇ 1. Alice m´a prvoˇc´ısla p = 23, q = 31. 2. Alice spoˇc´ıt´a n = p · q = 23 · 31 = 713. 3. Alice spoˇc´ıt´a ϕ(n) = (p − 1) · (q − 1) = 22 · 30 = 660. 4. Alice zvol´ı pˇrirozen´e ˇc´ıslo e takov´e, ˇze je s ϕ(n) nesoudˇeln´e, volme e = 17. 5. Alice urˇc´ı pˇrirozen´e ˇc´ıslo d takov´e, ˇze e · d ≡ 1 (mod ϕ(n)). Stanovme toto ˇc´ıslo d pˇresnˇe podle pozn´amky pod popisem algoritmu. Urˇceme nejvˇetˇs´ı spoleˇcn´ y dˇelitel ˇc´ısel 660 a 17: 660 : 17 = 38 17 : 14 = 1 14 : 3 = 4 3:2=1 2:1=2
(zb. 14), (zb. 3), (zb. 2), (zb. 1), (zb. 0).
tedy tedy tedy tedy
14 = 660 − 38 · 17 3 = 17 − 1 · 14 2 = 14 − 4 · 3 1=3−1·2
Spoˇc´ıtejme nyn´ı koeficienty v Bezoutovˇe identitˇe pro ˇc´ısla 660 a 17: 1 = 3 − 1 · 2 = 3 − 1 · (14 − 4 · 3) = 5 · 3 − 1 · 4 = 5 · (17 − 1 · 14) − 1 · 14 = 5 · 17 − 6 · 14 = 5 · 17 − 6 · (660 − 38 · 17) = −6 · 60 + 233 · 17 Alice tedy vol´ı d = 233. Jej´ı tzv. soukrom´ y kl´ıˇc tvoˇr´ı dvojice (n, s) = (713, 233). Veˇrejn´ y kl´ıˇc pak tvoˇr´ı dvojice (n, e) = (713, 17). 6. Alice odeˇsle neˇsifrovanˇe Bobovi veˇrejn´ y kl´ıˇc (n, e) = (713, 17). Bob obdrˇzel od Alice veˇrejn´ y kl´ıˇc. Nyn´ı bude cht´ıt zaˇsifrovat zpr´avu m = 12: 1. Bob spoˇc´ıt´a zbytek po dˇelen´ı ˇc´ısla me ˇc´ıslem n, tj. zbytek po dˇelen´ı ˇc´ısla 1217 ˇc´ıslem 713. K tomu m˚ uˇze vyuˇz´ıt napˇr´ıklad tzv. modul´arn´ı umocˇ nov´an´ı: 1217 = 12 · 1216 = 12 · (((122 )2 )2 )2 = 538 (mod 713). Bod tedy odeslal zaˇsifrovanou zpr´avu 538. Alice ji chce deˇsifrovat. Mus´ı tedy spoˇc´ıtat, jak´ y d´av´a zbytek 538233 po dˇelen´ı ˇc´ıslem 713. K v´ ypoˇctu vyuˇzijme nˇejak´ y matematick´ y software (napˇr´ıklad program Sage: http://www.sagemath.org/, ˇci http: //www.wolframalpha.com) a vyjde n´am skuteˇcnˇe zpr´ava m = 12. Nyn´ı si pˇredstav´ıme dalˇs´ı z ˇsifrovac´ıch algoritm˚ u, konkr´etnˇe algoritmus ElGamal. 14
ˇ Kapitola 2. Sifrovac´ ı algoritmy RSA a ElGamal
2.2
ElGamal
Algoritmus ElGamal publikoval poprv´e v roce 1984 egyptsk´ y matematik Taher ElGamal (nˇekdy t´eˇz psan´ y Elgamal). Neˇz se vˇsak s t´ımto algoritmem sezn´am´ıme, mus´ıme si uv´est trochu teorie. Definice 2.2.1. Necht’ p je prvoˇc´ıslo, a ∈ N takov´e, ˇze (p, a) = 1. Nejmenˇs´ı pˇrirozen´e ˇc´ıslo n takov´e, ˇze an ≡ 1 (mod p), naz´ yv´ame ˇra´d ˇc´ısla a modulo p. Moˇzn´a v´as napadne, proˇc v˚ ubec takov´e pˇrirozen´e ˇc´ıslo n existuje. Nemohlo by se n´ahodou st´at, ˇze pro vˇsechna pˇrirozen´a ˇc´ısla n bude platit, ˇze an 6≡ 1 (mod p)? Odpovˇed’ je snadn´a: nemohlo. Protoˇze je (a, p) = 1, je podle Mal´e Fermatovy vˇety ?? ap−1 ≡ 1 (mod p).
Pˇ r´ıklad 2.2.2. Urˇcete ˇra´dy ˇc´ısel 1, 2, 3, 4 modulo 5. ˇ sen´ı. Reˇ ˇ ad ˇc´ısla 1 je zˇrejmˇe 1, protoˇze 11 = 1. 1. R´ ˇ ad ˇc´ısla 2 je 4, protoˇze 21 , 22 ani 23 nejsou kongruentn´ı s ˇc´ıslem 1 modulo 5, ale 2. R´ podle Mal´e Fermatovy vˇety je 24 ≡ 1 (mod 5). 3. Obdobnˇe se odvod´ı, ˇze ˇra´d ˇc´ısla 3 modulo 5 je 4. ˇ ad ˇc´ısla 4 je 2, protoˇze 41 6≡ 1 (mod 5), ale 42 ≡ 1 (mod 5). 4. R´ My budeme v algoritmu ElGamal potˇrebovat pro dan´e prvoˇc´ıslo p ˇc´ıslo ˇra´du p − 1. To skuteˇcnˇe vˇzdy existuje, jak n´am ˇrekne dalˇs´ı tvrzen´ı. Bohuˇzel je vˇsak d˚ ukaz n´aroˇcn´ y, proto si ho neuvedeme, nicm´enˇe ho najdete v 1, kde se i dozv´ıte, jak takov´e ˇc´ıslo hledat. Tvrzen´ı 2.2.3. Pro kaˇzd´e prvoˇc´ıslo p existuje cel´e ˇc´ıslo a, kter´e m´a ˇr´ad p − 1 modulo p. Pojd’me si nyn´ı pˇredstavit algoritmus ElGamal. Ten jiˇz nen´ı zaloˇzen na n´aroˇcnosti rozkladu ˇc´ısla na souˇcin prvoˇc´ısel, ale na probl´emu tzv. diskr´etn´ıho logaritmu, jak si vysvˇetl´ıme pozdˇeji. Opˇet si budou pˇred´avat zpr´avu Alice a Bob. Bob bude cht´ıt opˇet Alici poslat zpr´avu m. Alice nejprve mus´ı vytvoˇrit veˇrejn´ y a soukrom´ y kl´ıˇc: 1. Alice zvol´ı prvoˇc´ıslo p a ˇc´ıslo a ˇra´du p − 1 modulo p. 2. Alice zvol´ı pˇrirozen´e ˇc´ıslo x a poˇc´ıt´a jak´ y zbytek d´av´a ax modulo p. Tento zbytek oznaˇcme b. 3. Alice odeˇsle Bobovi trojici (p, a, b). 15
ˇ Kapitola 2. Sifrovac´ ı algoritmy RSA a ElGamal
Nyn´ı jsme tedy ve stavu, kdy vˇsichni znaj´ı ˇc´ısla p, a a b. Pouze Alice vˇsak zn´a ˇc´ıslo x. ˇ Reknete si, ˇze ˇc´ıslo x m˚ uˇze nyn´ı kdokoliv urˇcit tak, ˇze bude postupnˇe umocˇ novat ˇc´ıslo a a d´ıvat se, jak´ y zbytek d´av´a v´ ysledek po dˇelen´ı ˇc´ıslem p. Takto umocˇ novat tak dlouho, dokud nedostane ˇc´ıslo b. To je opˇet ˇcasovˇe n´aroˇcn´e a v re´aln´em ˇcase neprovediteln´e. Pr´avˇe probl´em vyj´adˇrit pˇrirozen´e ˇc´ıslo x, pokud zn´ame a i zbytek po dˇelen´ı ˇc´ısla ax ˇc´ıslem p, naz´ yv´ame probl´em diskr´etn´ıho logaritmu. Bob nyn´ı bude cht´ıt zaˇsifrovat zpr´avu m. Od Alice mu doˇsla trojice (p, a, b). 1. Bob zvol´ı pˇrirozen´e ˇc´ıslo y a spoˇc´ıt´a, jak´ y zbytek d´av´a ˇc´ıslo ay po dˇelen´ı ˇc´ıslem p. Oznaˇcme toto ˇc´ıslo c1 . 2. Bob spoˇc´ıt´a, jak´ y zbytek d´av´a ˇc´ıslo m · by po dˇelen´ı ˇc´ıslem p. Tento zbytek oznaˇcme c2 . 3. Bob poˇsle Alici dvojici (c1 , c2 ) Dvojici (c1 , c2 ) si opˇet m˚ uˇze pˇreˇc´ıst kdokoliv. Aby vˇsak mohl urˇcit zpr´avu m, potˇreboval by zn´at pˇrirozen´e ˇc´ıslo y, kter´e se mu vˇsak opˇet nepodaˇr´ı zjistit. Pojd’me nyn´ı zjistit, jak´ ym zp˚ usobem bude Alice zpr´avu deˇsifrovat. 1. Alice spoˇc´ıt´a, jak´ y zbytek d´av´a ˇc´ıslo cx1 po dˇelen´ı ˇc´ıslem p. Tento zbytek oznaˇcme z. 2. Alice urˇc´ı cel´e ˇc´ıslo d takov´e, ˇze z · d ≡ 1 (mod p). 3. Alice dostane zpr´avu m tak, ˇze urˇc´ı, jak´ y zbytek d´av´a ˇc´ıslo c2 · d po dˇelen´ı ˇc´ıslem p. To, ˇze takto dostane Alice skuteˇcnˇe zpr´avu m, si samozˇrejmˇe dok´aˇzeme. Oznaˇcme α zbytek po dˇelen´ı ˇc´ısla c2 · d ˇc´ıslem p. Chceme dok´azat, ˇze α ≡ m (mod p). M´ame tedy α ≡ c2 · d (mod p). Bob dostal ˇc´ıslo c2 jako zbytek ˇc´ısla m · by po dˇelen´ı ˇc´ıslem p. Proto α ≡ (m · by ) · d (mod p). Alice dostala ˇc´ıslo b jako zbytek po dˇelen´ı ˇc´ısla ax prvoˇc´ıslem p. M´ame tak α ≡ (m · (ax )y ) · d (mod p). Upravme α ≡ m · ax·y · d (mod p) α ≡ m · (ay )x · d (mod p). ˇ ıslo ay ale d´av´a zbytek c2 po dˇelen´ı prvoˇc´ıslem p, jak to vypoˇc´ıtal Bob, proto C´ α ≡ m · cx1 · d (mod p). 16
ˇ Kapitola 2. Sifrovac´ ı algoritmy RSA a ElGamal ˇ ıslo cx d´av´a po dˇelen´ı ˇc´ıslem p zbytek z, coˇz spoˇc´ıtala Alice. C´ 1 α ≡ m · z · d (mod p). ˇ ıslo d bylo Alic´ı voleno tak, aby z · d ≡ 1 (mod p). Proto C´ α ≡ m · 1 (mod p). To jsme ale chtˇeli dostat. Takto jsme dok´azali spr´avnost algoritmu ElGamal. Opˇet si uk´aˇzeme princip algoritmu ElGamal na konkr´etn´ım pˇr´ıkladu. Pˇ r´ıklad 2.2.4. Bob chce Alici odeslat zpr´avu m = 12. Alice si zvol´ı p = 23. Urˇcete, jak Bob zaˇsifruje zpr´avu a d´ale tuto zpr´avu deˇsifrujte. ˇ sen´ı. Pojd’me postupovat pˇresnˇe tak, jak jsme si pˇredstavili algoritmus ElGamal. Reˇ 1. Alice zvol´ı ˇc´ıslo a ˇra´du 22 modulo 23. Takov´ ym ˇc´ıslem je napˇr´ıklad a = 5. 2. Alice zvol´ı pˇrirozen´e ˇc´ıslo x a poˇc´ıt´a jak´ y zbytek d´av´a 5x modulo 23. Zvolme x = 13. Potom 513 ≡ 5 · (52 )6 ≡ 5 · 256 ≡ 5 · 26 ≡ 5 · 64 ≡ 21 (mod 23). M´ame tak b = 21. 3. Alice odeˇsle Bobovi trojici (p, a, b) = (23, 5, 21). Bob obdrˇzel trojici (p, a, b) = (23, 5, 21) a bude cht´ıt zaˇsifrovat zpr´avu m = 12. 1. Bob zvol´ı pˇrirozen´e ˇc´ıslo y a spoˇc´ıt´a, jak´ y zbytek d´av´a ˇc´ıslo 5y po dˇelen´ı ˇc´ıslem 23. Zvolme y = 7. Potom 57 ≡ 5 · (52 )3 ≡ 5 · 253 ≡ 5 · 8 ≡ 17 (mod 23). M´ame tak c1 = 17. 2. Bob spoˇc´ıt´a, jak´ y zbytek d´av´a ˇc´ıslo 12 · 217 po dˇelen´ı ˇc´ıslem 23. 12 · 217 ≡ 12 · (−2)7 ≡ 5 (mod 23). M´ame tak c2 = 5. 3. Bob poˇsle Alici dvojici (c1 , c2 ) = (17, 5). Alice bude cht´ıt zpr´avu deˇsifrovat. 1. Alice spoˇc´ıt´a, jak´ y zbytek d´av´a ˇc´ıslo 1713 po dˇelen´ı ˇc´ıslem 23. 1713 ≡ 17 · (172 )6 ≡ 17 · 136 ≡ 17 · (132 )3 ≡ 17 · 83 ≡ 17 · 29 ≡ 17 · 6 ≡ 10 (mod 23). T´ımto zbytkem je z = 10. 17
ˇ Kapitola 2. Sifrovac´ ı algoritmy RSA a ElGamal
2. Alice urˇc´ı cel´e ˇc´ıslo d takov´e, ˇze 10 · d ≡ 1 (mod 23). Toto ˇc´ıslo m˚ uˇzeme opˇet urˇcit pomoc´ı Euklidova algoritmu obdobnˇe, jako jsme postupovali v RSA algoritmu. My pro n´aˇs pˇr´ıklad zvolme jin´ y postup, kter´ y je vˇsak tˇeˇzko aplikovateln´ y v obecn´em pˇr´ıkladu: 10d 10d 10d d
≡ ≡ ≡ ≡
1 (mod 23) 1 + 3 · 23 (mod 23) 70 (mod 23) 7 (mod 23).
Poloˇzme proto d = 7. 3. Alice dostane zpr´avu m tak, ˇze urˇc´ı, jak´ y zbytek d´av´a ˇc´ıslo 5 · 7 po dˇelen´ı ˇc´ıslem 23, coˇz je 12.
18
Z´avˇer
Z´ avˇ er V tomto textu jsme si uk´azali, jak n´am m˚ uˇze b´ yt uˇziteˇcn´a teorie ˇc´ısel v ˇsifrovac´ıch algoritmech. V z´avˇereˇcn´e lekci se pak jeˇstˇe pod´ıv´ame na dalˇs´ı ˇsifrovac´ı algoritmus, konkr´etnˇe na ˇsifrov´an´ı pomoc´ı eliptick´ ych kˇrivek. D´ale se pod´ıv´ame na to, jak lze vˇsechny algoritmy vyuˇz´ıt pˇri tvorbˇe digit´aln´ıho podpisu, coˇz je v dneˇsn´ı dobˇe pomˇernˇe aktu´aln´ı t´ema. Opˇet uvid´ıme, ˇze je vˇse zaloˇzeno na teorii ˇc´ısel. Teorie ˇc´ısel n´am ukazuje, jak kr´asn´a, uˇziteˇcn´a, ale z´aroveˇ n neˇcekan´a dok´aˇze b´ yt matematika. Ukazuje, ˇze i zd´anlivˇe jednoduch´ y probl´em rozkl´ad´an´ı ˇc´ısla na souˇcin prvoˇc´ısel m˚ uˇze b´ yt z´akladem ˇsifrovac´ıch algoritm˚ u, d´ıky kter´ ym m˚ uˇzeme pos´ılat informace, kter´e si dok´aˇze pˇreˇc´ıst pouze adres´at. Je to pr´avˇe teorie ˇc´ısel, kter´a n´am d´av´a ˇradu zaj´ımav´ ych probl´em˚ u, kter´e jsou snadno pochopiteln´e, avˇsak jejich ˇreˇsen´ı n´am d´av´a spoustu nov´ ych a nov´ ych poznatk˚ u. Vzpomeˇ nme zde Velkou Fermatovu vˇetu, kdy chceme naj´ıt vˇsechna nenulov´a cel´a ˇc´ısla x, y, z, kter´a budou splˇ novat rovnost xn + y n = z n . Tento lehce pochopiteln´ y probl´em formuloval v 17. stolet´ı francouzsk´ y matematik Pierre de Fermat. Aˇz teprve ned´avno, v roce 1994, dok´azal britsk´ y matematik Andrew John Wiles, ˇze tato rovnice nem´a ˇz´adn´e nenulov´e ˇreˇsen´ı pro n > 2. Na konec jeˇstˇe zmiˇ nme dva probl´emy teorie ˇc´ısel, kter´e zat´ım nikdo nevyˇreˇsil. Prvn´ı je probl´em t´ ykaj´ıc´ı se prvoˇc´ıseln´ ych dvojˇcat. Prvoˇc´ıseln´a dvojˇcata jsou dvˇe po sobˇe jdouc´ı lich´a ˇc´ısla, kter´a jsou prvoˇc´ısly (napˇr´ıklad 3 a 5, 11 a 13, 29 a 31). Doposud se vˇsak v˚ ubec nev´ı, kolik je prvoˇc´ıseln´ ych dvojˇcat, zda jich je koneˇcnˇe, ˇci nekoneˇcnˇe mnoho. Dalˇs´ım probl´emem jsou dokonal´a ˇc´ısla. Dokonal´e ˇc´ıslo je takov´e pˇrirozen´e ˇc´ıslo, kter´e je souˇctem sv´ ych kladn´ ych dˇelitel˚ u (kromˇe sebe sam´eho). Takov´ ym ˇc´ıslem je napˇr´ıklad ˇc´ıslo 6 = 1 + 2 + 3. Dalˇs´ımi ˇc´ısly jsou tˇreba 28 = 1 + 2 + 4 + 7 + 14, 496, 8128. Dosud je zn´amo 48 dokonal´ ych ˇc´ısel, pˇriˇcemˇz posledn´ı z nich bylo objeveno v u ´noru 2013. Dodnes nikdo nev´ı, zda je nekoneˇcnˇe mnoho dokonal´ ych ˇc´ısel a nikomu se zat´ım nepodaˇrilo naj´ıt lich´e dokonal´e ˇc´ıslo, ˇci dok´azat jeho neexistenci.
19
Literatura
Literatura [1] Bulant, M.: Algebra 2 — Teorie ˇc´ısel, http://is.muni.cz/el/1431/jaro2007/ M6520/um/main-print.pdf, 2007.
20
