Algoritmul Tonelli-Shanks

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 7 martie 2020; verificarea necesită 1 editare .

Algoritmul Tonelli-Shanks (numit algoritmul RESSOL de către Shanks) aparține aritmeticii modulare și este folosit pentru a rezolva comparații

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

unde este restul patratic modulo și este un număr prim impar . $n$ $p$ $p$

Algoritmul Tonelli-Shanks nu poate fi utilizat pentru module compuse; căutarea rădăcinilor pătrate modulo compozit este echivalentă din punct de vedere computațional cu factorizarea [1] .

O versiune echivalentă, dar puțin mai complicată a acestui algoritm a fost dezvoltată de Alberto Tonelli în 1891. Versiunea algoritmului discutată aici a fost dezvoltată independent de Daniel Shanks în 1973.

Algoritm

Date de intrare : — un număr prim impar, — un număr întreg care este un rest patratic modulo , cu alte cuvinte, , unde este simbolul Legendre . $p$ $n$ $p$ $\left({\frac {n}{p}}\right)=1$ $\left(\frac{a}{b}\dreapta)$

Rezultatul algoritmului : un reziduu care satisface comparația . $R$ $R^{2}\equiv n{\pmod {p}}$

Selectăm puteri a doi din , adică fie , unde impar, . Rețineți că dacă , adică , atunci soluția este determinată de formula . În continuare, presupunem . $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$
Alegem un nerezidu pătratic arbitrar , adică simbolul Legendre , și setăm . $z$ $\left({\frac {z}{p}}\right)=-1$ $c\equiv z^{Q}{\pmod {p}}$
Lasa si $R\equiv n^{\frac {Q+1}{2}}{\pmod {p)),$ $t\equiv n^{Q}{\pmod {p)),$ $M=S.$
Executăm ciclul:
1. Dacă , atunci algoritmul revine . $t\equiv 1{\pmod {p}}$ $R$
2. În caz contrar, în buclă găsim cel mai mic , , astfel încât prin iterare la pătrat. $i$ $0<i<M$ $t^{2^{i}}\equiv 1{\pmod {p}}$
3. Să , și să , să revină la începutul ciclului. $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$

După găsirea soluției de comparație, a doua soluție de comparație se găsește ca . $R$ $pR$

Exemplu

Să facem o comparație . este impar și, deoarece , 10 este un reziduu pătratic după criteriul lui Euler . $x^{2}\equiv 10{\pmod {13}}$ $p=13$ $10^{\frac {13-1}{2}}=10^{6}\equiv 1{\pmod {13}}$

Pasul 1: deci , . $p-1=12=3\cdot 2^{2)$ $Q=3$ $S=2$
Pasul 2: Preluare - nereziduu pătratic (pentru că (din nou după criteriul lui Euler)). Sa punem $z=2$ $2^{\frac {13-1}{2}}=-1{\pmod {13}}$ $c=2^{3}\equiv 8{\pmod {13)).$
Pasul 3: $R=10^{2}\equiv -4,\;t\equiv 10^{3}\equiv -1{\pmod {13)),M=2.$
Pasul 4: Începeți bucla: deci , pentru a spune simplu, . $t\not \equiv 1{\pmod {13}}$ $0<i<2$ $i=1$
- Să , atunci . $b\equiv 8^{2^{2-1-1}}\equiv 8{\pmod {13}}$ $b^{2}\equiv 8^{2}\equiv -1{\pmod {13}}$
- Să punem , , și . $R=-4\cdot 8\equiv 7{\pmod {13}}$ $t\equiv -1\cdot -1\equiv 1{\pmod {13)}$ $M=1$
- Reporniți bucla, deoarece bucla este completă, obținem $t\equiv 1{\pmod {13}}$ $R\equiv 7{\pmod {13)).$

Deoarece , evident , de aici obținem 2 soluții de comparație. $7^{2}=49\equiv 10{\pmod {13}}$ $(\pm 7)^{2}\equiv 6^{2}\equiv 10{\pmod {13)}$

Dovada

Lasă . Acum și , rețineți că . Ultima comparație rămâne adevărată după fiecare iterație a buclei principale a algoritmului. Dacă la un moment dat , atunci algoritmul se termină cu . $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}}$

Dacă , atunci luați în considerare modul pătratic nereziduu . Fie , apoi și , ceea ce arată că ordinea este . $t\nu \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}$

În mod similar, obținem că , deci ordinea se împarte , deci ordinea este . Deoarece este un pătrat modulo , atunci este și un pătrat, ceea ce înseamnă că . $t^{2^{S}}\equiv 1{\pmod {p}}$ $t$ $2^{S}$ $t$ $2^{S'}$ $n$ $p$ $t\equiv n^{Q}{\pmod {p}}$ $S'<S$

Să presupunem că și , și . Ca și înainte, se păstrează; cu toate acestea, în această construcție , ambele și au ordine . Rezultă că are ordinea , unde . $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'$

Dacă , atunci , iar algoritmul se oprește, revenind . În caz contrar, repornim bucla cu definiții similare până când obținem , care este egal cu 0. Deoarece secvența de naturale este strict descrescătoare, algoritmul se termină. $S''=0$ $t'\equiv 1{\pmod {p}}$ $R\equiv \pm r'{\pmod {p}}$ $b',r'',c'',t''$ $S^{(j)'}$ $S^{(j)'}$

Viteza algoritmului

Algoritmul Tonelli-Shanks funcționează în medie (peste toate intrările posibile (reziduuri pătratice și nereziduuri))

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

înmulțiri modulo, unde este numărul de cifre din reprezentarea binară și este numărul de cifre din reprezentarea binară . Dacă nereziduul patratic necesar este calculat prin verificarea unuia ales aleatoriu pentru a stabili dacă este un non-reziduu pătratic, atunci în medie acest lucru necesită calcularea a două simboluri Legendre [2] . Doi ca număr mediu de simboluri Legendre calculate este explicat după cum urmează: probabilitatea ca acesta să fie un reziduu pătratic este - probabilitatea este mai mare de jumătate, deci, în medie, vor fi necesare aproximativ două verificări dacă este un reziduu pătratic. $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$

Acest lucru arată că, în practică, algoritmul Tonelli-Shanks va funcționa foarte bine dacă modulul este aleatoriu, adică atunci când nu este deosebit de mare în raport cu numărul de cifre din reprezentarea binară . Algoritmul Cipolla are performanțe mai bune decât algoritmul Tonelli-Shanks dacă și numai dacă . Totuși, dacă în schimb algoritmul lui Sutherland este folosit pentru a efectua logaritmul discret pe subgrupul 2- Sylow al lui , acest lucru permite ca numărul de înmulțiri din expresie să fie înlocuit cu o valoare mărginită asimptotic [3] . Într-adevăr, este suficient să găsiți unul care să satisfacă chiar și atunci (rețineți că este un multiplu de 2, deoarece este un reziduu patratic). $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$ $c^{e}\equiv n^{Q)$ $R\equiv c^{-e/2}n^{(Q+1)/2)$ $R^{2}\equiv n$ $e$ $n$

Algoritmul necesită găsirea unui non-reziduu pătratic . În momentul de față, nu există un algoritm determinist , care să găsească astfel de , în timp polinomial de lungime . Totuși, dacă ipoteza Riemann generalizată este adevărată, atunci există un non-rezidu pătratic , [4] , care este ușor de găsit verificând în limitele specificate în timp polinomial . Aceasta este, desigur, o estimare în cel mai rău caz, deoarece, așa cum se arată mai sus, este suficient să verificați în medie 2 dintre ele aleatorii pentru a găsi un non-rezidu pătratic. $z$ $p$ $z$ $z<2\ln ^{2}{p)$ $z$ $z$

Aplicație

Algoritmul Tonelli-Shanks poate fi folosit pentru a găsi puncte pe o curbă eliptică peste un câmp de reziduuri . Poate fi folosit și pentru calcule în criptosistemul Rabin .

Generalizare

Algoritmul Tonelli-Shanks poate fi generalizat la orice grup ciclic (în loc de ) și la găsirea rădăcinilor de gradul al treilea pentru un natural arbitrar , în special, la calcularea rădăcinilor gradului al treilea într-un câmp finit [5] . $\mathbb {F} _{p}^{\times )$ $k$ $k$ $k$

Dacă sunt multe rădăcini pătrate de calculat în același grup ciclic și nu foarte mari, pentru a îmbunătăți și simplifica algoritmul și a crește viteza acestuia, se poate pregăti un tabel cu rădăcini pătrate ale pătratelor elementelor astfel: $S$

Punem în evidență puterile a doi în : astfel încât să fie ciudat. $p-1$ $Q,S$ $p-1=2^{S}Q$ $Q$
Lasă . $R\equiv n^{\frac {Q+1}{2)}{\pmod {p)),t\equiv n^{Q}\equiv R^{2}/n{\pmod {p }}$
Să găsim rădăcina din tabelul de rapoarte și să punem $b$ $b^{2}\equiv t$ $R\equiv R/b$
Întoarce-te . $R$

Note

↑ Oded Goldreich, Computational complexity: a conceptual perspective , Cambridge University Press, 2008, p. 588.
↑ Gonzalo Tornaria , Rădăcini pătrate modulo p (link indisponibil) , pagina 2.
↑ Sutherland, Andrew V. (2011), Structure calcul and discrete logarithms in finite abelian p -groups , Mathematics of Computation vol. 80: 477–500 , DOI 10.1090/s0025-5718-10-02356-2
↑ Bach, Eric (1990), Limite explicite pentru testarea primarității și problemele conexe , Mathematics of Computation vol. 55 (191): 355–380 , DOI 10.2307/2008811
↑ LM Adleman, K. Manders, G. Miller: 1977, „On taking roots in finite fields”. În: 18th IEEE Symposium on Foundations of Computer Science. p. 175–177.

Literatură

Nesterenko A. Yu. Metode teoretice numerice în criptografie. - Moscova. - 2012. - ISBN 978-5-94506-320-4 .
Ishmukhametov Sh. T. Metode de factorizare pentru numere naturale. - Universitatea din Kazan. — 2011.
Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery . O introducere în teoria numerelor. — al 5-lea. - Wiley, 1991. - ISBN 0-471-62546-9 .
Daniel Shanks. Cinci algoritmi teoretici de numere. Proceedings of the Second Manitoba Conference on Numerical Mathematics. P. 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. P. 344-346. 1891.
Gagan Tara Nanda - Matematică 115: Algoritmul RESSOL .

Link -uri

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

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin