Tonelli-Shanks algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 7 mars 2020; verifiering kräver 1 redigering .

Tonelli-Shanks-algoritmen (kallad RESSOL-algoritmen av Shanks) tillhör modulär aritmetik och används för att lösa jämförelser

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

där är den kvadratiska resten modulo och är ett udda primtal . $n$ $sid$ $sid$

Tonelli-Shanks-algoritmen kan inte användas för sammansatta moduler; att söka efter kvadratrötter modulo composite är beräkningsmässigt ekvivalent med faktorisering [1] .

En likvärdig men lite mer komplicerad version av denna algoritm utvecklades av Alberto Tonelli 1891. Den version av algoritmen som diskuteras här utvecklades oberoende av Daniel Shanks 1973.

Algoritm

Indata : — ett udda primtal, — ett heltal som är en kvadratisk rest modulo , med andra ord , där är Legendre-symbolen . $sid$ $n$ $sid$ $\left({\frac {n}{p}}\right)=1$ $\left(\frac{a}{b}\right)$

Resultatet av algoritmen : en rest som uppfyller jämförelsen . $R$ $R^{2}\equiv n{\pmod {p}}$

Vi väljer potenser av två från , det vill säga låt , där udda, . Observera att om , det vill säga, så bestäms lösningen av formeln . Därefter antar vi . $p-1$ $p-1=2^{S}Q$ $F$ $S\geqslant 1$ $S=1$ $p \equiv 3 \pmod 4$ $R\equiv \pm n^{\frac {p+1}{4))$ $S\geqslant 2$
Vi väljer en godtycklig kvadratisk icke-rest , det vill säga Legendre-symbolen , och set . $z$ $\left({\frac {z}{p}}\right)=-1$ $c\equiv z^{Q}{\pmod {p}}$
Låt också $R\equiv n^{\frac {Q+1}{2}}{\pmod {p)),$ $t\equiv n^{Q}{\pmod {p)),$ $M=S.$
Vi kör cykeln:
1. Om , då returnerar algoritmen . $t\equiv 1{\pmod {p}}$ $R$
2. Annars i slingan finner vi den minsta , , sådan att genom iteration av kvadrering. $i$ $0<i<M$ $t^{2^{i}}\equiv 1{\pmod {p}}$
3. Låt , och låt , återgå till början av cykeln. $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 att ha hittat jämförelselösningen hittas den andra jämförelselösningen som . $R$ $pR$

Exempel

Låt oss göra en jämförelse . är udda, och eftersom 10 är en kvadratisk rest enligt Eulers kriterium . $x^{2}\equiv 10{\pmod {13}}$ $p=13$ $10^{\frac {13-1}{2}}=10^{6}\equiv 1{\pmod {13}}$

Steg 1: så , . ${\displaystyle p-1=12=3\cdot 2^{2))$ $Q=3$ $S=2$
Steg 2: Ta - kvadratisk icke-rester (eftersom (igen enligt Eulers kriterium)). Låt oss sätta $z=2$ $2^{\frac {13-1}{2}}=-1{\pmod {13}}$ $c=2^{3}\equiv 8{\pmod {13)).$
Steg 3: $R=10^{2}\equiv -4,\;t\equiv 10^{3}\equiv -1{\pmod {13)),M=2.$
Steg 4: Börja slingan: så , för att uttrycka det enkelt, . $t\not \equiv 1{\pmod {13}}$ $0<i<2$ $i=1$
- Låt då . $b\equiv 8^{2^{2-1-1}}\equiv 8{\pmod {13}}$ $b^{2}\equiv 8^{2}\equiv -1{\pmod {13}}$
- Låt oss sätta , , och . $R=-4\cdot 8\equiv 7{\pmod {13}}$ $t\equiv -1\cdot -1\equiv 1{\pmod {13))$ $M=1$
- Starta om slingan, eftersom slingan är klar får vi $t\equiv 1{\pmod {13}}$ $R\equiv 7{\pmod {13)).$

Eftersom , uppenbarligen , härifrån får vi 2 jämförelselösningar. $7^{2}=49\equiv 10{\pmod {13}}$ $(\pm 7)^{2}\equiv 6^{2}\equiv 10{\pmod {13))$

Bevis

Låt . Låt nu och , notera det . Den sista jämförelsen förblir sann efter varje iteration av algoritmens huvudloop. Om någon gång slutar 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}}$

Om , då överväga den kvadratiska icke-rester modulo . Låt , sedan och , som visar att ordningen är . $t\not \equiv 1{\pmod {p}}$ $z$ $sid$ $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å samma sätt får vi det , så ordningen delar sig , så ordningen är . Eftersom är en kvadrat modulo , då är det också en kvadrat, vilket betyder att . $t^{2^{S}}\equiv 1{\pmod {p}}$ $t$ $2^{S}$ $t$ $2^{S'}$ $n$ $sid$ $t\equiv n^{Q}{\pmod {p}}$ $S'<S$

Låt oss anta att och , och . Liksom tidigare är den bevarad; dock i denna konstruktion både och har ordning . Det följer som har ordningen , där . $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'$

Om , då , och algoritmen slutar, returnerar . Annars startar vi om slingan med liknande definitioner tills vi får , vilket är lika med 0. Eftersom sekvensen av naturliga ämnen är strikt minskande, avslutas algoritmen. $S''=0$ $t'\equiv 1{\pmod {p}}$ $R\equiv \pm r'{\pmod {p}}$ $b',r'',c'',t''$ $S^{(j)'}$ $S^{(j)'}$

Algoritmhastighet

Tonelli-Shanks-algoritmen presterar i genomsnitt (över alla möjliga indata (kvadratiska rester och icke-rester))

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

modulo multiplikationer, där är antalet siffror i den binära representationen , och är antalet ettor i den binära representationen . Om den erforderliga kvadratiska icke-resten beräknas genom att kontrollera en slumpmässigt vald om det är en kvadratisk icke-rest, så kräver detta i genomsnitt beräkning av två Legendre-symboler [2] . Två som det genomsnittliga antalet beräknade Legendre-symboler förklaras enligt följande: sannolikheten att det är en kvadratisk rest är - sannolikheten är större än hälften, så i genomsnitt kommer det att ta ungefär två kontroller om det är en kvadratisk rest. $m=\lceil \log _{2}p\rceil =O(\ln p)$ $sid$ $k$ $sid$ $z$ $y$ $y$ ${\frac {\frac {p+1}{2}}{p}}={\frac {1}{2}}+{\frac {1}{2p}}>{\frac {1 }{2}}$ $y$

Detta visar att Tonelli-Shanks-algoritmen i praktiken kommer att fungera mycket bra om modulen är slumpmässig, det vill säga när den inte är särskilt stor i förhållande till antalet siffror i den binära representationen . Cipolla-algoritmen presterar bättre än Tonelli-Shanks-algoritmen om och bara om . Men om istället Sutherlands algoritm används för att utföra den diskreta logaritmen på 2- Sylow-undergruppen av , tillåter detta att antalet multiplikationer i uttrycket ersätts av ett asymptotiskt begränsat värde [3] . Det räcker faktiskt att hitta en sådan som uppfyller även då (observera att det är en multipel av 2, eftersom det är en kvadratisk rest). $sid$ $S$ $sid$ $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 att man hittar en kvadratisk icke-rest . För tillfället finns det ingen deterministisk algoritm , som skulle hitta sådana , i polynomisk tid av längd . Men om den generaliserade Riemann-hypotesen är sann, så finns det en kvadratisk icke-rest , [4] , som är lätt att hitta genom att kontrollera inom de angivna gränserna i polynomtid . Detta är naturligtvis en värsta uppskattning, eftersom det, som visas ovan, räcker med att kontrollera i genomsnitt 2 slumpmässiga för att hitta en kvadratisk icke-rest. $z$ $sid$ $z$ ${\displaystyle z<2\ln ^{2}{p))$ $z$ $z$

Applikation

Tonelli-Shanks-algoritmen kan användas för att hitta punkter på en elliptisk kurva över ett restfält . Den kan också användas för beräkningar i Rabins kryptosystem .

Generalisering

Tonelli-Shanks-algoritmen kan generaliseras till vilken cyklisk grupp som helst (istället för ) och till att hitta rötter av den th graden för en godtycklig naturlig , i synnerhet till att beräkna rötterna av den th graden i ett ändligt fält [5] . ${\displaystyle \mathbb {F} _{p}^{\times ))$ $k$ $k$ $k$

Om det finns många kvadratrötter som ska beräknas i samma cykliska grupp och inte särskilt stora, för att förbättra och förenkla algoritmen och öka dess hastighet, kan en tabell med kvadratrötter från elementens kvadrater förberedas enligt följande: $S$

Vi pekar ut krafter av två i : låt sådan att , vara udda. $p-1$ $Q,S$ $p-1=2^{S}Q$ $F$
Låt . $R\equiv n^{\frac {Q+1}{2)){\pmod {p)),t\equiv n^{Q}\equiv R^{2}/n{\pmod {p }}$
Låt oss hitta roten från kvottabellen och ställa in $b$ $b^{2}\equiv t$ $R\equiv R/b$
Återgå . $R$

Anteckningar

↑ Oded Goldreich, Computational complexity: a conceptual perspective , Cambridge University Press, 2008, s. 588.
↑ Gonzalo Tornaria , Square roots modulo p (ej tillgänglig länk) , sida 2.
↑ Sutherland, Andrew V. (2011), Structure computation and discrete logarithms in finite abelian p -groups , Mathematics of Computation vol. 80: 477–500 , DOI 10.1090/s0025-5718-160-223
↑ Bach, Eric (1990), Explicita gränser för primalitetstestning och relaterade problem , Mathematics of Computation vol. 55 (191): 355–380 , DOI 10.2307/2008811
↑ LM Adleman, K. Manders, G. Miller: 1977, "Om att slå rötter i finita fält". I: 18:e IEEE Symposium on Foundations of Computer Science. sid. 175–177.

Litteratur

Nesterenko A. Yu Talteoretiska metoder i kryptografi. - Moskva. - 2012. - ISBN 978-5-94506-320-4 .
Ishmukhametov Sh. T. Faktoriseringsmetoder för naturliga tal. – Kazans universitet. — 2011.
Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery . En introduktion till talteorin. — 5:a. - Wiley, 1991. - ISBN 0-471-62546-9 .
Daniel Shanks. Femtalsteoretiska 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 - Mathematics 115: The RESSOL Algorithm .

Länkar

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

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm