Text práce (558.6Kb)

(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áci napsala samostatnˇe a výhradnˇe s pouˇzit´ım citovaných pramen˚u. Souhlas´ım se zap˚ujˇcován´ım práce.

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 Z^∗p 15 2.1 Residua a jejich odmocniny . . . 16

2.1.1 AMM algoritmus . . . 18

2.2 Výpoˇcet qû-tých 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ýchoz´ı schémata a výpoˇ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ýza 35 4.1 Výskyt chybových 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 útok˚u a eliminace vlivu náhodných chyb 48 6.1 Analýza úspˇeˇsnosti chybového útoku . . . 48

6.2 Analýza útoku s chybovým 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ázev práce: Útoky zaloˇzené na hardwarových chybách Autor: Martina Válková

Katedra (´ustav): Katedra algebry

Vedouc´ı bakaláˇrské práce: Mgr. ˇStˇepán Holub, Ph.D.

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

Abstrakt: V pˇredloˇzené práci studujeme vyuˇzit´ı hardwarových výpoˇcetn´ıch chyb pro realizaci kryptoanalytických útok˚u. Zamˇeˇrujeme se konkrétnˇe na návrhy útok˚u prezentovaných v ˇclánku Biham E., Carmeli Y., Shamir A.:

Bug Attacks [1] a zkoumáme jejich praktické pouˇzit´ı v˚uˇci schémat˚um RSA a Pohlig-Hellman, vˇcetnˇe moˇznosti rozˇs´ıˇren´ı a adaptace útok˚u na r˚uzné výpoˇcetn´ı okolnosti, pˇriˇcemˇz upozorˇnujeme na vyˇsˇs´ı zranitelnost schémat pˇri realizaci modulárn´ıho mocnˇen´ı pouˇzit´ım algoritmu Right-to-Left. Pˇrináˇs´ıme výsledky praktického testován´ı útok˚u provádˇených v˚uˇci softwarové simu- laci bugového procesoru, které potvrzuj´ı skuteˇcnou bezpeˇcnostn´ı hrozbu uvaˇzované situace. ˇCistˇe matematická ˇcást práce je vˇenována výpoˇcetn´ımu pˇredpokladu jednoho z útok˚u, problematice hledán´ı odmocnin vZp.

Kl´ıˇcová slova: hardwarová chyba, útok, 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 Z^p. Keywords: hardware bug, attack, RSA, roots modulo p

(6)

Uvod ´

Práce se zamˇeˇruje na kryptoanalytické útoky, které vyuˇz´ıvaj´ı výpoˇcetn´ıch chyb deˇsifrovac´ıho zaˇr´ızen´ı. Vycház´ıme z pˇredpokladu, ˇze dané deˇsifrovac´ı zaˇr´ızen´ı obsahuje hardwarovou chybu (bug) v implementaci výpoˇcetn´ıch in- strukc´ı, kterou lze vhodným výbˇerem ˇsifrových text˚u následnˇe vyuˇz´ıt pro odhalen´ı utajovaného (deˇsifrovac´ıho) kl´ıˇce. Souˇcasná asymetrická schémata uˇz´ıvaná v kryptografii jsou postavena pˇredevˇs´ım na operaci mocnˇen´ı dlou- hých ˇc´ısel, tato operace je pˇritom typicky realizována prostˇrednictv´ım souˇci- nu. Jej´ı ˇcasté pouˇz´ıván´ı ve výpoˇctech se proto stává vhodným terˇcem útok˚u.

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

bug-attacks, vˇcetnˇe jejich základn´ıch princip˚u, vycház´ı z ˇclánku [1].

Tyto bug-útoky jsou do urˇcité m´ıry pˇr´ıbuzné s fault-attacks. Ty se sou- stˇred’uj´ı na zámˇerné vyvoláván´ı poruchy zaˇr´ızen´ı v urˇcitém okamˇziku vý- poˇctu s c´ılem zp˚usobit chybnost jeho výsledk˚u, ˇcehoˇz bývá dosahováno pro- vozován´ım ˇcinnosti zaˇr´ızen´ı v urˇcitém (neobvyklém) prostˇred´ı, jako pˇri vy- sokých teplotách, vlivem mikrovln apod. Takto vyvolané poruchy jsou vˇsak na rozd´ıl od úˇcink˚u bugu jen pˇrechodné, s náhodnými hodnotami výsledk˚u.

Vyˇzaduj´ı fyzické drˇzen´ı výpoˇcetn´ıho zaˇr´ızen´ı útoˇcn´ıkem a pro úspˇeˇsnost

´

utok˚u potˇrebuj´ı pˇresné naˇcasován´ı. Kromˇe toho jsou takové útoky dobˇre proveditelné u smart-karet, ale uˇz h˚uˇre napˇr´ıklad u poˇc´ıtaˇc˚u. Výhodou bug-

´

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

Chyby zp˚usobované bugem jsou deterministické a nastávaj´ı vˇzdy, kdyˇz je provádˇen d´ılˇc´ı výpoˇcet. Útoˇcn´ık uˇz pˇri bug-útoc´ıch neovlivˇnuje ˇcas nebo po- vahu chyby jako takové, vol´ı uˇz jen hodnoty vstup˚u prob´ıhaj´ıc´ıch výpoˇct˚u.

Smyslem práce bylo teoretické i praktické ovˇeˇren´ı realizovatelnosti a ús- pˇeˇsnosti aplikace uvaˇzovaných útok˚u, vˇcetnˇe jejich rozˇs´ıˇren´ı a adaptace na r˚uzná výpoˇcetnˇe-implementaˇcn´ı specifika.

(7)

V konkrétn´ıch útoc´ıch se zamˇeˇrujeme pˇredevˇs´ım na asymetrický ˇsifrovac´ı systém RSA, který patˇr´ı nepochybnˇe mezi jedno z nejrozˇs´ıˇrenˇejˇs´ıch schémat pouˇz´ıvaných v souˇcasné kryptografii. Pro porovnán´ı je uvaˇzováno i princi- pielnˇe podobné, ménˇe známé schéma Pohlig-Hellman, které funguje v okruhu s odliˇsnými vlastnostmi, teoreticky vyuˇzitelnými pro sn´ıˇzen´ı sloˇzitosti útok˚u.

Pˇredpokládanou metodou usnadˇnuj´ıc´ı generován´ı ˇsifrových text˚u vhodných pro útok je v jeho pˇr´ıpadˇe výpoˇcet odmocnin modulopprvoˇc´ıslo. Této problematice se vˇenuje ˇcistˇe matematická ˇcást práce - kapitola 2. J´ı pˇredcházej´ıc´ı kapitola jen struˇcnˇe shrnuje znalost v textu pouˇz´ıvaných definic a fakt z teorie ˇc´ısel v okruz´ıch a cyklických grupách a z teorie pravdˇepodobnosti.

Popisu základn´ıch uvaˇzovaných ˇsifrovac´ıch schémat a výchoz´ıch výpoˇcet- n´ıch pˇredpoklad˚u (jako je konkretizace druhu chyby v hardwarovém zaˇr´ızen´ı ˇ

ci varianta a zp˚usob implementovaných výpoˇcetn´ıch algoritm˚u) je vˇenována kapitola 3. Na základˇe tˇechto specifikac´ı jsou pak samotné myˇslenky útok˚u, pˇrevzatých z ˇclánku [1], uvedeny v kapitole 5 a v následuj´ıc´ıch kapitolách dále rozpracovávány.

Narozd´ıl od pˇredpokladu ˇclánku [1] se tato práce zamˇeˇruje i na reálný výskyt náhodných chyb bˇehem výpoˇct˚u na chybovém zaˇr´ızen´ı, jejichˇz existence jednoznaˇcnˇe ovlivˇnuje praktickou úspˇeˇsnost pˇri provádˇen´ı útok˚u. Je- jich pravdˇepodobnosti vzniku se podrobnˇe vˇenuje kapitola 4, v kapitole 6 je zkoumán vliv tˇechto chyb na uvaˇzované útoky a jsou zde popsány metody, kterými lze jejich negativn´ı vliv na úspˇeˇsnost útoku do urˇcité m´ıry redukovat. Pro moˇznost pˇr´ımého pouˇzit´ı pˇrevzatých útok˚u bylo nezbytné provést úpravy nˇekterých problematických ˇcást´ı jejich princip˚u, na jejichˇz rozbor se zamˇeˇruje kapitola 7. V n´ı je souˇcasnˇe ukázána moˇznost modifikace

´

utok˚u pro libovolný, nejen (v ˇclánku [1]) specificky pˇredpokládaný, zp˚usob implementace uvaˇzovaných algoritm˚u modulárn´ıho mocnˇen´ı (Left-to-Right, Right-to-Left). Pˇri analýze útok˚u uvid´ıme, ˇze vyhodnocován´ı deˇsifrovaných text˚u na základˇe práce s pˇresnou chybovou hodnotou vhodnˇe poskytuje

´

utoku výpoˇcetn´ı spolehlivost, proto si v této kapitole rovnˇeˇz ukáˇzeme, ˇze takový postup nen´ı nutné omezovat jen na nˇekterý z uvedených algoritm˚u mocnˇen´ı.

Z praktického hlediska pouˇzitelnosti útok˚u je také nezbytné uvaˇzovat r˚uzné optimalizace a pˇr´ıdavná schémata implementovaná souˇcasnˇe s kryp- tografickými schématy a posoudit moˇznost proveden´ı útoku i v takovém pˇr´ıpadˇe. Tomuto aspektu, se zamˇeˇren´ım na schéma RSA, se vˇenuje kapitola 8, kde je posuzována jak samotná moˇznost realizace útok˚u pˇri daných optimalizac´ıch (schématech), tak moˇznost potˇrebné modifikace p˚uvodn´ıch

(8)

n´avrh˚u ´utok˚u.

Ned´ılnou souˇcást´ı práce bylo vedle teoretické ˇcásti i praktické odzkouˇsen´ı veˇskerých útok˚u popsaných v textu. Informacemi o provedeném testován´ı se zabývá kapitola 9, ve které je ˇctenáˇr seznámen jak s d˚uleˇzitými výsledky jednotlivých útok˚u, tak i se zp˚usobem jejich proveden´ı a dalˇs´ımi d˚uleˇzitými informacemi týkaj´ıc´ımi se tohoto hlediska, jako je napˇr´ıklad volba modelu testovac´ıho zaˇr´ızen´ı nebo výbˇer testovaných parametr˚u.

Celkovým shrnut´ım se zabývá závˇereˇcná kapitola, v n´ıˇz jsou mimo jiné dána bezpeˇcnostn´ı doporuˇcen´ı, která je vhodné zavést jako urˇcitou prevenci proti realizaci útok˚u vyuˇz´ıvaj´ıc´ıch hardwarových výpoˇ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ádáme, ˇze ˇctenáˇr ovládá základy teorie pravdˇepodobnosti, a proto zde formáln´ı definice pravdˇepodobnosti a dalˇs´ıch pojm˚u (jako náhodný jev, náhodná veliˇcina) uvádˇet nebudeme. Pro naˇse potˇreby v´ıceménˇe postaˇc´ı i jen intuitivn´ı znalost tˇechto pojm˚u. Uved’me zde jen pouˇz´ıvané znaˇcen´ı a pˇripomeˇnme základn´ı fakta, která pˇri výpoˇctech pravdˇepodobnosti budeme vyuˇz´ıvat.

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

Tn

i=1A_i =Sn

i=1A¯_i,Sn

i=1A_i =Tn i=1A¯_i.

Pravdˇepodobnost náhodného jevu A znaˇc´ıme jako P(A). Základn´ı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

A_i) =

n

X

i=1

P(Ai)−X

i <

X

j

P(Ai∩A_j)+X

i <

X

j <

X

k

P(Ai∩A_j∩A_k)−. . .+(−1)ⁿ⁺¹P(

n

\

i=1

Ai)

(10)

Pozorov´an´ı 1.1.1. Rovnost P(Sn

i=1A_i) = Pn

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

i=1A_i)<Pn

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

Náhodné jevyA, B se nazývaj´ınezávislé, kdyˇzP(A∩B) = P(A)·P(B).

Náhodné jevyA₁, A₂, . . .se nazývaj´ınezávislé, kdyˇz pro libovolnou neprázd- nou podmnoˇzinu jev˚u plat´ı P(Tk

j=1Aij) = Qk

j=1P(Aij). Lze dokázat, ˇze doplˇnky nezávislých jev˚u jsou nezávislé jevy a plat´ı tvrzen´ı:

Tvrzen´ı 1.1.2. Jsou-li A₁, . . . , A_n nezávislé náhodné jevy, pak P(

n

[

i=1

A_i) = 1−

n

Y

i=1

P( ¯A_i).

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éto práci pouze v kontextu dˇelitelnosti v okruhu celých ˇc´ısel Z. Jako a|b znaˇc´ıme, ˇze a je dˇelitelem ˇc´ısla b, a jako adivb celoˇc´ıselný 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á, ˇze a a b dávaj´ı stejný zbytek po celoˇc´ıselném dˇelen´ı hodnotoun, tj. pokudn|a−b. Zápis gcd(a, b) oznaˇcuje nejvˇetˇs´ıho spoleˇcného dˇelitele prvk˚ua ab, který existuje pro kaˇzdou dvojici a, b∈ Z a pˇri dodrˇzován´ı konvence gcd(a, b)≥ 0 je jednoznaˇcnˇe urˇcen. Pro jeho výpoˇcet bývá pouˇz´ıván klasický Eukleid˚uv algoritmus, pˇriˇcemˇz staˇc´ı uvaˇzovat výpoˇcet pro a, b≥0. Pokud gcd(a, b) = 1, ˇr´ıkáme, ˇze prvky a a b jsounesoudˇelné. V rámci okruhu Z nav´ıc plat´ı tzv. Bezoutova rovnost (jej´ıˇz platnost bývá dokazována právˇe z pr˚ubˇehu Eukleidova algoritmu), která ˇr´ıká, ˇze pro kaˇzdou dvojici prvk˚u a, b∈Z existuj´ı prvkyu, v ∈Z takové, ˇze gcd(a, b) =ua+vb. Pro pˇr´ımý výpoˇcet tˇechto hodnot splˇnuj´ıc´ıch Bezoutovu rovnost se pouˇz´ıvá obsáhlejˇs´ı varianta algoritmu, tzv. rozˇs´ıˇrený Eukleid˚uv algoritmus.

(11)

Algoritmus 1. Rozˇs´ıˇrený Eukleid˚uv algoritmus ¹ VSTUP: a, bnezáporná celá ˇ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. (a₁, u₁, v₁)←(a,1,0)

(a₂, u₂, v₂)←(b,0,1) 2. i←2

3. Whilea_i 6= 0 do: /gcd(ai−1, a_i) = gcd(a_i, ai−1moda_i)/

i←i+ 1

a_i ←ai−2 (mod ai−1)

u_i ←ui−2−(ai−2divai−1)ui−1 /a_i =u_ia+v_ib/

v_i ←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á schémata, kterým se budeme v práci vˇenovat, funguj´ı v ko- neˇcných komutativn´ıch okruz´ıch (s jednotkou) (Zn,+,−,·,0,1), kde Zn = {0, . . . , n−1}a operace chápeme modulon. Pˇripomeˇnme si nˇekterá základn´ı fakta, která v tˇechto strukturách plat´ı.

Invertibiln´ım prvkem v okruhu R je takový prvek a, pro který 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⁻¹. Je-li R komutativn´ı okruh s jednotkou, pak (R^∗,·,⁻¹,1) je abelovská grupa, kde R^∗ pˇredstavuje mnoˇzinu vˇsech invertibiln´ıch prvk˚u okruhu R. Jedná 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ých s ˇc´ıslemn. Pokud jen =pê₁¹pê₂². . . pê_k^k prvoˇc´ıselný rozklad ˇc´ısla n, pak lze hodnotu Eulerovy funkce pron vypoˇc´ıtat jako

ϕ(n) =pê₁¹⁻¹pê₂²⁻¹. . . pê_k^k⁻¹·(p₁−1)(p₂−1). . .(p_k−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é indexovány podle jednotlivých krok˚u cyklu, poznamenejme vˇsak, ˇze pˇri implementaci postaˇc´ı pro výpoˇcet hodnot s in- dexemiuchovávat v pamˇeti pouze výsledky s indexyi−1 ai−2.

(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 Z^∗n = {0 < k < n : gcd(n, k) = 1} a speci´alnˇe Z^∗p = Z^p − {0}

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

Pozorován´ı 1.2.2. Mˇejme prveka ∈Z^∗n. Pakgcd(a, n) = 1a dle Bezoutovy rovnosti existuj´ı u, v ∈ Z taková, ˇze plat´ı ua+vn = 1. Odtud dostáváme hodnotu inverzn´ıho prvku a⁻¹ ≡u (mod n).

Eulerova vˇetaˇr´ıká, ˇze pokud a ∈ Z^∗n, pak a^ϕ(n) = 1. Jako d˚usledek pak plat´ı, ˇze pokud r ≡ s (mod ϕ(n)), pak a^r =a^s, tj. exponent lze redukovat modulo ϕ(n). Speciáln´ı pˇr´ıpad Eulerovy vˇety pro prvoˇc´ıslo p(ϕ(p) = p−1) se nazýváMalá Fermatova vˇeta.

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

x≡u₁ (mod n₁), . . . , x ≡u_k (mod n_k).

V následuj´ıc´ı kapitole se budeme vˇenovat problematice existence a hledán´ı ˇreˇsen´ı rovnic typux^r =a. Pro okruhZn, kdenje sloˇzené ˇc´ıslo s prvoˇc´ıselným rozkladem n = pê₁¹pê₂². . . pê_k^k, lze d´ıky platnosti CRT redukovat výpoˇcty na okruhy Zpêi_i urˇcené ˇciniteli rozkladu ˇc´ısla n, a poté jen zkombinovat d´ılˇc´ı výsledky do koneˇcného ˇreˇsen´ı. A protoˇze v této práci budeme vzhledem k výbˇeru kryptografických schémat explicitnˇe pracovat jen v okruz´ıch Zp

pro p liché prvoˇc´ıslo a Zn, kde n = pq je souˇcinem dvou lichých 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áln´ı pˇr´ıpad a = 0, a tedy pro a 6= 0 ˇreˇsit rovnici ekvivalentnˇe v mutliplikativn´ı grupˇe Z^∗p, o které nav´ıc plat´ı, ˇze je cyklická.

Jen poznamenejme, ˇze Z^∗n obecnˇe cyklickou grupou být nemus´ı. Plat´ı dokonce, ˇze Z^∗n je cyklická právˇe tehdy, kdyˇz n = 2,4, pê,2pê, kde e ≥ 1 a pje liché prvoˇc´ıslo. Platnost teorie o odmocninách tak lze rozˇs´ıˇrit na tyto cyklické grupy, avˇsak nikoliv obecnˇe pro Z^∗n, kden je libovolné sloˇzené ˇc´ıslo.

Nˇekteré výchoz´ı definice a základn´ı fakta, která plat´ı v cyklických grupách, zmiˇnme v následuj´ıc´ı ˇcásti.

(13)

1.2.2 Cyklick´ e grupy

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

zeageneruje grupuH, oznaˇcujeme jakohai=H. Pokud je grupa generována jedn´ım prvkem, tzv. generátorem, nazýváme takovou grupu cyklickou.

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

D˚ukaz. Bud’ A netriviáln´ı podgrupa Zn. Zvolme nejmenˇs´ıa ∈ A, a > 0, a bud’ m nejmenˇs´ı násobek (tj. souˇcet k sˇc´ıtanc˚u prvku a) takový, ˇze plat´ı n ≤ m = k·a. Pokud m 6= n, pak 0 < m−n < a. Protoˇze m −n ∈ A, dostáváme 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ádejme, ˇze existuje b ∈ A, které neleˇz´ı v hai. V takovém pˇr´ıpadˇe a6 |b, a tedy existuje i takové, ˇ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á implikace je zˇrejmá.

Lze ukázat, ˇze kaˇzdá koneˇcná cyklická grupa ˇrádu n je izomorfn´ı (cyk- lické) grupˇe (Zn,+,−,0). D´ıky tomu dostáváme následuj´ıc´ı tvrzen´ı.

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

T´ım jsme zároveˇn dokázali speciáln´ı pˇr´ıpad (pro cyklické grupy) obecnˇe platné Lagrangeovy vˇety, která ˇr´ıká, ˇze je-li H podgrupa koneˇcné grupy G, pak ˇrád grupy H dˇel´ı ˇrád G, specielnˇe tedy ˇrád kaˇzdého prvku dˇel´ı velikost celé grupy. O generátorech grup plat´ı následuj´ı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á grupa ˇrádu n má právˇe ϕ(n) generátor˚u a tedy rovnˇeˇz pro kaˇzdé d|n obsahuje ϕ(d) prvk˚u ˇrádu d.

Ménˇe známým d˚usledkem daného tvrzen´ı je rovnost:

(14)

D˚usledek 1.2.6. n=P

d|nϕ(d)

D˚ukaz. Kaˇzdý prvek grupy, která je ˇrádu n, generuje nˇekterou z jej´ıch podgrup. Z toho vyplývá, ˇze poˇcetn prvk˚u grupy odpov´ıdá souˇctu mnoˇzstv´ı ge- nerátor˚u pˇres vˇsechny podgrupy. Kaˇzdá podgrupa ˇrádudmá podle d˚usledku pˇredchoz´ıho tvrzen´ı právˇe ϕ(d) generátor˚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).

R´ˇad grupy pak m˚uˇzeme ekvivalentnˇe definovat jako nejmenˇs´ı kladné r ta- kové, ˇze a^r = 1 pro libovolný prvek grupy, a ˇrád prvku a jako nejmenˇs´ı kladné n takové, ˇze aⁿ = 1. Generátor α cyklické grupy ˇrádu n pak nˇekdy nazýváme n-tou primitivn´ı odmocninou z 1, nebot’ αⁿ = 1 a α^m 6= 1 pro vˇsechna 0< m < n.

Definice 1. Bud’ G koneˇcná cyklická grupa ˇrádu n. Mˇejme α generátor grupy G a libovolný prvek a ∈ G. Jako diskrétn´ı logaritmus prvku a pˇri základˇe α nazýváme jednoznaˇcnˇe urˇcené celé ˇc´ıslo x, 0≤x≤n−1, takové, ˇ

ze a=α^x, tj.x= log_αa.

Uloha nalezen´ı takov´´ ehox pˇri danýchG,α, aje známa jako (zobecnˇený) problém diskrétn´ıho logaritmu, o kterém se pˇredpokládá, ˇze jetˇeˇzký, tj. nen´ı znám zp˚usob, jak jej algoritmicky ˇreˇsit v tzv. polynomiáln´ım ˇcase alespoˇn pro nezanedbatelnou ˇcást vˇsech moˇzných vstup˚u, jsou-li parametry pro- blému peˇclivˇe vyb´ırány s ohledem na znalost jeho snadno-ˇreˇsitelných in- stanc´ı. Existuje v´ıce výpoˇcetn´ıch problém˚u, které jsou obecnˇe povaˇzovány zatˇeˇzké.²D˚ukazy pro to známy nejsou, ale nev´ı se o efektivn´ıch algoritmech, které by v obecném pˇr´ıpadˇe dokázaly danétˇeˇzké ulohy ˇreˇsit v re´´ alném ˇcase.

Snaha o jejich vyˇreˇsen´ı v konkrétn´ıch pˇr´ıpadech pak ˇcasto bývá realizována výpoˇctem hrubou silou, tj. snahou odzkouˇsen´ı vˇsech moˇznost´ı.

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

D˚ukaz. Mˇejme prvek a ˇrádu n, tj. aⁿ= 1. ˇRád prvku a^s odpov´ıdá nejmen- ˇs´ımu x takovému, ˇze (a^s)^x = 1, a podle ˇrádu prvku a mus´ı platit, ˇze n dˇel´ı sx. A protoˇze x je nejmenˇs´ı moˇzné, odpov´ıdá sx nejmenˇs´ımu spoleˇcnému násobku ˇc´ısel s, n. Rozmysleme si, ˇze je-licnejmenˇs´ım spoleˇcným násobkem 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)ⁿ .

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

(15)

Kapitola 2

V´ ypoˇ cet odmocnin v Z ^∗ _p

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

Kapitola je rozdˇelena do ˇctyˇr hlavn´ıch ˇcást´ı. V prvn´ı ˇcásti jsou pˇredloˇzena a dokázána základn´ı tvrzen´ı o existenci a vlastnostech r-tých residu´ı v Z^∗p

a popsána idea rozloˇzen´ı problému výpoˇctu jejich r-té odmocniny pˇri libo- volnémrna d´ılˇc´ı výpoˇcty prvoˇc´ıselných odmocnin. Dále zde struˇcnˇe diskutu- jeme problém aplikace známých algoritm˚u pro výpoˇcet odmocnin z hlediska pouˇzitelnosti pˇri velkých exponentech a jako nejvhodnˇejˇs´ı je zvolen a popsán tzv. AMM algoritmus, u nˇehoˇz uvád´ıme i jeho odvozen´ı.

Druhá ˇcást rozeb´ırá problematiku výpoˇctu qû-tých odmocnin metodou rekurzivnˇe poˇc´ıtaných prvoˇc´ıselnýchq-tých odmocnin, pro jej´ıˇz diskusi je zde definován pojem rekurzivn´ı posloupnosti q-tých odmocnin a ˇreˇsena jej´ı existence vZ^∗pna základˇe modelu datové strukturystromu. Pro obt´ıˇznˇejˇs´ı pˇr´ıpad qû6 |p−1 uvád´ıme alternativn´ı deterministický zp˚usob pˇr´ımého výpoˇctu.

V následuj´ıc´ıˇcásti pak dokazujeme korektnost rozloˇzen´ı problému hledán´ı r-tých odmocnin na výpoˇcty odmocnin prvoˇc´ıselných, resp. dokazujeme ˇre- ˇsitelnost d´ılˇc´ıch rovnic. Nakonec se jeˇstˇe krátce zm´ın´ıme o problému faktorizace, který s pˇredpokládanými postupy výpoˇct˚u odmocnin souvis´ı.

Speciáln´ımu pˇr´ıpadu druhých odmocnin se struˇcnˇe vˇenuje závˇer kapitoly.

Na základˇe odvozených vlastnost´ı kvadratických residu´ı jsou podrobnˇeji ana-

(16)

lyzovány moˇznosti výpoˇct˚u druhých (a 2û-tých) odmocnin a uvád´ıme alternativn´ı 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 ∈ Z^∗p nazýváme r-té residuum (modulo p), pokud má rovnice x^r = a ˇreˇsen´ı. V opaˇcném pˇr´ıpadˇe a nazýváme r-té neresiduum.

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

Reˇsen´ı rovniceˇ x^r =anaz´yv´amer-tou odmocninouprvkuaa oznaˇcujeme jej obecnˇe jako a^1/r.

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

Konkrétnˇe, pokud gcd(r, p−1) = 1, pak kaˇzdý prvek a ∈ Z^∗p je r-tým residuem a má právˇe jednu r-tou odmocninu.

D˚ukaz. Prvekrje invertibiln´ı d´ıky pˇredpokladu nesoudˇelnosti s ˇrádem grupy, tj. re≡ 1 (mod n) pro urˇcité e. Mˇejme prvek b takový, ˇze splˇnuje rovnost a=b^r. Úpravou této rovnosti dostávámeaê = (b^r)ê=b, existuje tedy právˇe jedno ˇreˇsen´ı rovnice, a to hodnotyaê, (aê)^r=a.

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

Konkrétnˇe, pokud r|p−1, pak kaˇzdé r-té residuum a ∈Z^∗p má r r˚uzných r-tých odmocnin.

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

Pro spor naopak pˇredpokládejme, ˇze existuj´ı 1 ≤ i < j ≤ r taková, ˇze bα^j =bαⁱ, tj. z vlastnosti krácen´ı v grupˇe, ˇze α^j = αⁱ. Pak plat´ıα^jα^r−i = αⁱα^r−i =α^r = 1. Dostáváme 1 = α^rα^j−i =α^j−i, 0< j −i < r, coˇz je spor.

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

(17)

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

D˚usledkem tvrzen´ı tak je, ˇze pokudr|p−1 a ajer-té residuum, náhodnˇe zvolený prvek ze Z^∗p bude r-tou odmocninou a s pravdˇepodobnost´ı _p−1^r .

Dokaˇzme nyn´ı formuli, podle n´ıˇz lze o libovolném prvku ze Z^∗p rozhod- nout, zda je r-tým residuem (pro libovolné 1< r < p−1).

Tvrzen´ı 2.1.3. Prvek a ∈ Z^∗p je r-té residuum právˇe tehdy, kdyˇz plat´ı a^p−1^δ = 1, kde δ = gcd(r, p−1). To je nav´ıc ekvivalentn´ı s t´ım, ˇze máme-li α generátor Z^∗p, pak a=αⁱ pro nˇejaké i takové, ˇze δ|i.

D˚ukaz. Pokud δ = gcd(r, p−1) = 1, pak kaˇzdé a ∈ Z^∗p je r-té residuum podle Tvrzen´ı 2.1.1, pˇriˇcemˇz rovnost a^p−1 = 1 plat´ı vˇzdy. Pˇredpokládejme proto dále δ6= 1.

Necht’ a je r-té residuum, tj. existuje b takové, ˇze a = b^r. Protoˇze δ|r, dostáváme a^p−1^δ = (b^r)^p−1^δ =b^r^δ^(p−1) = (b^p−1)^r^δ = 1.

Naopak pˇredpokládejme, ˇze plat´ıa^p−1^δ = 1. Bud’ α generátor Z^∗p, pak lze prvekavyjádˇrit jakoa=αⁱpro nˇejakéi. ˇRád prvkuaje pak podle Lemmatu 1.2.7 hodnoty _gcd(i,p−1)^p−1 a zároveˇn podle pˇredpokládané rovnosti dˇel´ı ^p−1_δ . Odtud dostáváme, ˇ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áváme, ˇze existuje e takové, ˇzere≡δ (mod p−1). Pak (αê^δⁱ)^r =α^δ^δⁱ =αⁱ =a.

Pozorován´ı 2.1.4. Necht’ a∈Z^∗p je r-té residuum a dnˇejaký dˇelitel ˇc´ıslar, pak a je rovnˇeˇz d-té residuum.

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

Tvrzen´ı 2.1.5. Poˇcet r-t´ych residu´ı v Z^∗p 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á residua právˇe vˇsechny prvky splˇnuj´ıc´ı rovnostx^d = 1. Tu splˇnuj´ı vˇsechny prvky d-tého ˇrádu a ˇrád˚u d⁰ dˇel´ıc´ıch d. Poznamenejme, ˇze d|p−1 a pˇredpoklad prvk˚u takových ˇrád˚u je tedy v souladu s Lagrangeovou vˇetou korektn´ı.

Pˇriˇcemˇz prvk˚u daného ˇrádu d⁰ je podle d˚usledku Tvrzen´ı 1.2.5 právˇe ϕ(d⁰) a podle D˚usledku 1.2.6 téhoˇz tvrzen´ı plat´ı, ˇzeP

d⁰|dϕ(d⁰) =d.

D˚usledek 2.1.6. Náhodnˇe zvolený prveka ∈Z^∗p jer-tým residuem s pravdˇe- podobnost´ı ¹_δ.

(18)

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

Pˇredpokládejme, ˇze um´ıme vypoˇc´ıtat libovolnou prvoˇc´ıselnou q-tou odmocninu prvku takovou, ˇzeq|p−1, a necht’δ= gcd(r, p−1) má prvoˇc´ıselný rozklad δ = q₁^v¹. . . q_k^v^k, kde v_i ≥ 1 pro vˇsechna 1 ≤ i ≤ k. Pak ˇc´ıslo r lze vyjádˇrit jako r =q₁û¹. . . q_kû^kt, kde t je taková hodnota, ˇze gcd(q_i, t) = 1 pro vˇsechna 1≤i≤k, a plat´ı, ˇze u_i ≥v_i a gcd(t, p−1) = 1.

Výpoˇcetr-té odmocniny lze pak rozloˇzit na ˇreˇsen´ı soustavy rovnic s exponenty urˇcenými d´ılˇc´ımi ˇciniteli uvedeného rozkladu ˇc´ısla r, tj. potˇrebujeme postupnˇe nalézt ˇreˇsen´ı rovnic x^t₀ = a, x^q

u1 1

1 = x0, . . . , x^q

uk k

k = xk−1. Pak x^r_k =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ˇzdyu_i-krát rekurzivnˇe opa- kovaný výpoˇcet qi-tých odmocnin, nebot’ x^qû = (x^qû−1)^q =a (podrobnˇeji se moˇznost´ı tohoto postupu budeme zabývat v ˇcásti 2.2). Z uvedeného principu vid´ıme, ˇze pro nalezen´ı libovolnér-té odmocniny je postaˇcuj´ıc´ı m´ıt speciáln´ı algoritmus na výpoˇcet prvoˇc´ıselných q-tých odmocnin pro pˇr´ıpady q|p−1.

Takový algoritmus odvod´ıme v následuj´ıc´ı ˇcásti, v dalˇs´ıch bude disku- tován podrobnˇeji zp˚usob výpoˇctuqû-tých odmocnin v závislosti na hodnotˇe ua poté dokázána ˇreˇsitelnost d´ılˇc´ıch kongruenc´ı ve výˇse popsaném postupu.

Protoˇze ˇreˇsen´ı rovnicex^r =aje koˇrenem polynomux^r−a a kaˇzdý prvek a∈Z^p je koˇrenem polynomu x^p−x, jinou metodou testován´ı, zda má daná rovnice ˇreˇsen´ı, m˚uˇze být zkoumán´ı (ne)soudˇelnosti polynomu x^r−as poly- nomem x^p −x v Zp[x]. Polynom x^r −a nesoudˇelný s x^p −x nemá ˇzádný koˇren ze Z^p, naopak pˇr´ıpadné existuj´ıc´ı koˇreny polynomu x^r−a, tedy r-té odmocniny prvku a, lze zjistit faktorizac´ı polynomu gcd(x^p −x, x^r−a) na lineárn´ı ˇcinitele. Tento postup je zvolen v pˇr´ıpadˇe verze algoritmu Tonelli- Shanks [4]. Metoda hledán´ı odmocnin na základˇe práce s polynomy je vˇsak pˇri velkých hodnotách exponent˚up,r v obecném pˇr´ıpadˇe nevyuˇzitelná, a to z d˚uvodu pˇr´ıliˇs velké výpoˇcetn´ı sloˇzitosti.

2.1.1 AMM algoritmus

Pro výpoˇcet q-tých odmocnin v Z^∗p, kde q|p−1, zde uvedeme algoritmus navrˇzený v ˇclánku [2] autory Adleman-Manders-Miller (dále 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é úpravy, které je

(19)

tˇreba v rámci algoritmu provést, jeho konkrétn´ı podobu lze nalézt v uve- deném ˇclánku.

AMM algoritmus vycház´ı z následuj´ıc´ıch dvou pomocných tvrzen´ı. V jejich popisu pracujme s lichými prvoˇc´ısly p,q takovými, ˇzeq|p−1. Hodnota v ≥1 necht’ je nejvˇetˇs´ı celé ˇc´ıslo takové, ˇzeq^v|p−1 (v odpov´ıdá definici tzv.

valuace). Pak

p−1 =q^v(qm+m⁰) (∗)

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

Lemma 2.1.7. Bud’ p−1 = q^v(qm+m⁰) s vlastnostmi dle (∗) a mˇejme h=q⁻¹ (mod qm+m⁰). Pokud a^qm+m⁰ = 1, pak a^h je q-tou odmocninou a.

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

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

(ag^q^v−j^λ)^q^j−1^(qm+m⁰⁾= 1.

D˚ukaz. Pro zjednoduˇsen´ı zápisu poloˇzme ¯a = a^q^j−1^(qm+m⁰⁾. Hledáme ˇreˇsen´ı λ rovnosti a^q^j−1^(qm+m⁰⁾ ·g^q^v−1^λ(qm+m⁰⁾ = 1, tj. vyjádˇren´ı inverzn´ıho prvku (¯a)⁻¹ (mod p) jako specifickou mocninu prvku ¯g = g^q^v−1^(qm+m⁰⁾ = g^(p−1)/q. Dokaˇzme existenci takového ˇreˇsen´ı.

Prvek g je dle pˇredpokladu q-té neresiduum, pˇriˇcemˇz gcd(q, p−1) = q, tud´ıˇz podle Tvrzen´ı 2.1.3 plat´ı, ˇze g^p−1^q 6= 1. Protoˇze (g^p−1^q )^q = g^p−1 = 1, ˇrád prvku ¯g 6= 1 dˇel´ı prvoˇc´ıslo q, tud´ıˇz ¯g je ˇrádu q. Dosazen´ım lze snadno ovˇeˇrit, ˇze (¯a)⁻¹ = ¯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)⁻¹ 6= 1 je rovnˇeˇz ˇrádu q. Oba prvky ¯g, (¯a)⁻¹ jsou tak generátorem q-prvkové podgrupy, pˇripomeˇnme, ˇze jedineˇcné v Z^∗p (viz.

D˚usledek 1.2.4), existuje tedy nˇejaké kladnéλ < qtakové, ˇze (¯a)⁻¹ = ¯g^λ. Lemma 2.1.8 tak ukazuje moˇznost, jak pomoc´ı libovolného q-tého neresidua odvodit z prvku a prvek leˇz´ıc´ı v podgrupˇe, jej´ıˇz ˇrád je alespoˇn o q-násobek niˇzˇs´ı neˇz je ˇrád grupy, z n´ıˇz prvek a pocház´ı. Pˇri opakované aplikaci daného Lemmatu se tedy budeme pohybovat v ˇretˇezci podgrup G_1(qm+m⁰₎⊂G_q(qm+m⁰₎⊂. . .⊂G_q^v_(qm+m⁰₎.

(20)

Algoritmus na základˇe tˇechto pozorován´ı funguje tak, ˇze na poˇcátku je nalezen nejmenˇs´ı exponent j₁, pro který a^q^j¹^(qm+m⁰⁾ = 1. Pokud j₁ = 0, algoritmus nalezne hodnotuq-té odmocniny aplikac´ı Lemmatu 2.1.7, v opaˇc- ném pˇr´ıpadˇe je za pouˇzit´ı Lemmatu 2.1.8 vypoˇctena nová hodnota a₂, pro kterou a^q₂^j²^(qm+m⁰⁾ = 1, kde j₂ je opˇet nejmenˇs´ı takový exponent a pˇritom plat´ı, ˇzej₂ < j₁. Algoritmus takto pokraˇcuje, aˇz v nˇejakém kroce pro nˇejaké a_i plat´ıj_i = 0 a m˚uˇze být pouˇzito Lemma 2.1.7 k výpoˇctu q-té odmocniny b_i prvku a_i. Z n´ı je nakonec odvozena hodnota q-té odmocniny prvku a.

Konkrétn´ı podoba algoritmu pak vypadá následovnˇe.

Algoritmus 2. AMM algoritmus

VSTUP: a∈Z^∗p, p, q lich´a prvoˇc´ısla, q|p−1 /a₀ =a/

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

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

2. Zvolmeg ∈Z^∗p takov´e, ˇzeg^p−1^q 6= 1 /g je q-t´e neresiduum/

¯

g ←g^p−1^q

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

4. s←1

5. Naleznˇeme nejmenˇs´ıj takov´e, ˇzea^q^j^(qm+m⁰⁾= 1 6. Whilej 6= 0 do:

(i) ¯a←a^q^j−1^(qm+m⁰⁾

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

(ii) a←a·g^q^v−j^·λ /a∈G_q^j−1_(qm+m⁰₎ dle Lemmatu 2.1.8/

s←s·g^q^v−j−1^·λ /a=a0 ·s^q/

(iii) Naleznˇeme nejmenˇs´ıj takov´e, ˇze a^q^j^(qm+m⁰⁾ = 1 7. /j = 0 : a∈G_1(qm+m⁰₎/

h←q⁻¹ (mod qm+m⁰)

b ←a^h /b^q =a=a₀·s^q/

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

9. Return(b·s⁻¹) /(bs⁻¹)^q=a/

Pro hledán´ı neresidu´ı nen´ı znám deterministický algoritmus. Nicménˇe, nen´ı-li prvoˇc´ıslo q pˇr´ıliˇs velké, lze nalezen´ı q-tého neresidua g v 2. kroce

(21)

provádˇet opakován´ım náhodné volby - dle D˚usledku 2.1.6 je pravdˇepodob- nost, ˇze náhodnˇe zvolené g ∈Z^∗p bude q-té neresiduum, rovna hodnotˇe 1/q.

Sloˇzitost nalezen´ı potˇrebné hodnoty λ v kroce 6(i) odpov´ıdá sloˇzitosti ˇreˇsen´ı úlohy diskrétn´ıho logaritmu, která je v obecném pˇr´ıpadˇe povaˇzována zatˇeˇzkou. Nicménˇe v algoritmu je tato úloha ˇreˇsena v rámciq-prvkové grupy, tud´ıˇz pˇri nepˇr´ıliˇs velkém q pˇripadá v úvahu výpoˇ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´ı rovnicex^q =a. Podle Tvrzen´ı 2.1.2 lze vˇsak z výstupn´ı hodnoty b dopoˇc´ıtat vˇsechna ˇreˇsen´ı jako {b, bα, . . . , bα^q−1}, kde jako α, hodnotu q-té primitivn´ı odmocniny z 1, lze pouˇzit´ım q-tého neresidua g, voleného v 2. kroce algoritmu, volit α = g^p−1^q (viz. d˚ukaz Lemmatu 2.1.8).

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

2.2 V´ ypoˇ cet q

^u

-t´ ych odmocnin

St´ale uvaˇzujme rozklad p−1 = q^v(qm+m⁰) dle (∗) z pˇredchoz´ı ˇc´asti, tj.

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

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

c´ıselné odmocniny aplikujemeu-krát za sebou. Je vˇsak zˇrejmé, ˇze v takovém pˇr´ıpadˇe vˇsechny postupnˇe zvolené hodnoty odmocnin musej´ı být q-tými residui, aby bylo moˇzné výpoˇcet q-tých odmocnin skuteˇcnˇe u-krát rekurzivnˇe opakovat. Zaved’me si pro tento jev definici.

Definice 3. Mˇejme libovolné celé ˇc´ıslo 1 < n < p−1. Pak posloupnost a₀ = a → a₁ = (a₀)^1/n → a₂ = (a₁)^1/n → . . . → a_k = (ak−1)^1/n prvk˚u ze Z^∗p, kde vˇsechna a_i pro 0 ≤ i < k jsou nutnˇe n-tými residui, nazvˇeme rekurzivn´ı posloupnost´ın-tých residu´ıstupnˇek. Triviáln´ı pˇr´ıpadadefinujme jako posloupnost stupnˇe 0.

(22)

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

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

Strom je specifický graf s propojenými prvky,uzly. Uvaˇzujme graf orien- tovaný a uspoˇrádaný tak, ˇze vrcholem grafu je jeden uzel a dalˇs´ı prvky leˇz´ı na jednotlivých niˇzˇs´ıch hladinách. Uzly stromu necht’ odpov´ıdaj´ı prvk˚um Z^∗p

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

Pˇredstavme si ve vrcholu stromu prvek a, který je qû-tým residuem.

Hledáme-li jeho qû-té odmocniny, pak staˇc´ı uvaˇzovat strom hloubky u, coˇz je strom, který má vrchol a dalˇs´ıch uurovn´ı. Vrchol de facto odpov´ıd´´ a nulté

´

urovni. Prvky z i-té úrovnˇe stromu splˇnuj´ı rovnostx^qⁱ =a a je jednoduché si rozmyslet, ˇze pokud je q-árn´ı strom plný, tj. obsahuje pˇri své hloubce maximáln´ı poˇcet uzl˚u, pak v kaˇzdé úrovnii leˇz´ıqⁱ uzl˚u.

Pokud plat´ı, ˇze qû|p−1, tj. u≤v, potom v kaˇzdéi-té úrovni,i≤u, leˇz´ı dle Tvrzen´ı 2.1.2 vˇzdy qⁱ r˚uzných prvk˚u, tj. strom mus´ı být plný a vˇsechny jeho cesty jsou délky u, tj. vedou aˇz na nejniˇzˇs´ıu-tou úroveˇn. Tyto cesty odpov´ıdaj´ı rekurzivn´ım q-árn´ım posloupnostem stupnˇe u. Výpoˇcet nˇejaké qû-té odmocniny prvku rekurzivn´ım výpoˇctem q-tých odmocnin si lze tedy v tomto pˇr´ıpadˇe pˇredstavit jako pouze sestupný pohyb definovaným stro- mem - v kaˇzdém uzlu je ovˇeˇrenaq-residuita prvku, která splnˇena je, poté je vypoˇctena nˇejaká hodnota q-té odmocniny daného prvku a proveden sestup na dalˇs´ı úroveˇn, do pˇr´ısluˇsného uzlu.

V obecném pˇr´ıpadˇe vˇsak tvrzen´ı, ˇze strom je plný, neplat´ı a pouˇzit´ı rekurzivn´ıch výpoˇct˚u q-tých odmocnin by tak k úspˇeˇsnému nalezen´ı nˇejaké qû-té odmocniny obecnˇe vyˇzadovalo prohledáván´ı výˇse definovaného stromu, hledán´ı cesty délky u. Pro pˇr´ıpad qû6 |p−1, tj. u > v, je proto vhodnˇejˇs´ı pouˇz´ıt odliˇsný postup výpoˇctu, a to dle následuj´ıc´ıho tvrzen´ı. Uvˇedomme

(23)

si pˇritom, ˇze je-li b ˇreˇsen´ım x^q^u = a, pak danou rovnost splˇnuj´ı i vˇsechna {b, bβ, . . . , bβ^q^v⁻¹}, kde β je q^v-t´a primitivn´ı odmocnina z 1.

Tvrzen´ı 2.2.1. Mˇejme p−1 = q^v(qm+m⁰) s vlastnostmi dle (∗). Necht’

a ∈ Z^∗p je qû-té residuum, kde u > v, a mˇejme inverzn´ı prvek h = (qû)⁻¹ (mod qm+m⁰). Pak a^h je qû-tá odmocnina prvku a.

D˚ukaz. Uvˇedomme si, ˇze se jedná jen o jinak formulované rozˇs´ıˇren´ı Lemmatu 2.1.7. Prvek a je dle pˇredpokladu qû-tým residuem, tud´ıˇz dle Tvrzen´ı 2.1.3 splˇnuje a^p−1^δ = 1, kde δ = gcd(qû, p− 1) = q^v, coˇz tedy neznamená nic jiného, neˇz a^qm+m⁰ = 1. Plat´ı, ˇze gcd(qû, qm+m⁰) = gcd(q, qm+m⁰) = 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ýpoˇctu r-té odmocniny prvkua pˇri libovolném r s vyuˇzit´ım výpoˇct˚u prvoˇc´ıselných q-tých odmocnin. Má-li δ = gcd(r, p−1) prvoˇc´ıselný rozklad δ =q₁^v¹. . . q_k^v^k, kdev_i ≥1 pro vˇsechna 1≤i≤k, pak

r=q^u₁¹. . . q_k^u^kt,

pˇriˇcemˇz gcd(t, p−1) = 1 au_i ≥v_ipro 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 x^r₀⁰ = a, x^r₁¹ = x₀, . . . , x^r_k^k = xk−1. Tento rozklad r uvaˇzujme v cel´em tomto odd´ıle.

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

cinitel rozkladu takový, ˇze r_i|p−1. Je-li a∈Z^∗p r-té residuum, pak libovolné ˇreˇsen´ı rovnice x^rⁱ =a je (r/r_i)-tým residuem.

D˚ukaz. Je-li a dle pˇredpokladu r-té residuum, pak podle Pozorován´ı 2.1.4 je rovnˇeˇz r_i-tým residuem, tud´ıˇz existuje ˇreˇsen´ıb rovnice x^rⁱ = a. Jestliˇze gcd(r, p−1) =δ, pak pˇri uvaˇzovaném specifickém rozkladu plat´ı, ˇzer_i|δ a ˇze gcd(r/ri, p−1) =δ/ri. Plat´ı, ˇzeb

p−1

δ/ri = (b^rⁱ)^p−1^δ =a^p−1^δ = 1, pˇriˇcemˇz posledn´ı rovnost vyplývá z r-residuity prvku a. Dle Tvrzen´ı 2.1.3 tak dostáváme, ˇze b je (r/r_i)-tým residuem.

Lemma 2.3.2. Necht’r=r₀. . . r_k je výˇse definovaný rozklad ar_i bud’ nˇejaký ˇ

cinitel rozkladu takový, ˇze r_i6 |p−1. Je-li a ∈ Z^∗p r-té residuum, pak a^f je (r/r_i)-tým residuem pro libovolné 1≤f < p−1.

(24)

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

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

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

¯

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

p−1

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

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

2. Pokud ri dˇel´ı p−1, tj. je tvaru q_iûⁱ, kde ui = vi, ˇreˇsen´ı nalezneme rekurzivn´ım, v_i-krát opakovaným výpoˇctem nˇejaké q_i-té odmocniny (pouˇzijme napˇr´ıklad AMM algoritmus).

3. Pokud r_i nedˇel´ıp−1, tj. je tvaru q^u_iⁱ, kde u_i > v_i, pouˇzijme Tvrzen´ı 2.2.1.

Dokaˇzme, ˇze pˇri uvedeném zp˚usobu ˇreˇsen´ı jsou (nezávisle na poˇrad´ı zpra- covávaných ˇcinitel˚u r_i) vˇsechny jednotlivé rovnice ˇreˇsitelné a bez nutnosti

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

D˚ukaz. Hledáme ˇreˇsen´ı rovnicex^r=a, kdeaje r-té residuum ar=r₀. . . r_k bud’ uvaˇzovaný rozklad v libovolném poˇrad´ı jeho ˇcinitel˚u.

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

ze a je r₀-té residuum. Splnˇen´ı této podm´ınky plyne z r-residuity prvku a a Pozorován´ı 2.1.4. Dle vlastnosti r₀ zvol´ıme zp˚usob ˇreˇsen´ı rovnice x^r⁰ = a a nalezneme nˇejaké ˇreˇsen´ıx0. Pˇriˇcemˇz, pokudr0|p−1, pakx0 je (r/r0)-tým residuem dle Lemmatu 2.3.1, v opaˇcném pˇr´ıpadˇe plat´ı, ˇzex₀ =a^f pro urˇcité f ax₀ je (r/r₀)-tým residuem dle Lemmatu 2.3.2, tud´ıˇz rovnice x^r/r⁰ =x₀, kterou zbývá dopoˇc´ıtat, je ˇreˇsitelná.

Indukc´ı tak lze analogicky ukázat pro vˇsechna zbylá r_i, i = 1, . . . , k, ˇze pˇri vstupu xi−1 (které je (r/r₀. . . ri−1)-tým residuem) nalezneme ˇreˇsen´ıx_i rovnice x^rⁱ =xi−1, které je pak (r/r0. . . ri)-tým residuem. Nakonec z´ıskané x_k splˇnujex^r_k =a a ukázali jsme, ˇze vˇsechny potˇrebné d´ılˇc´ı kongruence jsou ˇreˇsitelné a nalezen´ı koneˇcného výsledku lze provádˇet bez jakéhokoliv návratu ve výpoˇctu. Úspˇeˇsnost zp˚usobu ˇreˇsen´ı dle bodu 2.(pro ri|p−1) byla ˇreˇsena v pˇredchoz´ı ˇcásti 2.2.

(25)

2.3.1 Probl´ em faktorizace

Aˇckoliv jsme u navrˇzeného výpoˇctu libovolných r-tých odmocnin dokázali ˇreˇsitelnost d´ılˇc´ıch rovnic s prvoˇc´ıselnými exponenty, je zˇrejmé, ˇze d˚uleˇzitým aspektem pro moˇznost realizace takovéhoto postupu nen´ı jen zm´ınˇená velikost d´ılˇc´ıch prvoˇc´ıselných ˇcinitel˚u, která pro úspˇeˇsné pouˇz´ıván´ı AMM algoritmu nesm´ı být pˇr´ıliˇs velká, ale rozhoduj´ıc´ı je velkou ˇcást´ı primárnˇe sloˇzitost rozkladu gcd(r, p−1) na prvoˇc´ıselné ˇcinitele, tj. sloˇzitost faktorizace. Fak- torizace je vˇsak obecnˇe povaˇzována za tˇeˇzký problém. Nejedná-li se o ˇc´ısla urˇcitých specifických vlastnost´ı, nen´ı pro velká ˇc´ısla obecnˇe znám algoritmus takový, který by dokázal pˇri souˇcasných výpoˇcetn´ıch moˇznostech faktorizo- vat libovolnˇe velké ˇc´ıslo v reálném ˇcase.

S problémem faktorizace souvis´ı rovnˇeˇz problém výpoˇct˚u odmocnin vZⁿ. Jak jsme jiˇz uvedli v ˇcásti 1.2.1, výpoˇcet odmocnin vZn lze pˇri známé faktorizaci ˇc´ısla n snadno provést pouˇzit´ım CRT. Pokud vˇsak faktorizaci ˇc´ısla n neznáme, nelze takový postup zvolit a jiný obecnˇe znám nen´ı. Pokud je problém faktorizace tˇeˇzký, pak je (pro témˇeˇr vˇsechna residua)tˇeˇzkýi výpoˇcet odmocnin modulo sloˇzené ˇc´ıslo.

2.4 V´ ypoˇ cet druh´ ych odmocnin

Krátce se jeˇstˇe na závˇer zastavme u vlastnost´ı kvadratických residu´ı a alternativn´ıho zp˚usobu výpoˇctu druhých odmocnin pro nˇekteré tˇr´ıdy prvoˇc´ısel.

Podle Tvrzen´ı 2.1.3 plat´ı, ˇze pokud je α generátor Z^∗p, pak a ∈ Z^∗p je kvadratickým residuem právˇe tehdy, kdyˇza=αⁱ, kdeije sudé, resp. pokud a^p−1² = 1. Nav´ıc plat´ı:

Tvrzen´ı 2.4.1. Prveka ∈Z^∗p je kvadratick´ym neresiduem pr´avˇe tehdy, kdyˇz a^p−1² =−1.

D˚ukaz. Plat´ı, ˇze a^p−1 = 1 pro vˇsechny prvky Z^∗p a druh´a odmocnina z 1 je

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

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

Dosazen´ım do výrazu a^p−1² lze jednoduˇse dokázat, ˇze −1∈Q pro p≡1 (mod 4) a naopak −1 ∈ Q¯ pro p ≡ 3 (mod 4). Toho vyuˇzijeme v d˚ukazu následuj´ıc´ıho tvrzen´ı.