• Nebyly nalezeny žádné výsledky

Text práce (558.6Kb)

N/A
N/A
Protected

Academic year: 2022

Podíl "Text práce (558.6Kb)"

Copied!
73
0
0

Načítání.... (zobrazit plný text nyní)

Fulltext

(1)

Univerzita Karlova v Praze Matematicko-fyzik´ aln´ı fakulta

DIPLOMOV ´ A PR ´ ACE

Martina V´ alkov´ a

Utoky zaloˇ ´ zen´ e na hardwarov´ ych chyb´ ach

Katedra algebry

Vedouc´ı diplomov´ e pr´ ace: Mgr. ˇ Stˇ ep´ an Holub, Ph.D.

Studijn´ı program: Matematika,

matematick´ e metody informaˇ cn´ı bezpeˇ cnosti

2010

(2)

Prohlaˇsuji, ˇze jsem svou diplomovou pr´aci napsala samostatnˇe a v´yhradnˇe s pouˇzit´ım citovan´ych pramen˚u. Souhlas´ım se zap˚ujˇcov´an´ım pr´ace.

V Praze dne 6. 12. 2010 Martina V´alkov´a

(3)

Obsah

1 Matematick´y z´aklad 9

1.1 Z´aklady pravdˇepodobnosti . . . 9

1.2 Element´arn´ı teorie ˇc´ısel . . . 10

1.2.1 Komutativn´ı okruhy . . . 11

1.2.2 Cyklick´e grupy . . . 13

2 V´ypoˇcet odmocnin v Zp 15 2.1 Residua a jejich odmocniny . . . 16

2.1.1 AMM algoritmus . . . 18

2.2 V´ypoˇcet qu-t´ych odmocnin . . . 21

2.3 V´ypoˇcet r-t´ych odmocnin . . . 23

2.3.1 Probl´em faktorizace . . . 25

2.4 V´ypoˇcet druh´ych odmocnin . . . 25

3 V´ychoz´ı sch´emata a v´ypoˇcetn´ı algoritmy 28 3.1 Pˇredpoklady . . . 29

3.1.1 Algoritmy pro modul´arn´ı mocnˇen´ı . . . 30

3.1.2 Posuzov´an´ı v´ypoˇcetn´ı sloˇzitosti . . . 32

3.2 Kryptografick´a sch´emata . . . 32

3.2.1 RSA . . . 32

3.2.2 Pohlig-Hellman . . . 34

4 Pravdˇepodobnostn´ı anal´yza 35 4.1 V´yskyt chybov´ych slov . . . 36

4.2 M´ıra chybovosti zaˇr´ızen´ı . . . 36

4.2.1 Vliv implementace . . . 37

4.2.2 V´ysledky . . . 39

(4)

5 Z´akladn´ı ´utoky 41

5.1 LTOR a chybov´y ´utok . . . 43

5.2 RTOL a ´utok s chybov´ym faktorem . . . 45

6 Pˇresnost ´utok˚u a eliminace vlivu n´ahodn´ych chyb 48 6.1 Anal´yza ´uspˇeˇsnosti chybov´eho ´utoku . . . 48

6.2 Anal´yza ´utoku s chybov´ym faktorem . . . 50

7 Diskuse k ´utok˚um 52 7.1 LTOR-´utoky . . . 52

7.1.1 LTOR-´utok pro odliˇsnou implementaci . . . 54

7.1.2 LTOR a chybov´y faktor . . . 55

7.2 RTOL-´utoky . . . 57

8 RSA a vliv optimalizac´ı a bezpeˇcnostn´ıch sch´emat 59 8.1 Pouˇzit´ı CRT . . . 60

8.2 Montgomeryho n´asoben´ı . . . 60

8.3 Bezpeˇcnostn´ı sch´ema OAEP . . . 63

9 Simulace a testov´an´ı 65

10 Z´avˇer 69

Literatura 73

(5)

N´azev pr´ace: ´Utoky zaloˇzen´e na hardwarov´ych chyb´ach Autor: Martina V´alkov´a

Katedra (´ustav): Katedra algebry

Vedouc´ı bakal´aˇrsk´e pr´ace: Mgr. ˇStˇep´an Holub, Ph.D.

e-mail vedouc´ıho: Stepan.Holub@mff.cuni.cz

Abstrakt: V pˇredloˇzen´e pr´aci studujeme vyuˇzit´ı hardwarov´ych v´ypoˇcetn´ıch chyb pro realizaci kryptoanalytick´ych ´utok˚u. Zamˇeˇrujeme se konkr´etnˇe na n´avrhy ´utok˚u prezentovan´ych v ˇcl´anku Biham E., Carmeli Y., Shamir A.:

Bug Attacks [1] a zkoum´ame jejich praktick´e pouˇzit´ı v˚uˇci sch´emat˚um RSA a Pohlig-Hellman, vˇcetnˇe moˇznosti rozˇs´ıˇren´ı a adaptace ´utok˚u na r˚uzn´e v´ypoˇcetn´ı okolnosti, pˇriˇcemˇz upozorˇnujeme na vyˇsˇs´ı zranitelnost sch´emat pˇri realizaci modul´arn´ıho mocnˇen´ı pouˇzit´ım algoritmu Right-to-Left. Pˇrin´aˇs´ıme v´ysledky praktick´eho testov´an´ı ´utok˚u prov´adˇen´ych v˚uˇci softwarov´e simu- laci bugov´eho procesoru, kter´e potvrzuj´ı skuteˇcnou bezpeˇcnostn´ı hrozbu uvaˇzovan´e situace. ˇCistˇe matematick´a ˇc´ast pr´ace je vˇenov´ana v´ypoˇcetn´ımu pˇredpokladu jednoho z ´utok˚u, problematice hled´an´ı odmocnin vZp.

Kl´ıˇcov´a slova: hardwarov´a chyba, ´utok, RSA, odmocniny modulop Title: Attacks based on hardware bugs

Author: Martina V´alkov´a

Department: Department of Algebra Supervisor: Mgr. ˇStˇep´an Holub, Ph.D.

Supervisor’s e-mail address: Stepan.Holub@mff.cuni.cz

Abstract: The study concerns hardware bugs producing computational errors and cryptanalytic attacks which utilize them. Particularly, the research is focused on attacks presented in the article by Biham E., Carmeli Y., Shamir A.: Bug Attacks [1] and their practical application in the case of schemes RSA and Pohlig-Hellman and various computational circumstances, which points out bigger vulnerability of schemes in the case of using the Right- to-Left modular exponentiation algorithm. The attacks have been tested against the software simulation of a faulty processor, which confirmed that they pose a real security threat in point of that situation. The mathematical part of this work concerns the problem of the finding any roots in Zp. Keywords: hardware bug, attack, RSA, roots modulo p

(6)

Uvod ´

Pr´ace se zamˇeˇruje na kryptoanalytick´e ´utoky, kter´e vyuˇz´ıvaj´ı v´ypoˇcetn´ıch chyb deˇsifrovac´ıho zaˇr´ızen´ı. Vych´az´ıme z pˇredpokladu, ˇze dan´e deˇsifrovac´ı zaˇr´ızen´ı obsahuje hardwarovou chybu (bug) v implementaci v´ypoˇcetn´ıch in- strukc´ı, kterou lze vhodn´ym v´ybˇerem ˇsifrov´ych text˚u n´aslednˇe vyuˇz´ıt pro odhalen´ı utajovan´eho (deˇsifrovac´ıho) kl´ıˇce. Souˇcasn´a asymetrick´a sch´emata uˇz´ıvan´a v kryptografii jsou postavena pˇredevˇs´ım na operaci mocnˇen´ı dlou- h´ych ˇc´ısel, tato operace je pˇritom typicky realizov´ana prostˇrednictv´ım souˇci- nu. Jej´ı ˇcast´e pouˇz´ıv´an´ı ve v´ypoˇctech se proto st´av´a vhodn´ym terˇcem ´utok˚u.

Ze stejn´eho d˚uvodu se i zde v pˇredpokladu zamˇeˇr´ıme na hardwarov´e chyby projevuj´ıc´ı se pˇri operaci n´asoben´ı (multiplication bug). Tato myˇslenka tzv.

bug-attacks, vˇcetnˇe jejich z´akladn´ıch princip˚u, vych´az´ı z ˇcl´anku [1].

Tyto bug-´utoky jsou do urˇcit´e m´ıry pˇr´ıbuzn´e s fault-attacks. Ty se sou- stˇred’uj´ı na z´amˇern´e vyvol´av´an´ı poruchy zaˇr´ızen´ı v urˇcit´em okamˇziku v´y- poˇctu s c´ılem zp˚usobit chybnost jeho v´ysledk˚u, ˇcehoˇz b´yv´a dosahov´ano pro- vozov´an´ım ˇcinnosti zaˇr´ızen´ı v urˇcit´em (neobvykl´em) prostˇred´ı, jako pˇri vy- sok´ych teplot´ach, vlivem mikrovln apod. Takto vyvolan´e poruchy jsou vˇsak na rozd´ıl od ´uˇcink˚u bugu jen pˇrechodn´e, s n´ahodn´ymi hodnotami v´ysledk˚u.

Vyˇzaduj´ı fyzick´e drˇzen´ı v´ypoˇcetn´ıho zaˇr´ızen´ı ´utoˇcn´ıkem a pro ´uspˇeˇsnost

´

utok˚u potˇrebuj´ı pˇresn´e naˇcasov´an´ı. Kromˇe toho jsou takov´e ´utoky dobˇre provediteln´e u smart-karet, ale uˇz h˚uˇre napˇr´ıklad u poˇc´ıtaˇc˚u. V´yhodou bug-

´

utok˚u je to, ˇze nevyˇzaduj´ı fyzick´y pˇr´ıstup k zaˇr´ızen´ı bˇehem prob´ıhaj´ıc´ıho v´ypoˇctu a jsou prov´adˇeny bez nutnosti manipulace s operaˇcn´ım prostˇred´ım.

Chyby zp˚usobovan´e bugem jsou deterministick´e a nast´avaj´ı vˇzdy, kdyˇz je prov´adˇen d´ılˇc´ı v´ypoˇcet. ´Utoˇcn´ık uˇz pˇri bug-´utoc´ıch neovlivˇnuje ˇcas nebo po- vahu chyby jako takov´e, vol´ı uˇz jen hodnoty vstup˚u prob´ıhaj´ıc´ıch v´ypoˇct˚u.

Smyslem pr´ace bylo teoretick´e i praktick´e ovˇeˇren´ı realizovatelnosti a ´us- pˇeˇsnosti aplikace uvaˇzovan´ych ´utok˚u, vˇcetnˇe jejich rozˇs´ıˇren´ı a adaptace na r˚uzn´a v´ypoˇcetnˇe-implementaˇcn´ı specifika.

(7)

V konkr´etn´ıch ´utoc´ıch se zamˇeˇrujeme pˇredevˇs´ım na asymetrick´y ˇsifrovac´ı syst´em RSA, kter´y patˇr´ı nepochybnˇe mezi jedno z nejrozˇs´ıˇrenˇejˇs´ıch sch´emat pouˇz´ıvan´ych v souˇcasn´e kryptografii. Pro porovn´an´ı je uvaˇzov´ano i princi- pielnˇe podobn´e, m´enˇe zn´am´e sch´ema Pohlig-Hellman, kter´e funguje v okruhu s odliˇsn´ymi vlastnostmi, teoreticky vyuˇziteln´ymi pro sn´ıˇzen´ı sloˇzitosti ´utok˚u.

Pˇredpokl´adanou metodou usnadˇnuj´ıc´ı generov´an´ı ˇsifrov´ych text˚u vhodn´ych pro ´utok je v jeho pˇr´ıpadˇe v´ypoˇcet odmocnin modulopprvoˇc´ıslo. T´eto pro- blematice se vˇenuje ˇcistˇe matematick´a ˇc´ast pr´ace - kapitola 2. J´ı pˇredch´azej´ıc´ı kapitola jen struˇcnˇe shrnuje znalost v textu pouˇz´ıvan´ych definic a fakt z te- orie ˇc´ısel v okruz´ıch a cyklick´ych grup´ach a z teorie pravdˇepodobnosti.

Popisu z´akladn´ıch uvaˇzovan´ych ˇsifrovac´ıch sch´emat a v´ychoz´ıch v´ypoˇcet- n´ıch pˇredpoklad˚u (jako je konkretizace druhu chyby v hardwarov´em zaˇr´ızen´ı ˇ

ci varianta a zp˚usob implementovan´ych v´ypoˇcetn´ıch algoritm˚u) je vˇenov´ana kapitola 3. Na z´akladˇe tˇechto specifikac´ı jsou pak samotn´e myˇslenky ´utok˚u, pˇrevzat´ych z ˇcl´anku [1], uvedeny v kapitole 5 a v n´asleduj´ıc´ıch kapitol´ach d´ale rozpracov´av´any.

Narozd´ıl od pˇredpokladu ˇcl´anku [1] se tato pr´ace zamˇeˇruje i na re´aln´y v´yskyt n´ahodn´ych chyb bˇehem v´ypoˇct˚u na chybov´em zaˇr´ızen´ı, jejichˇz exis- tence jednoznaˇcnˇe ovlivˇnuje praktickou ´uspˇeˇsnost pˇri prov´adˇen´ı ´utok˚u. Je- jich pravdˇepodobnosti vzniku se podrobnˇe vˇenuje kapitola 4, v kapitole 6 je zkoum´an vliv tˇechto chyb na uvaˇzovan´e ´utoky a jsou zde pops´any me- tody, kter´ymi lze jejich negativn´ı vliv na ´uspˇeˇsnost ´utoku do urˇcit´e m´ıry redukovat. Pro moˇznost pˇr´ım´eho pouˇzit´ı pˇrevzat´ych ´utok˚u bylo nezbytn´e prov´est ´upravy nˇekter´ych problematick´ych ˇc´ast´ı jejich princip˚u, na jejichˇz rozbor se zamˇeˇruje kapitola 7. V n´ı je souˇcasnˇe uk´az´ana moˇznost modifikace

´

utok˚u pro libovoln´y, nejen (v ˇcl´anku [1]) specificky pˇredpokl´adan´y, zp˚usob implementace uvaˇzovan´ych algoritm˚u modul´arn´ıho mocnˇen´ı (Left-to-Right, Right-to-Left). Pˇri anal´yze ´utok˚u uvid´ıme, ˇze vyhodnocov´an´ı deˇsifrovan´ych text˚u na z´akladˇe pr´ace s pˇresnou chybovou hodnotou vhodnˇe poskytuje

´

utoku v´ypoˇcetn´ı spolehlivost, proto si v t´eto kapitole rovnˇeˇz uk´aˇzeme, ˇze takov´y postup nen´ı nutn´e omezovat jen na nˇekter´y z uveden´ych algoritm˚u mocnˇen´ı.

Z praktick´eho hlediska pouˇzitelnosti ´utok˚u je tak´e nezbytn´e uvaˇzovat r˚uzn´e optimalizace a pˇr´ıdavn´a sch´emata implementovan´a souˇcasnˇe s kryp- tografick´ymi sch´ematy a posoudit moˇznost proveden´ı ´utoku i v takov´em pˇr´ıpadˇe. Tomuto aspektu, se zamˇeˇren´ım na sch´ema RSA, se vˇenuje kapi- tola 8, kde je posuzov´ana jak samotn´a moˇznost realizace ´utok˚u pˇri dan´ych optimalizac´ıch (sch´ematech), tak moˇznost potˇrebn´e modifikace p˚uvodn´ıch

(8)

n´avrh˚u ´utok˚u.

Ned´ılnou souˇc´ast´ı pr´ace bylo vedle teoretick´e ˇc´asti i praktick´e odzkouˇsen´ı veˇsker´ych ´utok˚u popsan´ych v textu. Informacemi o proveden´em testov´an´ı se zab´yv´a kapitola 9, ve kter´e je ˇcten´aˇr sezn´amen jak s d˚uleˇzit´ymi v´ysledky jednotliv´ych ´utok˚u, tak i se zp˚usobem jejich proveden´ı a dalˇs´ımi d˚uleˇzit´ymi informacemi t´ykaj´ıc´ımi se tohoto hlediska, jako je napˇr´ıklad volba modelu testovac´ıho zaˇr´ızen´ı nebo v´ybˇer testovan´ych parametr˚u.

Celkov´ym shrnut´ım se zab´yv´a z´avˇereˇcn´a kapitola, v n´ıˇz jsou mimo jin´e d´ana bezpeˇcnostn´ı doporuˇcen´ı, kter´a je vhodn´e zav´est jako urˇcitou prevenci proti realizaci ´utok˚u vyuˇz´ıvaj´ıc´ıch hardwarov´ych v´ypoˇcetn´ıch chyb, vˇcetnˇe zamˇeˇren´ı na volbu parametr˚u procesoru deˇsifrovac´ıho zaˇr´ızen´ı.

(9)

Kapitola 1

Matematick´ y z´ aklad

1.1 Z´ aklady pravdˇ epodobnosti

Pˇredpokl´ad´ame, ˇze ˇcten´aˇr ovl´ad´a z´aklady teorie pravdˇepodobnosti, a proto zde form´aln´ı definice pravdˇepodobnosti a dalˇs´ıch pojm˚u (jako n´ahodn´y jev, n´ahodn´a veliˇcina) uv´adˇet nebudeme. Pro naˇse potˇreby v´ıcem´enˇe postaˇc´ı i jen intuitivn´ı znalost tˇechto pojm˚u. Uved’me zde jen pouˇz´ıvan´e znaˇcen´ı a pˇripomeˇnme z´akladn´ı fakta, kter´a pˇri v´ypoˇctech pravdˇepodobnosti bu- deme vyuˇz´ıvat.

Pro operace s jevy budeme pouˇz´ıvat z´apisy: doplnˇek ¯A(nenastane jevA), pr˚unikA∩B (jevyA aB nast´avaj´ı souˇcasnˇe) a sjednocen´ıA∪B (nastane alespoˇn jeden z jev˚uA, B). Poˇcet jev˚u budeme pˇredpokl´adat pouze koneˇcn´y a kromˇe pouˇz´ıvan´ych z´akladn´ıch z´akon˚u jako je komutativita, asociativita a distributivita jev˚u explicitnˇe pˇripomeˇnme tzv.de Morganovy z´akony:

Tn

i=1Ai =Sn

i=1i,Sn

i=1Ai =Tn i=1i.

Pravdˇepodobnost n´ahodn´eho jevu A znaˇc´ıme jako P(A). Z´akladn´ımi vlastnostmi pravdˇepodobnosti jsou: 1≥P(A)≥0,P( ¯A) = 1−P(A).

Pro sjednocen´ı dvou jev˚u plat´ı, ˇzeP(A∪B) = P(A) +P(B)−P(A∩B).

Tento vzorec lze indukc´ı rozˇs´ıˇrit pro libovoln´y koneˇcn´y poˇcet jev˚u:

P(

n

[

i=1

Ai) =

n

X

i=1

P(Ai)−X

i <

X

j

P(Ai∩Aj)+X

i <

X

j <

X

k

P(Ai∩Aj∩Ak)−. . .+(−1)n+1P(

n

\

i=1

Ai)

(10)

Pozorov´an´ı 1.1.1. Rovnost P(Sn

i=1Ai) = Pn

i=1P(Ai) plat´ı, jen pokud jsou jevy po dvou disjunktn´ı (nesluˇciteln´e), tj. Ai ∩Aj = θ, i 6= j. Jinak P(Sn

i=1Ai)<Pn

i=1P(Ai), dle v´yˇse uveden´eho vzorce.

N´ahodn´e jevyA, B se naz´yvaj´ınez´avisl´e, kdyˇzP(A∩B) = P(A)·P(B).

N´ahodn´e jevyA1, A2, . . .se naz´yvaj´ınez´avisl´e, kdyˇz pro libovolnou nepr´azd- nou podmnoˇzinu jev˚u plat´ı P(Tk

j=1Aij) = Qk

j=1P(Aij). Lze dok´azat, ˇze doplˇnky nez´avisl´ych jev˚u jsou nez´avisl´e jevy a plat´ı tvrzen´ı:

Tvrzen´ı 1.1.2. Jsou-li A1, . . . , An nez´avisl´e n´ahodn´e jevy, pak P(

n

[

i=1

Ai) = 1−

n

Y

i=1

P( ¯Ai).

Podm´ınˇen´a pravdˇepodobnost (pravdˇepodobnost jevu A za podm´ınky, ˇze nastal jev B) je d´ana vztahem: P(A|B) =P(A∩B)/P(B), kde P(B)>0.

Prosyst´em dvou jev˚u A,A¯(tj. existuj´ı jen dva moˇzn´e jevy) plat´ı rovnosti:

P(A|B) +P( ¯A|B) = 1, P(B) = P(B|A)P(A) +P(B|A)P¯ ( ¯A).

1.2 Element´ arn´ı teorie ˇ c´ısel

Pojem dˇelitelnost budeme pouˇz´ıvat v t´eto pr´aci pouze v kontextu dˇelitelnosti v okruhu cel´ych ˇc´ısel Z. Jako a|b znaˇc´ıme, ˇze a je dˇelitelem ˇc´ısla b, a jako adivb celoˇc´ıseln´y pod´ıl pˇri dˇelen´ıa hodnotou b. Kongruence prvk˚u a a b modulo n (znaˇc´ıme a ≡b (mod n)) znamen´a, ˇze a a b d´avaj´ı stejn´y zbytek po celoˇc´ıseln´em dˇelen´ı hodnotoun, tj. pokudn|a−b. Z´apis gcd(a, b) oznaˇcuje nejvˇetˇs´ıho spoleˇcn´eho dˇelitele prvk˚ua ab, kter´y existuje pro kaˇzdou dvojici a, b∈ Z a pˇri dodrˇzov´an´ı konvence gcd(a, b)≥ 0 je jednoznaˇcnˇe urˇcen. Pro jeho v´ypoˇcet b´yv´a pouˇz´ıv´an klasick´y Eukleid˚uv algoritmus, pˇriˇcemˇz staˇc´ı uvaˇzovat v´ypoˇcet pro a, b≥0. Pokud gcd(a, b) = 1, ˇr´ık´ame, ˇze prvky a a b jsounesoudˇeln´e. V r´amci okruhu Z nav´ıc plat´ı tzv. Bezoutova rovnost (jej´ıˇz platnost b´yv´a dokazov´ana pr´avˇe z pr˚ubˇehu Eukleidova algoritmu), kter´a ˇr´ık´a, ˇze pro kaˇzdou dvojici prvk˚u a, b∈Z existuj´ı prvkyu, v ∈Z takov´e, ˇze gcd(a, b) =ua+vb. Pro pˇr´ım´y v´ypoˇcet tˇechto hodnot splˇnuj´ıc´ıch Bezoutovu rovnost se pouˇz´ıv´a obs´ahlejˇs´ı varianta algoritmu, tzv. rozˇs´ıˇren´y Eukleid˚uv algoritmus.

(11)

Algoritmus 1. Rozˇs´ıˇren´y Eukleid˚uv algoritmus 1 VSTUP: a, bnez´aporn´a cel´a ˇc´ısla, a > b

V ´YSTUP: gcd(a, b) a cel´a ˇc´ısla u, v splˇnuj´ıc´ıua+vb= gcd(a, b) 1. (a1, u1, v1)←(a,1,0)

(a2, u2, v2)←(b,0,1) 2. i←2

3. Whileai 6= 0 do: /gcd(ai−1, ai) = gcd(ai, ai−1modai)/

i←i+ 1

ai ←ai−2 (mod ai−1)

ui ←ui−2−(ai−2divai−1)ui−1 /ai =uia+vib/

vi ←vi−2−(ai−2divai−1)vi−1

4. Return(ai−1, ui−1, vi−1) /gcd(ai−1,0) =ai−1/

1.2.1 Komutativn´ı okruhy

Kryptografick´a sch´emata, kter´ym se budeme v pr´aci vˇenovat, funguj´ı v ko- neˇcn´ych komutativn´ıch okruz´ıch (s jednotkou) (Zn,+,−,·,0,1), kde Zn = {0, . . . , n−1}a operace ch´apeme modulon. Pˇripomeˇnme si nˇekter´a z´akladn´ı fakta, kter´a v tˇechto struktur´ach plat´ı.

Invertibiln´ım prvkem v okruhu R je takov´y prvek a, pro kter´y existuje prvek b splˇnuj´ıc´ı rovnost a ·b = 1. Tuto (jednoznaˇcnˇe urˇcenou) hodnotu inverzn´ıho prvku obecnˇe znaˇc´ıme jako a−1. Je-li R komutativn´ı okruh s jed- notkou, pak (R,·,−1,1) je abelovsk´a grupa, kde R pˇredstavuje mnoˇzinu vˇsech invertibiln´ıch prvk˚u okruhu R. Jedn´a se o tzv. multiplikativn´ı grupu invertibiln´ıch prvk˚u okruhuR.

Eulerova funkce je definov´ana jako poˇcet ˇc´ısel z mnoˇziny {1, . . . , n−1}

nesoudˇeln´ych s ˇc´ıslemn. Pokud jen =pe11pe22. . . pekk prvoˇc´ıseln´y rozklad ˇc´ısla n, pak lze hodnotu Eulerovy funkce pron vypoˇc´ıtat jako

ϕ(n) =pe11−1pe22−1. . . pekk−1·(p1−1)(p2−1). . .(pk−1).

Speci´alnˇe, pokud je p prvoˇc´ıslo, pak ϕ(p) =p−1.

1Z d˚uvodu vˇetˇs´ı pˇrehlednosti algoritmu jsou promˇenn´e indexov´any podle jednotliv´ych krok˚u cyklu, poznamenejme vˇsak, ˇze pˇri implementaci postaˇc´ı pro v´ypoˇcet hodnot s in- dexemiuchov´avat v pamˇeti pouze v´ysledky s indexyi1 ai2.

(12)

Tvrzen´ı 1.2.1. Bud’ n ≥2 a n > a >0. Pak je ekvivalentn´ı:

gcd(a, n) = 1, a je invertibiln´ı prvek v okruhu Zn.

Tedy Zn = {0 < k < n : gcd(n, k) = 1} a speci´alnˇe Zp = Zp − {0}

pro pprvoˇc´ıslo. Nav´ıc lze d´ıky platnosti tohoto tvrzen´ı k v´ypoˇctu inverzn´ıch prvk˚u vhodnˇe vyuˇz´ıt rozˇs´ıˇren´y Eukleid˚uv algoritmus, a to dle n´asleduj´ıc´ıho pozorov´an´ı.

Pozorov´an´ı 1.2.2. Mˇejme prveka ∈Zn. Pakgcd(a, n) = 1a dle Bezoutovy rovnosti existuj´ı u, v ∈ Z takov´a, ˇze plat´ı ua+vn = 1. Odtud dost´av´ame hodnotu inverzn´ıho prvku a−1 ≡u (mod n).

Eulerova vˇetaˇr´ık´a, ˇze pokud a ∈ Zn, pak aϕ(n) = 1. Jako d˚usledek pak plat´ı, ˇze pokud r ≡ s (mod ϕ(n)), pak ar =as, tj. exponent lze redukovat modulo ϕ(n). Speci´aln´ı pˇr´ıpad Eulerovy vˇety pro prvoˇc´ıslo p(ϕ(p) = p−1) se naz´yv´aMal´a Fermatova vˇeta.

Klasick´a C´ınsk´ˇ a vˇeta o zbytc´ıch (ˇcasto oznaˇcovan´a anglickou zkratkou CRT) ˇr´ık´a, ˇze pro n = n1·. . .·nk, kde n1, . . . , nk jsou po dvou nesoudˇeln´a pˇrirozen´a ˇc´ısla, a pro libovoln´a cel´a ˇc´ısla u1, . . . , uk existuje pr´avˇe jedno x∈ {0, . . . , n−1}, kter´e ˇreˇs´ı soustavu kongruenc´ı

x≡u1 (mod n1), . . . , x ≡uk (mod nk).

V n´asleduj´ıc´ı kapitole se budeme vˇenovat problematice existence a hled´an´ı ˇreˇsen´ı rovnic typuxr =a. Pro okruhZn, kdenje sloˇzen´e ˇc´ıslo s prvoˇc´ıseln´ym rozkladem n = pe11pe22. . . pekk, lze d´ıky platnosti CRT redukovat v´ypoˇcty na okruhy Zpeii urˇcen´e ˇciniteli rozkladu ˇc´ısla n, a pot´e jen zkombinovat d´ılˇc´ı v´ysledky do koneˇcn´eho ˇreˇsen´ı. A protoˇze v t´eto pr´aci budeme vzhledem k v´ybˇeru kryptografick´ych sch´emat explicitnˇe pracovat jen v okruz´ıch Zp

pro p lich´e prvoˇc´ıslo a Zn, kde n = pq je souˇcinem dvou lich´ych prvoˇc´ısel, omezme se na ˇreˇsen´ı tˇechto rovnic pouze vZp. Nav´ıc, d´ıky tomu, ˇze vZp pro kaˇzdou dvojici prvk˚u a, b6= 0 plat´ı, ˇze a·b 6= 0, m˚uˇzeme vypustit trivi´aln´ı pˇr´ıpad a = 0, a tedy pro a 6= 0 ˇreˇsit rovnici ekvivalentnˇe v mutliplikativn´ı grupˇe Zp, o kter´e nav´ıc plat´ı, ˇze je cyklick´a.

Jen poznamenejme, ˇze Zn obecnˇe cyklickou grupou b´yt nemus´ı. Plat´ı dokonce, ˇze Zn je cyklick´a pr´avˇe tehdy, kdyˇz n = 2,4, pe,2pe, kde e ≥ 1 a pje lich´e prvoˇc´ıslo. Platnost teorie o odmocnin´ach tak lze rozˇs´ıˇrit na tyto cyklick´e grupy, avˇsak nikoliv obecnˇe pro Zn, kden je libovoln´e sloˇzen´e ˇc´ıslo.

Nˇekter´e v´ychoz´ı definice a z´akladn´ı fakta, kter´a plat´ı v cyklick´ych grup´ach, zmiˇnme v n´asleduj´ıc´ı ˇc´asti.

(13)

1.2.2 Cyklick´ e grupy

Pojmem grupa mˇejme na mysli abelovskou (komutativn´ı) grupu. Grupa H je podgrupou grupy G pr´avˇe tehdy, kdyˇz H ⊆ G a je uzavˇren´a na vˇsechny operace (tj. v´ysledek operace je opˇet prvkem H). R´ˇad grupy je definov´an jako poˇcet prvk˚u grupy,ˇr´ad prvku jako ˇr´ad podgrupy, kterou generuje. To, ˇ

zeageneruje grupuH, oznaˇcujeme jakohai=H. Pokud je grupa generov´ana jedn´ım prvkem, tzv. gener´atorem, naz´yv´ame takovou grupu cyklickou.

Tvrzen´ı 1.2.3. Bud’ n ≥ 2 a n > a > 0. Pak A je netrivi´aln´ı podgrupa grupy (Zn,+,−,0)pr´avˇe tehdy, kdyˇz A={0, d,2d, . . . ,(k−1)d} pro nˇejak´e d|n, kde 1≤d < n a n =dk.

D˚ukaz. Bud’ A netrivi´aln´ı podgrupa Zn. Zvolme nejmenˇs´ıa ∈ A, a > 0, a bud’ m nejmenˇs´ı n´asobek (tj. souˇcet k sˇc´ıtanc˚u prvku a) takov´y, ˇze plat´ı n ≤ m = k·a. Pokud m 6= n, pak 0 < m−n < a. Protoˇze m −n ∈ A, dost´av´ame spor s volbou a. Proto plat´ı, ˇze m = n, tedy a|n, n = ak.

Pak a generuje k-prvkovou grupu hai = {0, a, . . . ,(k − 1)a}, hai ⊆ A.

Pˇredpokl´adejme, ˇze existuje b ∈ A, kter´e neleˇz´ı v hai. V takov´em pˇr´ıpadˇe a6 |b, a tedy existuje i takov´e, ˇze ai < b < a(i+ 1). Pak b−ai∈A a pˇritom 0 < b −ai < a, coˇz je opˇet spor. Odtud hai = A. Opaˇcn´a implikace je zˇrejm´a.

Lze uk´azat, ˇze kaˇzd´a koneˇcn´a cyklick´a grupa ˇr´adu n je izomorfn´ı (cyk- lick´e) grupˇe (Zn,+,−,0). D´ıky tomu dost´av´ame n´asleduj´ıc´ı tvrzen´ı.

D˚usledek 1.2.4. Je-li Gcyklick´a grupa ˇr´adun, pak obsahuje podgrupu ˇr´adu dpr´avˇe tehdy, kdyˇz d|n. A pokudd|n, pak existuje pr´avˇe jedna podgrupa ˇr´adu d (tj. o d prvc´ıch) a je cyklick´a.

T´ım jsme z´aroveˇn dok´azali speci´aln´ı pˇr´ıpad (pro cyklick´e grupy) obecnˇe platn´e Lagrangeovy vˇety, kter´a ˇr´ık´a, ˇze je-li H podgrupa koneˇcn´e grupy G, pak ˇr´ad grupy H dˇel´ı ˇr´ad G, specielnˇe tedy ˇr´ad kaˇzd´eho prvku dˇel´ı velikost cel´e grupy. O gener´atorech grup plat´ı n´asleduj´ıc´ı.

Tvrzen´ı 1.2.5. Bud’ n ≥2 a n > a >0. Pak je ekvivalentn´ı:

gcd(a, n) = 1, a je gener´ator cyklick´e grupy Zn.

Jako d˚usledek tohoto tvrzen´ı plat´ı, ˇze cyklick´a grupa ˇr´adu n m´a pr´avˇe ϕ(n) gener´ator˚u a tedy rovnˇeˇz pro kaˇzd´e d|n obsahuje ϕ(d) prvk˚u ˇr´adu d.

M´enˇe zn´am´ym d˚usledkem dan´eho tvrzen´ı je rovnost:

(14)

D˚usledek 1.2.6. n=P

d|nϕ(d)

D˚ukaz. Kaˇzd´y prvek grupy, kter´a je ˇr´adu n, generuje nˇekterou z jej´ıch pod- grup. Z toho vypl´yv´a, ˇze poˇcetn prvk˚u grupy odpov´ıd´a souˇctu mnoˇzstv´ı ge- ner´ator˚u pˇres vˇsechny podgrupy. Kaˇzd´a podgrupa ˇr´adudm´a podle d˚usledku pˇredchoz´ıho tvrzen´ı pr´avˇe ϕ(d) gener´ator˚u, pˇriˇcemˇz d|n podle D˚usledku 1.2.4. Tedy n=P

d|nϕ(d).

Uvaˇzujme nad´ale cyklickou grupu v multiplikativn´ı notaci (G,·,−1,1).

R´ˇad grupy pak m˚uˇzeme ekvivalentnˇe definovat jako nejmenˇs´ı kladn´e r ta- kov´e, ˇze ar = 1 pro libovoln´y prvek grupy, a ˇr´ad prvku a jako nejmenˇs´ı kladn´e n takov´e, ˇze an = 1. Gener´ator α cyklick´e grupy ˇr´adu n pak nˇekdy naz´yv´ame n-tou primitivn´ı odmocninou z 1, nebot’ αn = 1 a αm 6= 1 pro vˇsechna 0< m < n.

Definice 1. Bud’ G koneˇcn´a cyklick´a grupa ˇr´adu n. Mˇejme α gener´ator grupy G a libovoln´y prvek a ∈ G. Jako diskr´etn´ı logaritmus prvku a pˇri z´akladˇe α naz´yv´ame jednoznaˇcnˇe urˇcen´e cel´e ˇc´ıslo x, 0≤x≤n−1, takov´e, ˇ

ze a=αx, tj.x= logαa.

Uloha nalezen´ı takov´´ ehox pˇri dan´ychG,α, aje zn´ama jako (zobecnˇen´y) probl´em diskr´etn´ıho logaritmu, o kter´em se pˇredpokl´ad´a, ˇze jetˇeˇzk´y, tj. nen´ı zn´am zp˚usob, jak jej algoritmicky ˇreˇsit v tzv. polynomi´aln´ım ˇcase alespoˇn pro nezanedbatelnou ˇc´ast vˇsech moˇzn´ych vstup˚u, jsou-li parametry pro- bl´emu peˇclivˇe vyb´ır´any s ohledem na znalost jeho snadno-ˇreˇsiteln´ych in- stanc´ı. Existuje v´ıce v´ypoˇcetn´ıch probl´em˚u, kter´e jsou obecnˇe povaˇzov´any zatˇeˇzk´e.2D˚ukazy pro to zn´amy nejsou, ale nev´ı se o efektivn´ıch algoritmech, kter´e by v obecn´em pˇr´ıpadˇe dok´azaly dan´etˇeˇzk´e ulohy ˇreˇsit v re´´ aln´em ˇcase.

Snaha o jejich vyˇreˇsen´ı v konkr´etn´ıch pˇr´ıpadech pak ˇcasto b´yv´a realizov´ana v´ypoˇctem hrubou silou, tj. snahou odzkouˇsen´ı vˇsech moˇznost´ı.

Lemma 1.2.7. Je-li a prvek ˇr´adu n, pak as je ˇr´adu n/gcd(s, n).

D˚ukaz. Mˇejme prvek a ˇr´adu n, tj. an= 1. ˇR´ad prvku as odpov´ıd´a nejmen- ˇs´ımu x takov´emu, ˇze (as)x = 1, a podle ˇr´adu prvku a mus´ı platit, ˇze n dˇel´ı sx. A protoˇze x je nejmenˇs´ı moˇzn´e, odpov´ıd´a sx nejmenˇs´ımu spoleˇcn´emu n´asobku ˇc´ısel s, n. Rozmysleme si, ˇze je-licnejmenˇs´ım spoleˇcn´ym n´asobkem prvk˚u e a f, plat´ı, ˇze c·gcd(e, f) =e·f. Odtud sx·gcd(s, n) =s·n, tedy x= gcd(s,n)n .

2Pro podrobnˇejˇs´ı studium doporuˇcujeme literaturu [5].

(15)

Kapitola 2

V´ ypoˇ cet odmocnin v Z p

V t´eto kapitole se budeme vˇenovat ˇreˇsitelnosti a hled´an´ı ˇreˇsen´ı rovnic typu xr =av Zp, kde oznaˇcen´ım pmˇejme jednotnˇe v cel´e kapitole na mysli lich´e prvoˇc´ıslo. Uvaˇzujme pˇritom jen kladn´er < p−1, nebot’ v opaˇcn´em pˇr´ıpadˇe lze exponent vˇzdy redukovat moduloϕ(p) =p−1 dle Mal´e Fermatovy vˇety se zachov´an´ım shodn´eho ˇreˇsen´ı rovnice. Pˇripomeˇnme, ˇze multiplikativn´ı grupa Zp je cyklick´a vzhledem k n´asoben´ı modulo pa je ˇr´adu p−1.

Kapitola je rozdˇelena do ˇctyˇr hlavn´ıch ˇc´ast´ı. V prvn´ı ˇc´asti jsou pˇredloˇzena a dok´az´ana z´akladn´ı tvrzen´ı o existenci a vlastnostech r-t´ych residu´ı v Zp

a pops´ana idea rozloˇzen´ı probl´emu v´ypoˇctu jejich r-t´e odmocniny pˇri libo- voln´emrna d´ılˇc´ı v´ypoˇcty prvoˇc´ıseln´ych odmocnin. D´ale zde struˇcnˇe diskutu- jeme probl´em aplikace zn´am´ych algoritm˚u pro v´ypoˇcet odmocnin z hlediska pouˇzitelnosti pˇri velk´ych exponentech a jako nejvhodnˇejˇs´ı je zvolen a pops´an tzv. AMM algoritmus, u nˇehoˇz uv´ad´ıme i jeho odvozen´ı.

Druh´a ˇc´ast rozeb´ır´a problematiku v´ypoˇctu qu-t´ych odmocnin metodou rekurzivnˇe poˇc´ıtan´ych prvoˇc´ıseln´ychq-t´ych odmocnin, pro jej´ıˇz diskusi je zde definov´an pojem rekurzivn´ı posloupnosti q-t´ych odmocnin a ˇreˇsena jej´ı exis- tence vZpna z´akladˇe modelu datov´e strukturystromu. Pro obt´ıˇznˇejˇs´ı pˇr´ıpad qu6 |p−1 uv´ad´ıme alternativn´ı deterministick´y zp˚usob pˇr´ım´eho v´ypoˇctu.

V n´asleduj´ıc´ıˇc´asti pak dokazujeme korektnost rozloˇzen´ı probl´emu hled´an´ı r-t´ych odmocnin na v´ypoˇcty odmocnin prvoˇc´ıseln´ych, resp. dokazujeme ˇre- ˇsitelnost d´ılˇc´ıch rovnic. Nakonec se jeˇstˇe kr´atce zm´ın´ıme o probl´emu fakto- rizace, kter´y s pˇredpokl´adan´ymi postupy v´ypoˇct˚u odmocnin souvis´ı.

Speci´aln´ımu pˇr´ıpadu druh´ych odmocnin se struˇcnˇe vˇenuje z´avˇer kapitoly.

Na z´akladˇe odvozen´ych vlastnost´ı kvadratick´ych residu´ı jsou podrobnˇeji ana-

(16)

lyzov´any moˇznosti v´ypoˇct˚u druh´ych (a 2u-t´ych) odmocnin a uv´ad´ıme alter- nativn´ı postup pro tˇr´ıdu prvoˇc´ısel p≡3 (mod 4) (a p≡5 (mod 8)).

2.1 Residua a jejich odmocniny

Definice 2. Prvek a ∈ Zp naz´yv´ame r-t´e residuum (modulo p), pokud m´a rovnice xr = a ˇreˇsen´ı. V opaˇcn´em pˇr´ıpadˇe a naz´yv´ame r-t´e neresiduum.

Speci´alnˇe pro r= 2 hovoˇr´ıme o tzv. kvadratick´ych (ne)residu´ıch.

Reˇsen´ı rovniceˇ xr =anaz´yv´amer-tou odmocninouprvkuaa oznaˇcujeme jej obecnˇe jako a1/r.

Tvrzen´ı 2.1.1. Bud’G cyklick´a grupa ˇr´adu n a necht’gcd(r, n) = 1. Mˇejme libovoln´e a ∈ G. Pak m´a rovnice xr = a v dan´e grupˇe pr´avˇe jedno ˇreˇsen´ı, a to prvek ae, kde re≡1 (mod n).

Konkr´etnˇe, pokud gcd(r, p−1) = 1, pak kaˇzd´y prvek a ∈ Zp je r-t´ym residuem a m´a pr´avˇe jednu r-tou odmocninu.

D˚ukaz. Prvekrje invertibiln´ı d´ıky pˇredpokladu nesoudˇelnosti s ˇr´adem grupy, tj. re≡ 1 (mod n) pro urˇcit´e e. Mˇejme prvek b takov´y, ˇze splˇnuje rovnost a=br. ´Upravou t´eto rovnosti dost´av´ameae = (br)e=b, existuje tedy pr´avˇe jedno ˇreˇsen´ı rovnice, a to hodnotyae, (ae)r=a.

Tvrzen´ı 2.1.2. Mˇejme cyklickou grupu Gˇr´adu n a kladn´e cel´e ˇc´ıslo r 6= 1 takov´e, ˇzer|n. Je-li rovnicexr =apro dan´ea ∈Gˇreˇsiteln´a, pak existuje cel- kem rr˚uzn´ych ˇreˇsen´ı. Nav´ıc, je-liα primitivn´ır-t´a odmocnina z1ab nˇejak´e ˇreˇsen´ı dan´e rovnice, pak vˇsechna ˇreˇsen´ı lze vyj´adˇrit jako {b, bα, . . . , bαr−1}, speci´alnˇe pro r = 2 jsou ˇreˇsen´ı{b,−b}.

Konkr´etnˇe, pokud r|p−1, pak kaˇzd´e r-t´e residuum a ∈Zp m´a r r˚uzn´ych r-t´ych odmocnin.

D˚ukaz. Mˇejme nˇejak´e ˇreˇsen´ı b rovnice xr = a a prvek α, kter´y je r-tou primitivn´ı odmocninu z 1. Poznamenejme, ˇze existence takov´eho prvku α v grupˇe vypl´yv´a z pˇredpokladu, ˇze r|n. Je zˇrejm´e, ˇze (bαi)r = brr)i = a pro vˇsechna 1≤ i≤r, pˇriˇcemˇz bαi ∈ G. Dokaˇzme, ˇze ˇreˇsen´ı jsou vz´ajemnˇe r˚uzn´a.

Pro spor naopak pˇredpokl´adejme, ˇze existuj´ı 1 ≤ i < j ≤ r takov´a, ˇze bαj =bαi, tj. z vlastnosti kr´acen´ı v grupˇe, ˇze αj = αi. Pak plat´ıαjαr−i = αiαr−ir = 1. Dost´av´ame 1 = αrαj−ij−i, 0< j −i < r, coˇz je spor.

Tedy bαi 6=bαj pro vˇsechna i6= j. Kaˇzd´e ˇreˇsen´ı rovnice xr = a je koˇrenem

(17)

polynomuxr−a, pˇriˇcemˇz polynom stupnˇer m´a nejv´yˇse rkoˇren˚u, tj. nalezli jsme vˇsechna ˇreˇsen´ı dan´e rovnice. Pro r= 2 je α =−1.

D˚usledkem tvrzen´ı tak je, ˇze pokudr|p−1 a ajer-t´e residuum, n´ahodnˇe zvolen´y prvek ze Zp bude r-tou odmocninou a s pravdˇepodobnost´ı p−1r .

Dokaˇzme nyn´ı formuli, podle n´ıˇz lze o libovoln´em prvku ze Zp rozhod- nout, zda je r-t´ym residuem (pro libovoln´e 1< r < p−1).

Tvrzen´ı 2.1.3. Prvek a ∈ Zp je r-t´e residuum pr´avˇe tehdy, kdyˇz plat´ı ap−1δ = 1, kde δ = gcd(r, p−1). To je nav´ıc ekvivalentn´ı s t´ım, ˇze m´ame-li α gener´ator Zp, pak a=αi pro nˇejak´e i takov´e, ˇze δ|i.

D˚ukaz. Pokud δ = gcd(r, p−1) = 1, pak kaˇzd´e a ∈ Zp je r-t´e residuum podle Tvrzen´ı 2.1.1, pˇriˇcemˇz rovnost ap−1 = 1 plat´ı vˇzdy. Pˇredpokl´adejme proto d´ale δ6= 1.

Necht’ a je r-t´e residuum, tj. existuje b takov´e, ˇze a = br. Protoˇze δ|r, dost´av´ame ap−1δ = (br)p−1δ =brδ(p−1) = (bp−1)rδ = 1.

Naopak pˇredpokl´adejme, ˇze plat´ıap−1δ = 1. Bud’ α gener´ator Zp, pak lze prvekavyj´adˇrit jakoa=αipro nˇejak´ei. ˇR´ad prvkuaje pak podle Lemmatu 1.2.7 hodnoty gcd(i,p−1)p−1 a z´aroveˇn podle pˇredpokl´adan´e rovnosti dˇel´ı p−1δ . Odtud dost´av´ame, ˇze δ nutnˇe dˇel´ı gcd(i, p− 1), a tedy δ|i. Pˇripomeˇnme, ˇ

ze δ = gcd(r, p−1), a proto z platnosti Bezoutovy rovnosti dost´av´ame, ˇze existuje e takov´e, ˇzere≡δ (mod p−1). Pak (αeδi)rδδii =a.

Pozorov´an´ı 2.1.4. Necht’ a∈Zp je r-t´e residuum a dnˇejak´y dˇelitel ˇc´ıslar, pak a je rovnˇeˇz d-t´e residuum.

Nakonec odvod’me, kolikr-t´ych residu´ı pˇri dan´emrvZp vlastnˇe existuje.

Tvrzen´ı 2.1.5. Poˇcet r-t´ych residu´ı v Zp je p−1δ , kde δ= gcd(r, p−1).

D˚ukaz. Bud’d= p−1δ , kdeδ = gcd(r, p−1). Podle Tvrzen´ı 2.1.3 jsour-t´a resi- dua pr´avˇe vˇsechny prvky splˇnuj´ıc´ı rovnostxd = 1. Tu splˇnuj´ı vˇsechny prvky d-t´eho ˇr´adu a ˇr´ad˚u d0 dˇel´ıc´ıch d. Poznamenejme, ˇze d|p−1 a pˇredpoklad prvk˚u takov´ych ˇr´ad˚u je tedy v souladu s Lagrangeovou vˇetou korektn´ı.

Pˇriˇcemˇz prvk˚u dan´eho ˇr´adu d0 je podle d˚usledku Tvrzen´ı 1.2.5 pr´avˇe ϕ(d0) a podle D˚usledku 1.2.6 t´ehoˇz tvrzen´ı plat´ı, ˇzeP

d0|dϕ(d0) =d.

D˚usledek 2.1.6. N´ahodnˇe zvolen´y prveka ∈Zp jer-t´ym residuem s pravdˇe- podobnost´ı 1δ.

(18)

V pˇr´ıpadˇe, ˇze gcd(r, p − 1) = 1, lze hodnotu r-t´e odmocniny prvku vypoˇc´ıtat dle Tvrzen´ı 2.1.1. Je vˇsak ot´azkou, jak vypoˇc´ıtat r-t´e odmocniny prvku pro libovoln´er.

Pˇredpokl´adejme, ˇze um´ıme vypoˇc´ıtat libovolnou prvoˇc´ıselnou q-tou od- mocninu prvku takovou, ˇzeq|p−1, a necht’δ= gcd(r, p−1) m´a prvoˇc´ıseln´y rozklad δ = q1v1. . . qkvk, kde vi ≥ 1 pro vˇsechna 1 ≤ i ≤ k. Pak ˇc´ıslo r lze vyj´adˇrit jako r =q1u1. . . qkukt, kde t je takov´a hodnota, ˇze gcd(qi, t) = 1 pro vˇsechna 1≤i≤k, a plat´ı, ˇze ui ≥vi a gcd(t, p−1) = 1.

V´ypoˇcetr-t´e odmocniny lze pak rozloˇzit na ˇreˇsen´ı soustavy rovnic s expo- nenty urˇcen´ymi d´ılˇc´ımi ˇciniteli uveden´eho rozkladu ˇc´ısla r, tj. potˇrebujeme postupnˇe nal´ezt ˇreˇsen´ı rovnic xt0 = a, xq

u1 1

1 = x0, . . . , xq

uk k

k = xk−1. Pak xrk =a. Prvn´ı rovnici lze d´ıky nesoudˇelnosti tsp−1 ˇreˇsit metodou mocnˇen´ı dle Tvrzen´ı 2.1.1. Ostatn´ı lze zˇrejmˇe ˇreˇsit jako vˇzdyui-kr´at rekurzivnˇe opa- kovan´y v´ypoˇcet qi-t´ych odmocnin, nebot’ xqu = (xqu−1)q =a (podrobnˇeji se moˇznost´ı tohoto postupu budeme zab´yvat v ˇc´asti 2.2). Z uveden´eho principu vid´ıme, ˇze pro nalezen´ı libovoln´er-t´e odmocniny je postaˇcuj´ıc´ı m´ıt speci´aln´ı algoritmus na v´ypoˇcet prvoˇc´ıseln´ych q-t´ych odmocnin pro pˇr´ıpady q|p−1.

Takov´y algoritmus odvod´ıme v n´asleduj´ıc´ı ˇc´asti, v dalˇs´ıch bude disku- tov´an podrobnˇeji zp˚usob v´ypoˇctuqu-t´ych odmocnin v z´avislosti na hodnotˇe ua pot´e dok´az´ana ˇreˇsitelnost d´ılˇc´ıch kongruenc´ı ve v´yˇse popsan´em postupu.

Protoˇze ˇreˇsen´ı rovnicexr =aje koˇrenem polynomuxr−a a kaˇzd´y prvek a∈Zp je koˇrenem polynomu xp−x, jinou metodou testov´an´ı, zda m´a dan´a rovnice ˇreˇsen´ı, m˚uˇze b´yt zkoum´an´ı (ne)soudˇelnosti polynomu xr−as poly- nomem xp −x v Zp[x]. Polynom xr −a nesoudˇeln´y s xp −x nem´a ˇz´adn´y koˇren ze Zp, naopak pˇr´ıpadn´e existuj´ıc´ı koˇreny polynomu xr−a, tedy r-t´e odmocniny prvku a, lze zjistit faktorizac´ı polynomu gcd(xp −x, xr−a) na line´arn´ı ˇcinitele. Tento postup je zvolen v pˇr´ıpadˇe verze algoritmu Tonelli- Shanks [4]. Metoda hled´an´ı odmocnin na z´akladˇe pr´ace s polynomy je vˇsak pˇri velk´ych hodnot´ach exponent˚up,r v obecn´em pˇr´ıpadˇe nevyuˇziteln´a, a to z d˚uvodu pˇr´ıliˇs velk´e v´ypoˇcetn´ı sloˇzitosti.

2.1.1 AMM algoritmus

Pro v´ypoˇcet q-t´ych odmocnin v Zp, kde q|p−1, zde uvedeme algoritmus navrˇzen´y v ˇcl´anku [2] autory Adleman-Manders-Miller (d´ale v textu budeme algoritmus oznaˇcovat jako AMM alg.). Pˇresnou podobu algoritmu popiˇsme pro q > 2. Pro jednoduˇsˇs´ı pˇr´ıpad q = 2 zmiˇnme jen nutn´e ´upravy, kter´e je

(19)

tˇreba v r´amci algoritmu prov´est, jeho konkr´etn´ı podobu lze nal´ezt v uve- den´em ˇcl´anku.

AMM algoritmus vych´az´ı z n´asleduj´ıc´ıch dvou pomocn´ych tvrzen´ı. V je- jich popisu pracujme s lich´ymi prvoˇc´ısly p,q takov´ymi, ˇzeq|p−1. Hodnota v ≥1 necht’ je nejvˇetˇs´ı cel´e ˇc´ıslo takov´e, ˇzeqv|p−1 (v odpov´ıd´a definici tzv.

valuace). Pak

p−1 =qv(qm+m0) (∗)

pro nˇejak´a cel´a ˇc´ısla m, m0, q > m0 ≥1. Nav´ıc zˇrejmˇe gcd(q, qm+m0) = 1.

Lemma 2.1.7. Bud’ p−1 = qv(qm+m0) s vlastnostmi dle (∗) a mˇejme h=q−1 (mod qm+m0). Pokud aqm+m0 = 1, pak ah je q-tou odmocninou a.

D˚ukaz. Prvekaleˇz´ı v podgrupˇe ˇr´aduqm+m0. Protoˇze gcd(q, qm+m0) = 1, plyne zbytek z Tvrzen´ı 2.1.1.

Lemma 2.1.8. Bud’ p−1 = qv(qm+m0) s vlastnostmi dle (∗) a necht’ g je q-t´e neresiduum. Mˇejme a∈Zp takov´e, ˇze plat´ıaqj(qm+m0) = 1 pro nˇejak´e 1 ≤ j < v a j bud’ nejmenˇs´ı takov´e moˇzn´e. Pak pro nˇejak´e cel´e ˇc´ıslo λ, 0< λ < q, plat´ı

(agqv−jλ)qj−1(qm+m0)= 1.

D˚ukaz. Pro zjednoduˇsen´ı z´apisu poloˇzme ¯a = aqj−1(qm+m0). Hled´ame ˇreˇsen´ı λ rovnosti aqj−1(qm+m0) ·gqv−1λ(qm+m0) = 1, tj. vyj´adˇren´ı inverzn´ıho prvku (¯a)−1 (mod p) jako specifickou mocninu prvku ¯g = gqv−1(qm+m0) = g(p−1)/q. Dokaˇzme existenci takov´eho ˇreˇsen´ı.

Prvek g je dle pˇredpokladu q-t´e neresiduum, pˇriˇcemˇz gcd(q, p−1) = q, tud´ıˇz podle Tvrzen´ı 2.1.3 plat´ı, ˇze gp−1q 6= 1. Protoˇze (gp−1q )q = gp−1 = 1, ˇr´ad prvku ¯g 6= 1 dˇel´ı prvoˇc´ıslo q, tud´ıˇz ¯g je ˇr´adu q. Dosazen´ım lze snadno ovˇeˇrit, ˇze (¯a)−1 = ¯a(q−1) a ¯a(q−1)q= 1, tud´ıˇz analogicky jako v pˇr´ıpadˇe prvku

¯

g lze odvodit, ˇze prvek (¯a)−1 6= 1 je rovnˇeˇz ˇr´adu q. Oba prvky ¯g, (¯a)−1 jsou tak gener´atorem q-prvkov´e podgrupy, pˇripomeˇnme, ˇze jedineˇcn´e v Zp (viz.

D˚usledek 1.2.4), existuje tedy nˇejak´e kladn´eλ < qtakov´e, ˇze (¯a)−1 = ¯gλ. Lemma 2.1.8 tak ukazuje moˇznost, jak pomoc´ı libovoln´eho q-t´eho ne- residua odvodit z prvku a prvek leˇz´ıc´ı v podgrupˇe, jej´ıˇz ˇr´ad je alespoˇn o q-n´asobek niˇzˇs´ı neˇz je ˇr´ad grupy, z n´ıˇz prvek a poch´az´ı. Pˇri opakovan´e aplikaci dan´eho Lemmatu se tedy budeme pohybovat v ˇretˇezci podgrup G1(qm+m0)⊂Gq(qm+m0)⊂. . .⊂Gqv(qm+m0).

(20)

Algoritmus na z´akladˇe tˇechto pozorov´an´ı funguje tak, ˇze na poˇc´atku je nalezen nejmenˇs´ı exponent j1, pro kter´y aqj1(qm+m0) = 1. Pokud j1 = 0, algoritmus nalezne hodnotuq-t´e odmocniny aplikac´ı Lemmatu 2.1.7, v opaˇc- n´em pˇr´ıpadˇe je za pouˇzit´ı Lemmatu 2.1.8 vypoˇctena nov´a hodnota a2, pro kterou aq2j2(qm+m0) = 1, kde j2 je opˇet nejmenˇs´ı takov´y exponent a pˇritom plat´ı, ˇzej2 < j1. Algoritmus takto pokraˇcuje, aˇz v nˇejak´em kroce pro nˇejak´e ai plat´ıji = 0 a m˚uˇze b´yt pouˇzito Lemma 2.1.7 k v´ypoˇctu q-t´e odmocniny bi prvku ai. Z n´ı je nakonec odvozena hodnota q-t´e odmocniny prvku a.

Konkr´etn´ı podoba algoritmu pak vypad´a n´asledovnˇe.

Algoritmus 2. AMM algoritmus

VSTUP: a∈Zp, p, q lich´a prvoˇc´ısla, q|p−1 /a0 =a/

V ´YSTUP: nˇejak´e ˇreˇsen´ıxq=a (existuje-li)

1. If ap−1q 6= 1 then Return(a nen´ıq-t´e residuum) /ovˇeˇren´ıq-residuity/

2. Zvolmeg ∈Zp takov´e, ˇzegp−1q 6= 1 /g je q-t´e neresiduum/

¯

g ←gp−1q

3. Vypoˇctˇeme v, m, m0 takov´a, ˇze p−1 = qv(qm+m0) /qv+16 |p−1/

4. s←1

5. Naleznˇeme nejmenˇs´ıj takov´e, ˇzeaqj(qm+m0)= 1 6. Whilej 6= 0 do:

(i) ¯a←aqj−1(qm+m0)

Naleznˇeme ˇreˇsen´ıλ rovnice ¯a·g¯λ = 1

(ii) a←a·gqv−j·λ /a∈Gqj−1(qm+m0) dle Lemmatu 2.1.8/

s←s·gqv−j−1·λ /a=a0 ·sq/

(iii) Naleznˇeme nejmenˇs´ıj takov´e, ˇze aqj(qm+m0) = 1 7. /j = 0 : a∈G1(qm+m0)/

h←q−1 (mod qm+m0)

b ←ah /bq =a=a0·sq/

8. Vypoˇctˇeme s−1 (mod p) /pouˇzit´ım rozˇs. Eukleidova alg./

9. Return(b·s−1) /(bs−1)q=a/

Pro hled´an´ı neresidu´ı nen´ı zn´am deterministick´y algoritmus. Nicm´enˇe, nen´ı-li prvoˇc´ıslo q pˇr´ıliˇs velk´e, lze nalezen´ı q-t´eho neresidua g v 2. kroce

(21)

prov´adˇet opakov´an´ım n´ahodn´e volby - dle D˚usledku 2.1.6 je pravdˇepodob- nost, ˇze n´ahodnˇe zvolen´e g ∈Zp bude q-t´e neresiduum, rovna hodnotˇe 1/q.

Sloˇzitost nalezen´ı potˇrebn´e hodnoty λ v kroce 6(i) odpov´ıd´a sloˇzitosti ˇreˇsen´ı ´ulohy diskr´etn´ıho logaritmu, kter´a je v obecn´em pˇr´ıpadˇe povaˇzov´ana zatˇeˇzkou. Nicm´enˇe v algoritmu je tato ´uloha ˇreˇsena v r´amciq-prvkov´e grupy, tud´ıˇz pˇri nepˇr´ıliˇs velk´em q pˇripad´a v ´uvahu v´ypoˇcet hrubou silou.

Tyto dva body v´ypoˇctu urˇcuj´ı, ˇze algoritmus funguje s vhodnou sloˇzitost´ı za pˇredpokladu, ˇzeq nen´ı pˇr´ıliˇs velk´e.

Poznamenejme, ˇze algoritmus vrac´ı jen jedno ˇreˇsen´ı rovnicexq =a. Podle Tvrzen´ı 2.1.2 lze vˇsak z v´ystupn´ı hodnoty b dopoˇc´ıtat vˇsechna ˇreˇsen´ı jako {b, bα, . . . , bαq−1}, kde jako α, hodnotu q-t´e primitivn´ı odmocniny z 1, lze pouˇzit´ım q-t´eho neresidua g, volen´eho v 2. kroce algoritmu, volit α = gp−1q (viz. d˚ukaz Lemmatu 2.1.8).

Pozn´amka 1. Pro potˇreby v´ypoˇctu druh´e odmocniny prvku, tedy q = 2, staˇc´ı v algoritmu (resp. pˇr´ısluˇsn´ych Lemmatech) jednoduˇse nahradit:q→2, m0 →1,h→m+1 aλ →1. Volba hodnotyλplyne z vlastnosti hodnoty kva- dratick´e neresiduity gp−12 =−1, ˇc´ımˇz se celkovˇe sniˇzuje v´ypoˇcetn´ı sloˇzitost algoritmu v˚uˇci sloˇzitosti pˇri prvoˇc´ıseln´em lich´em q. Obˇe moˇzn´a ˇreˇsen´ı podle Tvrzen´ı 2.1.2 z´ısk´ame jakob,−b.

2.2 V´ ypoˇ cet q

u

-t´ ych odmocnin

St´ale uvaˇzujme rozklad p−1 = qv(qm+m0) dle (∗) z pˇredchoz´ı ˇc´asti, tj.

q je libovoln´e prvoˇc´ıslo takov´e, ˇze q|p−1, a v nejvˇetˇs´ı cel´e ˇc´ıslo takov´e, ˇze qv|p−1. Pod´ıvejme se bl´ıˇze na zp˚usob, jak´ym vypoˇc´ıtat qu-tou odmocninu prvku a pˇri dan´em u.

Nab´ız´ı se pˇrirozen´a myˇslenka, ˇze z´akladn´ı AMM algoritmus pro prvo- ˇ

c´ıseln´e odmocniny aplikujemeu-kr´at za sebou. Je vˇsak zˇrejm´e, ˇze v takov´em pˇr´ıpadˇe vˇsechny postupnˇe zvolen´e hodnoty odmocnin musej´ı b´yt q-t´ymi re- sidui, aby bylo moˇzn´e v´ypoˇcet q-t´ych odmocnin skuteˇcnˇe u-kr´at rekurzivnˇe opakovat. Zaved’me si pro tento jev definici.

Definice 3. Mˇejme libovoln´e cel´e ˇc´ıslo 1 < n < p−1. Pak posloupnost a0 = a → a1 = (a0)1/n → a2 = (a1)1/n → . . . → ak = (ak−1)1/n prvk˚u ze Zp, kde vˇsechna ai pro 0 ≤ i < k jsou nutnˇe n-t´ymi residui, nazvˇeme rekurzivn´ı posloupnost´ın-t´ych residu´ıstupnˇek. Trivi´aln´ı pˇr´ıpadadefinujme jako posloupnost stupnˇe 0.

(22)

Je-li a qu-t´e residuum, pak je zˇrejm´e, ˇze takov´a rekurzivn´ı posloupnost q-t´ych residu´ı stupnˇeu existuje a sloˇzitost nalezen´ı nˇejak´equ-t´e odmocniny metodou rekurzivn´ıch v´ypoˇct˚u tedy bude odpov´ıdat sloˇzitosti nalezen´ı ta- kov´e posloupnosti.

Na pomoc si vezmˇeme strukturu z teorie graf˚u, tzv. strom. Budeme se snaˇzit pouˇz´ıvat jen v´ıcem´enˇe intuitivn´ı pojmy, form´an´ı definice t´ykaj´ıc´ı se t´eto struktury zde proto zav´adˇet nebudeme, ˇcten´aˇre pˇr´ıpadnˇe odkazujeme na nˇejakou odbornou literaturu teorie graf˚u.

Strom je specifick´y graf s propojen´ymi prvky,uzly. Uvaˇzujme graf orien- tovan´y a uspoˇr´adan´y tak, ˇze vrcholem grafu je jeden uzel a dalˇs´ı prvky leˇz´ı na jednotliv´ych niˇzˇs´ıch hladin´ach. Uzly stromu necht’ odpov´ıdaj´ı prvk˚um Zp

a je-li uzel propojen s nˇejak´ymi uzly na hladinˇe o 1 stupeˇn n´ıˇze, znamen´a to, ˇze tyto podˇrazen´e prvky, tzv.synov´e, jsou jehoq-tou odmocninou a dan´y prvek je tedyq-t´ym residuem. Nen´ı-li uzel stromu spojen s ˇz´adn´ym uzlem na niˇzˇs´ı hladinˇe, je q-t´ym neresiduem. Protoˇze uvaˇzujeme pˇr´ıpad, kdy q|p−1, m´a-li uzel stromu nˇejak´e syny, m´a jich podle Tvrzen´ı 2.1.2 pr´avˇeq, tj. jedn´a se o model tzv. ´upln´eho q-´arn´ıho stromu.

Pˇredstavme si ve vrcholu stromu prvek a, kter´y je qu-t´ym residuem.

Hled´ame-li jeho qu-t´e odmocniny, pak staˇc´ı uvaˇzovat strom hloubky u, coˇz je strom, kter´y m´a vrchol a dalˇs´ıch uurovn´ı. Vrchol de facto odpov´ıd´´ a nult´e

´

urovni. Prvky z i-t´e ´urovnˇe stromu splˇnuj´ı rovnostxqi =a a je jednoduch´e si rozmyslet, ˇze pokud je q-´arn´ı strom pln´y, tj. obsahuje pˇri sv´e hloubce maxim´aln´ı poˇcet uzl˚u, pak v kaˇzd´e ´urovnii leˇz´ıqi uzl˚u.

Pokud plat´ı, ˇze qu|p−1, tj. u≤v, potom v kaˇzd´ei-t´e ´urovni,i≤u, leˇz´ı dle Tvrzen´ı 2.1.2 vˇzdy qi r˚uzn´ych prvk˚u, tj. strom mus´ı b´yt pln´y a vˇsechny jeho cesty jsou d´elky u, tj. vedou aˇz na nejniˇzˇs´ıu-tou ´uroveˇn. Tyto cesty odpov´ıdaj´ı rekurzivn´ım q-´arn´ım posloupnostem stupnˇe u. V´ypoˇcet nˇejak´e qu-t´e odmocniny prvku rekurzivn´ım v´ypoˇctem q-t´ych odmocnin si lze tedy v tomto pˇr´ıpadˇe pˇredstavit jako pouze sestupn´y pohyb definovan´ym stro- mem - v kaˇzd´em uzlu je ovˇeˇrenaq-residuita prvku, kter´a splnˇena je, pot´e je vypoˇctena nˇejak´a hodnota q-t´e odmocniny dan´eho prvku a proveden sestup na dalˇs´ı ´uroveˇn, do pˇr´ısluˇsn´eho uzlu.

V obecn´em pˇr´ıpadˇe vˇsak tvrzen´ı, ˇze strom je pln´y, neplat´ı a pouˇzit´ı rekurzivn´ıch v´ypoˇct˚u q-t´ych odmocnin by tak k ´uspˇeˇsn´emu nalezen´ı nˇejak´e qu-t´e odmocniny obecnˇe vyˇzadovalo prohled´av´an´ı v´yˇse definovan´eho stromu, hled´an´ı cesty d´elky u. Pro pˇr´ıpad qu6 |p−1, tj. u > v, je proto vhodnˇejˇs´ı pouˇz´ıt odliˇsn´y postup v´ypoˇctu, a to dle n´asleduj´ıc´ıho tvrzen´ı. Uvˇedomme

(23)

si pˇritom, ˇze je-li b ˇreˇsen´ım xqu = a, pak danou rovnost splˇnuj´ı i vˇsechna {b, bβ, . . . , bβqv−1}, kde β je qv-t´a primitivn´ı odmocnina z 1.

Tvrzen´ı 2.2.1. Mˇejme p−1 = qv(qm+m0) s vlastnostmi dle (∗). Necht’

a ∈ Zp je qu-t´e residuum, kde u > v, a mˇejme inverzn´ı prvek h = (qu)−1 (mod qm+m0). Pak ah je qu-t´a odmocnina prvku a.

D˚ukaz. Uvˇedomme si, ˇze se jedn´a jen o jinak formulovan´e rozˇs´ıˇren´ı Lemmatu 2.1.7. Prvek a je dle pˇredpokladu qu-t´ym residuem, tud´ıˇz dle Tvrzen´ı 2.1.3 splˇnuje ap−1δ = 1, kde δ = gcd(qu, p− 1) = qv, coˇz tedy neznamen´a nic jin´eho, neˇz aqm+m0 = 1. Plat´ı, ˇze gcd(qu, qm+m0) = gcd(q, qm+m0) = 1 a zbytek plyne z Tvrzen´ı 2.1.1.

2.3 V´ ypoˇ cet r-t´ ych odmocnin

Pˇripomeˇnme si myˇslenku v´ypoˇctu r-t´e odmocniny prvkua pˇri libovoln´em r s vyuˇzit´ım v´ypoˇct˚u prvoˇc´ıseln´ych q-t´ych odmocnin. M´a-li δ = gcd(r, p−1) prvoˇc´ıseln´y rozklad δ =q1v1. . . qkvk, kdevi ≥1 pro vˇsechna 1≤i≤k, pak

r=qu11. . . qkukt,

pˇriˇcemˇz gcd(t, p−1) = 1 aui ≥vipro vˇsechna 1≤i≤k. Zap´ıˇseme-li rozklad r bez ohledu na poˇrad´ı ˇcinitel˚u obecnˇe jako r =r0. . . rk, pak potˇrebujeme postupnˇe odvodit ˇreˇsen´ı rovnic xr00 = a, xr11 = x0, . . . , xrkk = xk−1. Tento rozklad r uvaˇzujme v cel´em tomto odd´ıle.

Lemma 2.3.1. Necht’r=r0. . . rk je v´yˇse definovan´y rozklad ari bud’ nˇejak´y ˇ

cinitel rozkladu takov´y, ˇze ri|p−1. Je-li a∈Zp r-t´e residuum, pak libovoln´e ˇreˇsen´ı rovnice xri =a je (r/ri)-t´ym residuem.

D˚ukaz. Je-li a dle pˇredpokladu r-t´e residuum, pak podle Pozorov´an´ı 2.1.4 je rovnˇeˇz ri-t´ym residuem, tud´ıˇz existuje ˇreˇsen´ıb rovnice xri = a. Jestliˇze gcd(r, p−1) =δ, pak pˇri uvaˇzovan´em specifick´em rozkladu plat´ı, ˇzeri|δ a ˇze gcd(r/ri, p−1) =δ/ri. Plat´ı, ˇzeb

p−1

δ/ri = (bri)p−1δ =ap−1δ = 1, pˇriˇcemˇz posledn´ı rovnost vypl´yv´a z r-residuity prvku a. Dle Tvrzen´ı 2.1.3 tak dost´av´ame, ˇze b je (r/ri)-t´ym residuem.

Lemma 2.3.2. Necht’r=r0. . . rk je v´yˇse definovan´y rozklad ari bud’ nˇejak´y ˇ

cinitel rozkladu takov´y, ˇze ri6 |p−1. Je-li a ∈ Zp r-t´e residuum, pak af je (r/ri)-t´ym residuem pro libovoln´e 1≤f < p−1.

(24)

D˚ukaz. Bud’δ= gcd(r, p−1). Zr-residuity prvkuaplyne rovnostap−1δ = 1.

Pˇredpokl´adejme nejdˇr´ıve, ˇze gcd(ri, p−1) = 1. Potom gcd(r/ri, p−1) =δ a (af)p−1δ = (ap−1δ )f = 1. Z Tvrz. 2.1.3 tak plyne, ˇzeaf je (r/ri)-t´e residuum.

Pˇredpokl´adejme gcd(ri, p− 1) 6= 1, oznaˇcme pˇr´ısluˇsnou hodnotu jako

¯

ri. Pˇri uvaˇzovan´em specifick´em rozkladu plat´ı, ˇze gcd(r/ri, p−1) = δ/¯ri, pˇriˇcemˇz (af)

p−1

δ/¯ri = (af)p−1δ r¯i = 1, tedy opˇet se jedn´a o (r/ri)-t´e residuum.

Zvolme zp˚usob hled´an´ı ˇreˇsen´ı d´ılˇc´ıch rovnic xri =xri−1 dle vlastnost´ıri: 1. Pokud gcd(ri, p−1) = 1, pouˇzijme Tvrzen´ı 2.1.1.

2. Pokud ri dˇel´ı p−1, tj. je tvaru qiui, kde ui = vi, ˇreˇsen´ı nalezneme rekurzivn´ım, vi-kr´at opakovan´ym v´ypoˇctem nˇejak´e qi-t´e odmocniny (pouˇzijme napˇr´ıklad AMM algoritmus).

3. Pokud ri nedˇel´ıp−1, tj. je tvaru quii, kde ui > vi, pouˇzijme Tvrzen´ı 2.2.1.

Dokaˇzme, ˇze pˇri uveden´em zp˚usobu ˇreˇsen´ı jsou (nez´avisle na poˇrad´ı zpra- cov´avan´ych ˇcinitel˚u ri) vˇsechny jednotliv´e rovnice ˇreˇsiteln´e a bez nutnosti

”n´avrat˚u“ tak v´ypoˇcet vede k nalezen´ır-t´e odmocniny z a, respektive, ˇze ˇreˇsen´ı kaˇzd´e d´ılˇc´ı rovnice m´a potˇrebn´e residu´aln´ı vlastnosti k tomu, aby n´asleduj´ıc´ı libovolnˇe zvolen´a rovnice byla ˇreˇsiteln´a.

D˚ukaz. Hled´ame ˇreˇsen´ı rovnicexr=a, kdeaje r-t´e residuum ar=r0. . . rk bud’ uvaˇzovan´y rozklad v libovoln´em poˇrad´ı jeho ˇcinitel˚u.

Vezmˇeme si prvn´ı ˇcinitel, r0. Je-li rovnice xr0 =aˇreˇsiteln´a, mus´ı platit, ˇ

ze a je r0-t´e residuum. Splnˇen´ı t´eto podm´ınky plyne z r-residuity prvku a a Pozorov´an´ı 2.1.4. Dle vlastnosti r0 zvol´ıme zp˚usob ˇreˇsen´ı rovnice xr0 = a a nalezneme nˇejak´e ˇreˇsen´ıx0. Pˇriˇcemˇz, pokudr0|p−1, pakx0 je (r/r0)-t´ym residuem dle Lemmatu 2.3.1, v opaˇcn´em pˇr´ıpadˇe plat´ı, ˇzex0 =af pro urˇcit´e f ax0 je (r/r0)-t´ym residuem dle Lemmatu 2.3.2, tud´ıˇz rovnice xr/r0 =x0, kterou zb´yv´a dopoˇc´ıtat, je ˇreˇsiteln´a.

Indukc´ı tak lze analogicky uk´azat pro vˇsechna zbyl´a ri, i = 1, . . . , k, ˇze pˇri vstupu xi−1 (kter´e je (r/r0. . . ri−1)-t´ym residuem) nalezneme ˇreˇsen´ıxi rovnice xri =xi−1, kter´e je pak (r/r0. . . ri)-t´ym residuem. Nakonec z´ıskan´e xk splˇnujexrk =a a uk´azali jsme, ˇze vˇsechny potˇrebn´e d´ılˇc´ı kongruence jsou ˇreˇsiteln´e a nalezen´ı koneˇcn´eho v´ysledku lze prov´adˇet bez jak´ehokoliv n´avratu ve v´ypoˇctu. ´Uspˇeˇsnost zp˚usobu ˇreˇsen´ı dle bodu 2.(pro ri|p−1) byla ˇreˇsena v pˇredchoz´ı ˇc´asti 2.2.

(25)

2.3.1 Probl´ em faktorizace

Aˇckoliv jsme u navrˇzen´eho v´ypoˇctu libovoln´ych r-t´ych odmocnin dok´azali ˇreˇsitelnost d´ılˇc´ıch rovnic s prvoˇc´ıseln´ymi exponenty, je zˇrejm´e, ˇze d˚uleˇzit´ym aspektem pro moˇznost realizace takov´ehoto postupu nen´ı jen zm´ınˇen´a veli- kost d´ılˇc´ıch prvoˇc´ıseln´ych ˇcinitel˚u, kter´a pro ´uspˇeˇsn´e pouˇz´ıv´an´ı AMM algo- ritmu nesm´ı b´yt pˇr´ıliˇs velk´a, ale rozhoduj´ıc´ı je velkou ˇc´ast´ı prim´arnˇe sloˇzitost rozkladu gcd(r, p−1) na prvoˇc´ıseln´e ˇcinitele, tj. sloˇzitost faktorizace. Fak- torizace je vˇsak obecnˇe povaˇzov´ana za tˇeˇzk´y probl´em. Nejedn´a-li se o ˇc´ısla urˇcit´ych specifick´ych vlastnost´ı, nen´ı pro velk´a ˇc´ısla obecnˇe zn´am algoritmus takov´y, kter´y by dok´azal pˇri souˇcasn´ych v´ypoˇcetn´ıch moˇznostech faktorizo- vat libovolnˇe velk´e ˇc´ıslo v re´aln´em ˇcase.

S probl´emem faktorizace souvis´ı rovnˇeˇz probl´em v´ypoˇct˚u odmocnin vZn. Jak jsme jiˇz uvedli v ˇc´asti 1.2.1, v´ypoˇcet odmocnin vZn lze pˇri zn´am´e fak- torizaci ˇc´ısla n snadno prov´est pouˇzit´ım CRT. Pokud vˇsak faktorizaci ˇc´ısla n nezn´ame, nelze takov´y postup zvolit a jin´y obecnˇe zn´am nen´ı. Pokud je probl´em faktorizace tˇeˇzk´y, pak je (pro t´emˇeˇr vˇsechna residua)tˇeˇzk´yi v´ypoˇcet odmocnin modulo sloˇzen´e ˇc´ıslo.

2.4 V´ ypoˇ cet druh´ ych odmocnin

Kr´atce se jeˇstˇe na z´avˇer zastavme u vlastnost´ı kvadratick´ych residu´ı a alter- nativn´ıho zp˚usobu v´ypoˇctu druh´ych odmocnin pro nˇekter´e tˇr´ıdy prvoˇc´ısel.

Podle Tvrzen´ı 2.1.3 plat´ı, ˇze pokud je α gener´ator Zp, pak a ∈ Zp je kvadratick´ym residuem pr´avˇe tehdy, kdyˇza=αi, kdeije sud´e, resp. pokud ap−12 = 1. Nav´ıc plat´ı:

Tvrzen´ı 2.4.1. Prveka ∈Zp je kvadratick´ym neresiduem pr´avˇe tehdy, kdyˇz ap−12 =−1.

D˚ukaz. Plat´ı, ˇze ap−1 = 1 pro vˇsechny prvky Zp a druh´a odmocnina z 1 je

±1. Pˇriˇcemˇz ap−12 = 1 pr´avˇe tehdy, kdyˇz a je kvadratick´e residuum.

Pro zjednoduˇsen´ı z´apis˚u zaved’me znaˇcen´ı mnoˇziny vˇsech kvadratick´ych residu´ı jako Q, mnoˇzinu vˇsech kvadratick´ych neresidu´ı oznaˇcujme jako ¯Q.

Dosazen´ım do v´yrazu ap−12 lze jednoduˇse dok´azat, ˇze −1∈Q pro p≡1 (mod 4) a naopak −1 ∈ Q¯ pro p ≡ 3 (mod 4). Toho vyuˇzijeme v d˚ukazu n´asleduj´ıc´ıho tvrzen´ı.

Odkazy

Související dokumenty

Pro modelov´ an´ı bod˚ u, kter´ e nebyly prozkoum´ any, byla pouˇ zita metoda Gibbsova vzorkov´ an´ı, kter´ a pro odhad v´ yˇsek nezn´ am´ eho ter´ enu vyuˇ z´ıv´ a zn´

Napˇ r´ ıklad je moˇ zn´e se zamyslet nad ot´azkou, kter´a ze vstupuj´ ıc´ ıch mˇ e ˇ ren´ ych veliˇ cin se pod´ ıl´ ı na v´ ysledn´e nejistot ˇ e nejv´ ıce.. To

Existenci konkr´ etn´ı moˇ znosti (ze zn´ am´ e mnoˇ ziny) uk´ aˇ zeme, pokud poˇ cet moˇ znost´ı, kter´ e nemohou nastat je menˇs´ı neˇ z celkov´ y poˇ cet

Existenci konkr´ etn´ı moˇ znosti (ze zn´ am´ e mnoˇ ziny) uk´ aˇ zeme, pokud poˇ cet moˇ znost´ı, kter´ e nemohou nastat je menˇs´ı neˇ z celkov´ y poˇ cet

Pˇ ri ladˇ en´ı programu je moˇ zn´ e vyuˇ z´ıt plugin pro webov´ y prohl´ıˇ zeˇ c, kter´ y zachov´ av´ a jednotliv´ e stavy pˇ ri zmˇ enˇ e a d´ıky nezmˇ enitelnosti

V teoretick´ e ˇ c´ asti pr´ ace jsou pops´ any moˇ znosti pouˇ zit´ı jazyka Kotlin pˇ ri v´ yvoji aplikac´ı pro Android a pˇ ri v´ yvoji serverov´ ych aplikac´ı

Vˇsechny tyto parametry byly stejnˇ e jako u navrho- van´ eho algoritmu natr´ enov´ any na jejich optim´ aln´ı hodnoty, kter´ e byly posl´ eze pouˇ z´ıv´ any pouˇ z´ıv´

Aby byla takov´ a operace v˚ ubec moˇ zn´ a, je zapotˇ reb´ı syt´ emu, kter´ y umoˇ zˇ nuje centralizovanou spr´ avu, poskytuje moˇ znosti konfigurace a spr´ avy s´ıtˇ e