Tonelli-Shanksův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 7. března 2020; ověření vyžaduje 1 úpravu .

Algoritmus Tonelli-Shanks (Shanksem nazývaný algoritmus RESSOL) patří k modulární aritmetice a používá se k řešení porovnávání .

x^{2}\equiv n{\pmod {p)),

kde je kvadratický zbytek modulo a je liché prvočíslo . $n$ $p$ $p$

Algoritmus Tonelli-Shanks nelze použít pro složené moduly; hledání odmocnin modulo kompozit je výpočetně ekvivalentní faktorizaci [1] .

Ekvivalentní, ale o něco složitější verzi tohoto algoritmu vyvinul Alberto Tonelli v roce 1891. Zde popsaná verze algoritmu byla vyvinuta nezávisle Danielem Shanksem v roce 1973.

Algoritmus

Vstupní data : — liché prvočíslo, — celé číslo , které je kvadratickým zbytkem modulo , jinými slovy , kde je Legendreův symbol . $p$ $n$ $p$ $\left({\frac {n}{p}}\right)=1$ $\left(\frac{a}{b}\right)$

Výsledek algoritmu : zbytek , který vyhovuje srovnání . $R$ $R^{2}\equiv n{\pmod {p}}$

Vybíráme mocniny dvou z , tedy nechť , kde liché, . Všimněte si, že pokud , to je , pak je řešení určeno vzorcem . Dále předpokládáme . $p-1$ $p-1=2^{S}Q$ $Q$ $S\geqslant 1$ $S=1$ $p \equiv 3 \pmod 4$ $R\equiv \pm n^{\frac {p+1}{4))$ $S\geqslant 2$
Zvolíme libovolný kvadratický nonresidue , tedy Legendreův symbol , a nastavíme . $z$ $\left({\frac {z}{p}}\right)=-1$ $c\equiv z^{Q}{\pmod {p}}$
Nechte také $R\equiv n^{\frac {Q+1}{2}}{\pmod {p)),$ $t\equiv n^{Q}{\pmod {p)),$ $M=S.$
Provedeme cyklus:
1. Pokud , pak se algoritmus vrátí . $t\equiv 1{\pmod {p}}$ $R$
2. Jinak ve smyčce najdeme nejmenší , , takové, že iterací kvadratury. $i$ $0<i<M$ $t^{2^{i}}\equiv 1{\pmod {p}}$
3. Nechte , a nechte , vrátit se na začátek cyklu. $b\equiv c^{2^{Mi-1}}{\pmod {p}}$ $R:\equiv Rb{\pmod {p)),$ $t:\equiv tb^{2}{\pmod {p)),$ $c:\equiv b^{2}{\pmod {p)),$ $M:=i$

Po nalezení srovnávacího řešení je druhé srovnávací řešení nalezeno jako . $R$ $pR$

Příklad

Udělejme srovnání . je liché, a protože , 10 je kvadratický zbytek podle Eulerova kritéria . $x^{2}\equiv 10{\pmod {13}}$ $p=13$ $10^{\frac {13-1}{2}}=10^{6}\equiv 1{\pmod {13}}$

Krok 1: tak , . ${\displaystyle p-1=12=3\cdot 2^{2))$ $Q=3$ $S=2$
Krok 2: Vezměte - kvadratické nezbytky (protože (opět podle Eulerova kritéria)). Položme $z=2$ $2^{\frac {13-1}{2}}=-1{\pmod {13}}$ $c=2^{3}\equiv 8{\pmod {13)).$
Krok 3: $R=10^{2}\equiv -4,\;t\equiv 10^{3}\equiv -1{\pmod {13)),M=2.$
Krok 4: Začněte smyčku: takže zjednodušeně řečeno . $t\not \equiv 1{\pmod {13}}$ $0<i<2$ $i=1$
- Nechte tedy . $b\equiv 8^{2^{2-1-1}}\equiv 8{\pmod {13}}$ $b^{2}\equiv 8^{2}\equiv -1{\pmod {13}}$
- Položme , , a . $R=-4\cdot 8\equiv 7{\pmod {13}}$ $t\equiv -1\cdot -1\equiv 1{\pmod {13))$ $M=1$
- Restartujte smyčku, protože smyčka je dokončena, dostaneme $t\equiv 1{\pmod {13}}$ $R\equiv 7{\pmod {13)).$

