Tonelli-Shanks algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 7. marts 2020; verifikation kræver 1 redigering .

Tonelli-Shanks-algoritmen (kaldet RESSOL-algoritmen af Shanks) hører til modulær aritmetik og bruges til at løse sammenligninger

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

hvor er den kvadratiske rest modulo , og er et ulige primtal . $n$ $s$ $s$

Tonelli-Shanks-algoritmen kan ikke bruges til sammensatte moduler; søgning efter kvadratrødder modulo composite er beregningsmæssigt ækvivalent med faktorisering [1] .

En tilsvarende, men lidt mere kompliceret version af denne algoritme blev udviklet af Alberto Tonelli i 1891. Den version af algoritmen, der diskuteres her, blev udviklet uafhængigt af Daniel Shanks i 1973.

Algoritme

Inputdata : — et ulige primtal — et heltal , der er en kvadratisk rest modulo , med andre ord, , hvor er Legendre-symbolet . $s$ $n$ $s$ $\left({\frac {n}{p}}\right)=1$ $\left(\frac{a}{b}\right)$

Resultatet af algoritmen : en rest , der opfylder sammenligningen . $R$ $R^{2}\equiv n{\pmod {p}}$

Vi vælger potenser af to fra , det vil sige lad , hvor ulige, . Bemærk, at hvis , det vil sige , så er løsningen bestemt af formlen . Dernæst antager vi . $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$
Vi vælger en vilkårlig kvadratisk nonresidue , det vil sige Legendre-symbolet , og sæt . $z$ $\left({\frac {z}{p}}\right)=-1$ $c\equiv z^{Q}{\pmod {p))$
Lad også $R\equiv n^{\frac {Q+1}{2}}{\pmod {p)),$ $t\equiv n^{Q}{\pmod {p)),$ $M=S.$
Vi udfører cyklussen:
1. Hvis , så returnerer algoritmen . $t\equiv 1{\pmod {p}}$ $R$
2. Ellers finder vi i løkken den mindste , , sådan at ved iteration af kvadrat. $jeg$ $0<i<M$ $t^{2^{i}}\equiv 1{\pmod {p}}$
3. Lad , og lad , vende tilbage til begyndelsen af cyklussen. $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$

Efter at have fundet sammenligningsløsningen findes den anden sammenligningsløsning som . $R$ $pR$

Eksempel

Lad os lave en sammenligning . er ulige, og da 10 er en kvadratisk rest efter Eulers kriterium . $x^{2}\equiv 10{\pmod {13}}$ $p=13$ $10^{\frac {13-1}{2}}=10^{6}\equiv 1{\pmod {13}}$

Trin 1: så , . ${\displaystyle p-1=12=3\cdot 2^{2))$ $Q=3$ $S=2$
Trin 2: Tag - kvadratisk ikke-rest (fordi (igen efter Eulers kriterium)). Lad os sætte $z=2$ $2^{\frac {13-1}{2}}=-1{\pmod {13}}$ $c=2^{3}\equiv 8{\pmod {13)).$
Trin 3: $R=10^{2}\equiv -4,\;t\equiv 10^{3}\equiv -1{\pmod {13)),M=2.$
Trin 4: Begynd løkken: så , for at sige det enkelt, . $t\not \equiv 1{\pmod {13}}$ $0<i<2$ $i=1$
- Lad da . $b\equiv 8^{2^{2-1-1}}\equiv 8{\pmod {13}}$ $b^{2}\equiv 8^{2}\equiv -1{\pmod {13}}$
- Lad os sætte , , og . $R=-4\cdot 8\equiv 7{\pmod {13}}$ $t\equiv -1\cdot -1\equiv 1{\pmod {13))$ $M=1$
- Genstart løkken, da løkken er færdig, får vi $t\equiv 1{\pmod {13}}$ $R\equiv 7{\pmod {13)).$

Da vi naturligvis herfra får 2 sammenligningsløsninger. $7^{2}=49\equiv 10{\pmod {13}}$ $(\pm 7)^{2}\equiv 6^{2}\equiv 10{\pmod {13))$

Bevis

Lad . Lad nu og , bemærk det . Den sidste sammenligning forbliver sand efter hver iteration af algoritmens hovedsløjfe. Hvis på et tidspunkt , så afsluttes algoritmen med . $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}}$

Hvis , så overvej den kvadratiske non-residue modulo . Lad , derefter og , som viser at rækkefølgen er . $t\not \equiv 1{\pmod {p}}$ $z$ $s$ $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}$

På samme måde får vi det , så rækkefølgen deler sig , så rækkefølgen er . Da er en kvadratisk modulo , så er det også en firkant, hvilket betyder at . $t^{2^{S}}\equiv 1{\pmod {p}}$ $t$ $2^{S}$ $t$ $2^{S'}$ $n$ $s$ $t\equiv n^{Q}{\pmod {p}}$ $S'<S$

Lad os antage, at og , og . Som før er den bevaret; dog i denne konstruktion både og har orden . Det følger, at har den rækkefølge , hvor . $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'$

Hvis , så , og algoritmen stopper, returnerer . Ellers genstarter vi løkken med lignende definitioner , indtil vi får , som er lig med 0. Da sekvensen af naturals er strengt faldende, afsluttes algoritmen. $S''=0$ $t'\equiv 1{\pmod {p}}$ $R\equiv \pm r'{\pmod {p}}$ $b',r'',c'',t''$ $S^{(j)'}$ $S^{(j)'}$

Algoritmehastighed

Tonelli-Shanks-algoritmen fungerer i gennemsnit (over alle mulige input (kvadratiske rester og ikke-rester))

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

modulo multiplikationer, hvor er antallet af cifre i den binære repræsentation , og er antallet af ener i den binære repræsentation . Hvis den nødvendige kvadratiske ikke-rest beregnes ved at kontrollere en tilfældigt valgt en for, om det er en kvadratisk ikke-rest, så kræver dette i gennemsnit beregning af to Legendre-symboler [2] . To som det gennemsnitlige antal beregnede Legendre-symboler forklares som følger: sandsynligheden for, at det er en kvadratisk rest er - sandsynligheden er større end halvdelen, så i gennemsnit vil det tage omkring to kontroller, om det er en kvadratisk rest. $m=\lceil \log _{2}p\rceil =O(\ln p)$ $s$ $k$ $s$ $z$ $y$ $y$ ${\frac {\frac {p+1}{2}}{p}}={\frac {1}{2}}+{\frac {1}{2p}}>{\frac {1 }{2}}$ $y$

Dette viser, at Tonelli-Shanks-algoritmen i praksis vil fungere meget godt, hvis modulet er tilfældigt, det vil sige, når det ikke er specielt stort i forhold til antallet af cifre i den binære repræsentation . Cipolla-algoritmen yder bedre end Tonelli-Shanks-algoritmen, hvis og kun hvis . Men hvis Sutherlands algoritme i stedet bruges til at udføre den diskrete logaritme på 2 - Sylow-undergruppen af , tillader dette, at antallet af multiplikationer i udtrykket erstattes af en asymptotisk afgrænset værdi [3] . Det er faktisk tilstrækkeligt at finde en sådan, der opfylder selv da (bemærk, at det er et multiplum af 2, da det er en kvadratisk rest). $s$ $S$ $s$ $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$

Algoritmen kræver at finde en kvadratisk ikke-rest . I øjeblikket er der ingen deterministisk algoritme , som ville finde en sådan , i polynomiel længde . Men hvis den generaliserede Riemann-hypotese er sand, så er der en kvadratisk ikke-rest , [4] , som er let at finde ved at tjekke inden for de angivne grænser i polynomiel tid . Dette er naturligvis et worst-case estimat, da det, som vist ovenfor, er tilstrækkeligt at tjekke i gennemsnit 2 tilfældige for at finde en kvadratisk ikke-rest. $z$ $s$ $z$ ${\displaystyle z<2\ln ^{2}{p))$ $z$ $z$

Ansøgning

Tonelli-Shanks-algoritmen kan bruges til at finde punkter på en elliptisk kurve over et restfelt . Det kan også bruges til beregninger i Rabins kryptosystem .

Generalisering

Tonelli-Shanks-algoritmen kan generaliseres til enhver cyklisk gruppe (i stedet for ) og til at finde rødder af th grad for en vilkårlig naturlig , især til at beregne rødderne af th grad i et endeligt felt [5] . ${\displaystyle \mathbb {F} _{p}^{\times ))$ $k$ $k$ $k$

Hvis der er mange kvadratrødder, der skal beregnes i den samme cykliske gruppe og ikke er særlig store, for at forbedre og forenkle algoritmen og øge dens hastighed, kan en tabel med kvadratrødder af elementernes kvadrater udarbejdes som følger: $S$

Vi fremhæver to potenser i : lad sådan at , være ulige. $p-1$ $Q,S$ $p-1=2^{S}Q$ $Q$
Lad . $R\equiv n^{\frac {Q+1}{2)){\pmod {p)),t\equiv n^{Q}\equiv R^{2}/n{\pmod {p }}$
Lad os finde roden fra tabellen over forhold og sætte $b$ $b^{2}\equiv t$ $R\equiv R/b$
Retur . $R$

Noter

↑ Oded Goldreich, Computational complexity: a conceptual perspective , Cambridge University Press, 2008, s. 588.
↑ Gonzalo Tornaria , Kvadratrødder modulo p (utilgængeligt link) , side 2.
↑ Sutherland, Andrew V. (2011), Structure computation and discrete logarithms in finite abelian p -groups , Mathematics of Computation bind 80: 477–500 , DOI 10.1090/s0025-5718-160-2235
↑ Bach, Eric (1990), Eksplicitte grænser for primalitetstestning og relaterede problemer , Mathematics of Computation bind 55 (191): 355–380 , DOI 10.2307/2008811
↑ LM Adleman, K. Manders, G. Miller: 1977, "Om at slå rødder i endelige felter". I: 18th IEEE Symposium on Foundations of Computer Science. s. 175-177.

Litteratur

Nesterenko A. Yu. Talteoretiske metoder i kryptografi. - Moskva. - 2012. - ISBN 978-5-94506-320-4 .
Ishmukhametov Sh. T. Faktoriseringsmetoder for naturlige tal. - Kazan Universitet. – 2011.
Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery . En introduktion til talteorien. — 5. - Wiley, 1991. - ISBN 0-471-62546-9 .
Daniel Shanks. Fem talteoretiske algoritmer. Proceedings of the Second Manitoba Conference on Numerical Mathematics. 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. s. 344-346. 1891.
Gagan Tara Nanda - Matematik 115: RESSOL-algoritmen .

Links

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

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme