Algoritmy pro rychlé umocňování modulo

Modulo rychlé umocňovací algoritmy jsou druhem modulo umocňovacích algoritmů , které jsou široce používány v různých kryptosystémech pro urychlení výpočetních operací s velkými čísly.

Metoda využívající Chinese Remainder Theorem

Popis metody

Nechť je požadováno vypočítat , kde jsou čísla dostatečně velká, a nechat modul rozložit na prvočíselníky . Pak pro rychlé umocnění modulo můžete použít čínskou větu o zbytku a vyřešit systém rovnic (když jste předtím vypočítali zbytky pomocí Fermatovy věty, kde ): $S=x^{a}{\bmod {n}}$ $x, a, n$ $n=p_{1}p_{2}...p_{j}$ $x^{a}\equiv r_{i}{\pmod {p_{i}}}$ $i=1,2,...,j$

${\begin{cases}x^{a}\equiv r_{1}{\pmod {p_{1}}},\qquad 0\leqslant r_{1}<p_{1}\\x^{a}\ equiv r_{2}{\pmod {p_{2}}},\qquad 0\leqslant r_{2}<p_{2}\\\qquad ......\qquad \qquad \qquad .... ..\\x^{a}\equiv r_{j}{\pmod {p_{j}}},\qquad 0\leqslant r_{j}<p_{j}\\\end{cases}}$

Nahrazením za pro pohodlí řešíme systém s ohledem na a získáváme . $x^{a}$ $t$ $t$ $S$

Příklad

Nechť je požadováno spočítat $S=3^{5}{\bmod {3}}0$

${\begin{cases}t=3^{5}\equiv 1{\pmod {2}}\\t=3^{5}\equiv 0{\pmod {3}}\\t=3^{5 }\equiv 3{\pmod {5}}\\\end{cases}}$

Systém reprezentujeme ve formě

${\begin{cases}t=3^{5}=1+2u\\t=3^{5}=0+3v\\t=3^{5}=3+5w\\\end{cases} }$

Dosazením t z první rovnice do druhé dostaneme , potom , nebo , nebo ; $1+2u\ekviv 0{\pmod {3}}$ $2u\equiv 2{\pmod {3}}$ $u\equiv 1{\pmod {3}}$ $u=1+3h$

dosazením potom t z první rovnice do třetí, přičemž se vezme v úvahu výraz pro dostaneme nebo , pak ; $u$ $1+2(1+3h)\ekviv 3{\pmod {5}}$ $6h\ekviv 0{\pmod {5}}$ $h=0{\pmod {5}}$

pak tedy ,; $t=3^{5}\ekviv 1+2(1+3\cdot 0)\ekviv 3{\pmod {5}}$ $S=3^{5}{\bmod {5}}=3$

Aplikace

Významný zisk z tohoto algoritmu lze získat při provádění násobení. Při použití tohoto algoritmu bude násobení prováděno dvakrát rychleji.

Výpočetní složitost

Tato metoda umožňuje snížit počet výpočtů v čase. Ať je to trochu dlouhé . Při obvyklém umocňování to bude trvat asi násobení modulo. Řekněme, že chceme počítat . Snížení o a problém se redukuje na kalkulaci . Každý stupeň v tomto zápisu má délku . Proto bude každá operace umocňování vyžadovat operace. Celkem bude vyžadovat násobení modulo prvočíslo nebo místo původního násobení modulo . $3-4$ $A$ $k$ $3k/2$ $(x^{a}{\bmod {p)),x^{a}{\bmod {q)))$ $A$ $p-1$ $q-1$ $(x^{a{\bmod {(}}p-1)}{\bmod {p)),x^{a{\bmod {(}}q-1)}{\bmod {q}})$ $k/2$ $3k/4$ $2\cdot 3k/4=3k/2$ $p$ $q$ $n$

Metoda opakované kvadratury a násobení

Popis metody

Nechť je třeba vypočítat . Představte si stupeň , kde $x^{a}{\bmod {n}}$ $a=a_{j-1}2^{j-1}+a_{j-2}2^{j-2}+...+a_{2}2^{2}+a_{1}2^ {1}+a_{0}$ $a_{j}=(0,1)$

Uveďme to ve tvaru: $x^{a}{\bmod {n}}$

$x^{a}{\bmod {n}}=x^{a_{j-1}2^{j-1}+a_{j-2}2^{j-2}+...+a_{ 2}2^{2}+a_{1}2^{1}+a_{0}}{\bmod {n}}=$

$=(x^{2})^{a_{j-1}2^{j-2}+a_{j-2}2^{j-3}+...+a_{1}2^{0 }}x^{a_{0}}{\bmod {n}}=$

$=((x^{2})^{2})^{a_{j-1}2^{j-3}+a_{j-2}2^{j-4}+...+a_{ 2}2^{0}}(x^{2})^{a_{1}}x^{a_{0}}{\bmod {n}}=$

$=(...((x^{2})^{2}...)^{2})^{a_{j-1}}...(x^{8})^{a_{3 }}(x^{4})^{a_{2}}(x^{2})^{a_{1}}x^{a_{0}}{\bmod {n}}$

Dále se vypočítá hodnota výrazu a provede se nahrazení v transformovaném výrazu. $x^{2}{\bmod {n}}$

Tato operace se provádí, dokud není nalezen výsledek.

Příklad

Nechť je třeba vypočítat . Představme stupeň jako . Pojďme reprezentovat ve formě $249^{321}{\bmod {4}}99$ $321=256+64+1=2^{8}+2^{6}+2^{0}$ $249^{321}{\bmod {4}}99$ $249^{321}{\bmod {4}}99=249^{2^{8}+2^{6}+2^{0}}{\bmod {4}}99=$

$=(((((249^{2})^{2})^{2})^{2})^{2})^{2})^{2})^{2}(( ( ((249^{2})^{2})^{2})^{2})^{2})^{2}249{\bmod {4}}99=[249^{2}\ ekv. 125({\bmod {4}}99)]=$

$=(((((125^{2})^{2})^{2})^{2})^{2})^{2})^{2}((((125^{2) })^{2})^{2})^{2})^{2}249{\bmod {4}}99=[125^{2}\equiv 156({\bmod {4}}99) ]=$

$=(((((156^{2})^{2})^{2})^{2})^{2})^{2}(((156^{2})^{2}) ^{2})^{2}249{\bmod {4}}99=[156^{2}\equiv 384({\bmod {4}}99)]=$

$=((((384^{2})^{2})^{2})^{2})^{2}((384^{2})^{2})^{2}249{\ bmod {4}}99=[384^{2}\equiv 251({\bmod {4}}99)]=$

$=(((251^{2})^{2})^{2})^{2}(251^{2})^{2}249{\bmod {4}}99=[251^{2 }\equiv 127({\bmod {4}}99)]=$

$=((127^{2})^{2})^{2}127^{2}249{\bmod {4}}99=[127^{2}\equiv 161({\bmod {4}} 99)]=$

$=(161^{2})^{2}161*249{\bmod {4}}99=[161^{2}\equiv 472({\bmod {4}}99)]=$

$=472^{2}161*249{\bmod {4}}99=[472^{2}\equiv 230({\bmod {4}}99)]=$

$=230*161*249{\bmod {4}}99=447$

Aplikace

Jestliže - prvočíslo nebo je součinem dvou velkých prvočísel, pak se obvykle používá metoda opakované kvadratury a násobení. Pokud je však složený, pak se tato metoda obvykle používá spolu s čínskou větou o zbytku. $n$ $n$

Výpočetní složitost

Průměrná složitost tohoto algoritmu se rovná operacím násobení dvoubitových čísel plus operacím dělení -bitových čísel -bitovým číslem. Pro -bitová a delší čísla se tento algoritmus na počítači provádí poměrně rychle. $1.5a$ $A$ $1.5a$ $2a$ $A$ $1000$

Montgomeryho metoda umocňování

Historie

Tuto metodu navrhl v roce 1985 Peter Montgomery , aby urychlil modulární umocňování.

Popis metody

V této metodě je každé číslo spojeno s určitým obrázkem a všechny výpočty se provádějí s a na konci se provede přechod z obrázku na číslo. $X$ $F(x)$ $F(x)$

Věta (Montgomery).

Dovolit být coprime kladná celá čísla a . Potom pro jakékoli celé číslo je dělitelné , a . Navíc, jestliže , pak je rozdíl buď , nebo . $N,R$ $N'=(-N^{-1}){\bmod {R}}$ $X$ $y=x+N((xN'){\bmod {R)))$ $R$ $y/R\equiv xR^{-1}({\bmod {N)))$ $0\leqslant x<RN$ $y/R-((xR^{-1}){\bmod {N)))$ $0$ $N$

Tato věta nám umožňuje vypočítat optimálním způsobem hodnotu pro některé vhodně zvolené . $(xR^{-1}){\bmod {N}}$ $R$

Definice 1. Pro čísla , , , taková, že gcd a , nazýváme — zbytek čísla množství . $R$ $N$ $X$ $(R,N)=1$ $0\leqslant x<N$ $(R,N)$ $X$ ${\overline {x}}=(xR){\bmod {N}}$

Definice 2. Montgomeryho součin dvou celých čísel se nazývá číslo $A$ $b$ $M(a,b)=abR^{-1}{\bmod {N}}$

Věta (Montgomeryho pravidla). Nechte čísla , být coprime, a . Pak a $R$ $N$ $0\leqslant a,b<N$ $a{\bmod {N}}=M({\overline {a}},1)$ $M({\overline {a)],{\overline {b)))={\overline {ab}}$

To znamená, že pro názornost píšeme výraz pro umocňování : $X$ $3$ $M(M(M({\overline {x}},{\overline {x}}),{\overline {x}}),1)=x^{3}{\bmod {N}}$

Algoritmus (Produkt Montgomery). Nechť jsou dána celá čísla , kde je liché a . Tento algoritmus vrací . $0\leqslant c,d<N$ $N$ $R=2^{s}>N$ $M(c,d)$

1 [Funkce M Montgomery]

M(c,d)

{

x=cd

;

z=y/z

; //V souladu s teorémem (Montgomery) . 2 [Správný výsledek] jestliže ;

(z\geqslant N)z=zN

vrátit se ;

z

}

Algoritmus (Montgomeryho metoda umocňování). Nechť jsou čísla , , a zvolena stejným způsobem jako pro algoritmus (Montgomeryho součin). Tento algoritmus vrací . Binární bity označujeme . $0\leqslant x<N$ $y>0$ $R$ $x^{y}{\bmod {N}}$ $(y_{0},...,y_{D-1})$ $y$

1 [Výchozí nastavení]

{\overline {x}}=(xR){\bmod {N}}

; //Použití nějaké metody dělení se zbytkem.

{\overline {p}}=R{\bmod {N}}

; //Použití nějaké metody dělení se zbytkem. 2 [Schéma umocňování] pro {

(D-1\geqslant j\geqslant 0)

{\overline {p}}=M({\overline {p}},{\overline {p}})

; //pomocí algoritmu(Montgomery product) . jestliže ;

(y_{i}==1){\overline {p}}=M({\overline {p}},{\overline {x}})

} //Nyní se rovná .

{\overline {p}}

{\overline {x}}^{y}

3 [Konečný stupeň]

M({\overline {p)),1)

;

V důsledku toho získáme obrázek, ze kterého můžeme získat konečný výsledek , a výraz se vypočítá předem. Pro součin dvou čísel bude výsledek vypadat takto ${\overline {x}}=xR{\bmod {N}}$ $x={\overline {x}}R^{-1}{\bmod {N}}$ $R^{-1}{\bmod {N}}$ $z={\overline {z}}R^{-1}{\bmod {N}}={\overline {x}}{\overline {y}}R^{-1}{\bmod {N}} \equiv {\frac ((\overline {x}}{\overline {y}}-({\overline {x}}{\overline {y}}(N^{-1}{\bmod {R}} ){\bmod {R)))N}{R}}{\bmod {N}}$

Příklad

Nechat , a chtít vynásobit dvě čísla a (tj. čtverec) $N=11$ $b=R=2^{5}=32>N$ $x=3$ $x=3$ $X$

$3$ má obrázek $3\cdot R{\bmod {N}}=96{\bmod {1}}1=8$

(pro kontrolu má obrázek ) $9$ $9\cdot R{\bmod {N}}=288{\bmod {1}}1=2$

Obrázky násobíme:

$w={\overline {x}}\cdot {\overline {x}}=64$ ,

Provádíme přechod od obrazu násobení k požadovanému předobrazu

$q=N^{-1}{\bmod {R}}=3$ ,

$u=-w\cdot q{\bmod {R}}=-64\cdot 3{\bmod {3}}2=-192{\bmod {3}}2=0$ ,

${\overline {z}}=(w+u\cdot N)/R=(64+0\cdot 32)/32=2$

Podle toho prototyp $z={\overline {z}}\cdot R^{-1}{\bmod {N}}=2\cdot 32^{-1}{\bmod {1}}1=9$

Aplikace

Tato metoda má výkonnostní výhodu oproti metodě opakované kvadratury a násobení, protože modulové násobení dvou čísel je mnohem rychlejší.

Výpočetní složitost

Tato metoda umožňuje zredukovat (pro velké hodnoty ) výpočet funkce na jedno násobení dvou čísel velikosti . Složitost Montgomeryho násobení se odhaduje jako . $N$ $\operatorname {mod}$ $N$ $O(n^{2})$

Algoritmus pomocí "školní" metody

Popis metody

Pro přehlednost zvažte metodu pro základ , to znamená, že budeme provádět výpočty v binární (nebo binární, protože ) číselné soustavě. Základ má plus v tom, že operace dělení by je posunuta doprava a násobení by je posunuta doleva. $B=2$ $B$ $B=2$ $B=2$ $2$ $2$

Definice 1. Reprezentace nezáporného celého čísla v číselné soustavě se základem (nebo -árním zápisem čísla ) je nejkratší posloupnost celých čísel , nazývaná číslice položky, takže každá z těchto číslic splňuje nerovnost a rovnost $X$ $B$ $B$ $X$ $(x_{i})$ $0\leqslant x_{i}<B$ $x=\součet _{i=0}^{D-1}x_{i}B^{i}$

Zvažte například binární algoritmus pro převzetí z produktu . $\operatorname {mod}$ $xy$

Algoritmus (binární algoritmus pro násobení a odebrání zbytku). Nechť kladná celá čísla jsou dána taková , že , . Tento algoritmus vrací výsledek složené operace . Předpokládáme, že binární reprezentace čísla je dána podle definice 1 , takže bity čísla jsou ve tvaru , a je nejvýznamnější bit. $X$ $y$ $0\leqslant x$ $y<N$ $(xy){\bmod {N}}$ $X$ $X$ $(x_{0},...,x_{D-1})$ $x_{D-1}>0$

1 [Výchozí nastavení]

s=0

; 2 [Převést všechny bity]

D

pro {

(D-1\geqslant j\geqslant 0)

s=2s

; jestliže ;

(s\geqslant N)s=sN

jestliže ;

(x_{j}==1)s=s+y

jestliže ;

(s\geqslant N)s=sN

} vrátit se ;

s

Tato metoda má jednu nevýhodu: nevyužívá výhody vícebitové aritmetiky dostupné na jakémkoli moderním počítači. Proto se obvykle používají velké základny . $B$ $2$

Výpočtová náročnost "školní" metody

Vyjádření tvaru má odhad výpočetní složitosti − $a^{b}({\bmod {n)))$ $O_{s}((\log n)^{3})$

Viz také

Poznámky

Literatura

Crandall Richard, Pomerance Carl. Prvočísla: Kryptografické a výpočetní aspekty / Ed. a s předmluvou. V. N. Chubaríková .. - M .: URSS:: Dům knihy "LIBROKOM", 2011. - 664 s. - ISBN 978-5-453-00016-6 , 978-5-397-03060-2.
Moldavsko NA Teoretické minimum a algoritmy digitálního podpisu. - Petrohrad: BVH-Petersburg: Dům knihy "LIBROKOM", 2010. - 304 s. - ISBN 978-5-9775-0585-7 .
Ferguson, Nils, Schneier, Bruce. Praktická kryptografie. - M .: Williams Publishing House, 2004. - 432 s. — ISBN 5-8459-0733-0 .
Mao V. Moderní kryptografie : Teorie a praxe / přel. D. A. Klyushina - M. : Williams , 2005. - 768 s. — ISBN 978-5-8459-0847-6