Vzhledem k tomu , samozřejmě , odtud dostáváme 2 řešení porovnání. $7^{2}=49\equiv 10{\pmod {13}}$ $(\pm 7)^{2}\equiv 6^{2}\equiv 10{\pmod {13))$

Důkaz

Nechte _ Nechte nyní a , všimněte si toho . Poslední srovnání zůstává pravdivé po každé iteraci hlavní smyčky algoritmu. Pokud v určitém okamžiku , pak algoritmus skončí s . $p-1=2^{S}Q$ $r\equiv n^{\frac {Q+1}{2}}{\pmod {p}}$ $t\equiv n^{Q}{\pmod {p))$ $r^{2}\equiv nt{\pmod {p}}$ $t\equiv 1{\pmod {p}}$ $r^{2}\equiv n{\pmod {p}}$ $R\equiv \pm r{\pmod {p}}$

Jestliže , pak zvažte kvadratický nezbytkový modulo . Nechť , pak a , což ukazuje, že pořadí je . $t\not \equiv 1{\pmod {p}}$ $z$ $p$ $c\equiv z^{Q}{\pmod {p}}$ $c^{2^{S}}\equiv (z^{Q})^{2^{S}}\equiv z^{p-1}\equiv 1{\pmod {p}}$ $c^{2^{S-1}}\equiv z^{\frac {p-1}{2}}\equiv \left({\frac {z}{p}}\right)\equiv -1{\pmod {p}}$ $C$ $2^{S}$

Podobně dostaneme, že , takže pořadí se dělí , takže pořadí je . Protože je čtverec modulo , pak je to také čtverec, což znamená, že . $t^{2^{S}}\equiv 1{\pmod {p}}$ $t$ $2^{S}$ $t$ $2^{S'}$ $n$ $p$ $t\equiv n^{Q}{\pmod {p))$ $S'<S$

Předpokládejme, že a , a . Stejně jako dříve je zachována; však v této konstrukci , oba a mají pořádek . Z toho vyplývá, že má pořadí , kde . $b\equiv c^{2^{SS'-1}}{\pmod {p}}$ $r'\equiv br{\pmod {p}}$ $c'\equiv b^{2}{\pmod {p))$ $t'\equiv c't{\pmod {p}}$ $r'^{2}\equiv nt'{\pmod {p))$ $t$ $c'$ $2^{S'}$ $t'$ $2^{S''}$ $S''<S'$

Pokud , potom , a algoritmus se zastaví, vrátí se . V opačném případě restartujeme smyčku s podobnými definicemi , dokud nedostaneme , která se rovná 0. Protože posloupnost přirozených je přísně klesající, algoritmus skončí. $S''=0$ $t'\equiv 1{\pmod {p}}$ $R\equiv \pm r'{\pmod {p}}$ $b',r'',c'',t''$ $S^{(j)'}$ $S^{(j)'}$

Rychlost algoritmu

Algoritmus Tonelli-Shanks funguje v průměru (přes všechny možné vstupy (kvadratické zbytky a nezbytky))

2m+2k+{\frac {S(S-1)}{4}}+{\frac {1}{2^{S-1}}}-9=O(S^{2})= O(\ln ^{2}p)

modulo násobení, kde je počet číslic v binární reprezentaci a je počet jedniček v binární reprezentaci . Pokud se požadované kvadratické nezbytky vypočítávají kontrolou náhodně vybraného , zda se jedná o kvadratické nezbytky, pak to v průměru vyžaduje výpočet dvou Legendreových symbolů [2] . Dva jako průměrný počet vypočítaných Legendreových symbolů se vysvětluje následovně: pravděpodobnost, že se jedná o kvadratický zbytek je - pravděpodobnost je větší než poloviční, takže v průměru zabere asi dvě kontroly, zda se jedná o kvadratický zbytek. $m=\lceil \log _{2}p\rceil =O(\ln p)$ $p$ $k$ $p$ $z$ $y$ $y$ ${\frac {\frac {p+1}{2}}{p}}={\frac {1}{2}}+{\frac {1}{2p}}>{\frac {1 {2}}$ $y$

To ukazuje, že v praxi bude Tonelli-Shanksův algoritmus fungovat velmi dobře, pokud je modul náhodný, to znamená, když není příliš velký vzhledem k počtu číslic v binární reprezentaci . Algoritmus Cipolla funguje lépe než algoritmus Tonelli-Shanks tehdy a jen tehdy, když . Pokud se však místo toho použije Sutherlandův algoritmus k provedení diskrétního logaritmu na 2- Sylow podskupině , umožňuje to nahradit počet násobení ve výrazu asymptoticky omezenou hodnotou [3] . Ve skutečnosti stačí najít takový, který vyhovuje i tehdy (všimněte si, že je to násobek 2, protože je kvadratický zbytek). $p$ $S$ $p$ $S(S-1)>8m+20$ $\mathbb {F} _{p}$ $S(S-1)$ $O\left({\frac {S\ln S}{\ln \ln S}}\right)$ $E$ ${\displaystyle c^{e}\equiv n^{Q))$ ${\displaystyle R\equiv c^{-e/2}n^{(Q+1)/2))$ $R^{2}\equiv n$ $E$ $n$

Algoritmus vyžaduje nalezení kvadratického non-rezidua . V tuto chvíli neexistuje žádný deterministický algoritmus , který by takové našel v polynomiálním čase délky . Je-li však zobecněná Riemannova hypotéza pravdivá, pak existuje kvadratický nezbytek , [4] , který lze snadno najít kontrolou ve specifikovaných mezích v polynomiálním čase . Toto je samozřejmě odhad nejhoršího případu, protože, jak je uvedeno výše, stačí zkontrolovat průměrně 2 náhodné, aby se našel kvadratický zbytek. $z$ $p$ $z$ ${\displaystyle z<2\ln ^{2}{p))$ $z$ $z$

Aplikace

Algoritmus Tonelli-Shanks lze použít k nalezení bodů na eliptické křivce nad polem zbytků . Může být také použit pro výpočty v Rabinově kryptosystému .

Generalizace

Tonelli-Shanksův algoritmus lze zobecnit na libovolnou cyklickou grupu (místo ) a na hledání kořenů tého stupně pro libovolný přirozený , zejména na výpočet kořenů tého stupně v konečném poli [5] . ${\displaystyle \mathbb {F} _{p}^{\times ))$ $k$ $k$ $k$

Pokud je ve stejné cyklické skupině mnoho odmocnin, které je třeba vypočítat a nejsou příliš velké, lze pro zlepšení a zjednodušení algoritmu a zvýšení jeho rychlosti připravit tabulku druhých odmocnin druhých mocnin prvků takto: $S$

Vyčleňujeme mocniny dvou v : nechť takové, že , je liché. $p-1$ $Q,S$ $p-1=2^{S}Q$ $Q$
Nechte _ $R\equiv n^{\frac {Q+1}{2)){\pmod {p)),t\equiv n^{Q}\equiv R^{2}/n{\pmod {p }}$
Najdeme kořen z tabulky poměrů a dáme $b$ $b^{2}\equiv t$ $R\equiv R/b$
Návrat . $R$

Poznámky

↑ Oded Goldreich, Computational complexity: a conceptual perspective , Cambridge University Press, 2008, str. 588.
↑ Gonzalo Tornaria , Odmocniny modulo p (nedostupný odkaz) , strana 2.
↑ Sutherland, Andrew V. (2011), Výpočet struktury a diskrétní logaritmy v konečných abelovských p -grupách , Mathematics of Computation sv. 80: 477–500 , DOI 10.1090/s0025-5718-10-202
↑ Bach, Eric (1990), Explicitní hranice pro testování primálnosti a související problémy , Mathematics of Computation sv. 55 (191): 355–380 , DOI 10.2307/2008811
↑ LM Adleman, K. Manders, G. Miller: 1977, „O zakořenění v konečných polích“. In: 18. IEEE Symposium on Foundations of Computer Science. p. 175–177.

Literatura

Nesterenko A. Yu.Číselné teoretické metody v kryptografii. - Moskva. - 2012. - ISBN 978-5-94506-320-4 .
Ishmukhametov Sh. T. Faktorizační metody pro přirozená čísla. — Kazaňská univerzita. — 2011.
Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery . Úvod do teorie čísel. — 5. - Wiley, 1991. - ISBN 0-471-62546-9 .
Daniel Shanks. Teoretické algoritmy pěti čísel. Sborník příspěvků z druhé manitobské konference o numerické matematice. S. 51–70. 1973.
Alberto Tonelli, Bemerkung uber die Auflosung quadratischer Congruenzen . Nachrichten von der Koniglichen Gesellschaft der Wissenschaften und der Georg-Augusts-Universitat zu Gottingen. str. 344-346. 1891.
Gagan Tara Nanda - Matematika 115: Algoritmus RESSOL .

Odkazy

Implementace Pythonu http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin