Tonelli-Shanks-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 7.3.2020 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Tonelli-Shanks-algoritmi (Shanks kutsuu sitä RESSOL-algoritmiksi) kuuluu modulaariseen aritmetiikkaan ja sitä käytetään vertailujen ratkaisemiseen.

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

missä on neliöllinen jäännös modulo ja on pariton alkuluku . $n$ $s$ $s$

Tonelli-Shanks-algoritmia ei voi käyttää yhdistelmämoduuleille; Modulokomposiitin neliöjuuren etsiminen vastaa laskennallisesti tekijöiden jakamista [1] .

Alberto Tonelli kehitti vastaavan mutta hieman monimutkaisemman version tästä algoritmista vuonna 1891. Tässä käsitellyn algoritmin version kehitti itsenäisesti Daniel Shanks vuonna 1973.

Algoritmi

Syöttötiedot : — pariton alkuluku, — kokonaisluku , joka on neliöllinen jäännös modulo , toisin sanoen , jossa on Legendre-symboli . $s$ $n$ $s$ $\left({\frac {n}{p}}\right)=1$ $\left(\frac{a}{b}\right)$

Algoritmin tulos : jäännös , joka tyydyttää vertailun . $R$ $R^{2}\equiv n{\pmod {p}}$

Valitsemme kahden potenssit kohdasta , eli anna , missä pariton, . Huomaa, että jos eli , niin ratkaisu määräytyy kaavan mukaan . Seuraavaksi oletamme . $p-1$ $p-1=2^{S}Q$ $K$ $S\geqslant 1$ $S=1$ $p \equiv 3 \pmod 4$ $R\equiv \pm n^{\frac {p+1}{4))$ $S\geqslant 2$
Valitsemme mielivaltaisen neliöllisen nonresiduen eli Legendre-symbolin ja asetamme . $z$ $\left({\frac {z}{p}}\right)=-1$ $c\equiv z^{Q}{\pmod {p))$
Anna myös $R\equiv n^{\frac {Q+1}{2}}{\pmod {p)),$ $t\equiv n^{Q}{\pmod {p)),$ $M=S.$
Suoritamme syklin:
1. Jos , niin algoritmi palauttaa . $t\equiv 1{\pmod {p}}$ $R$
2. Muuten silmukasta löydämme pienimmän , , siten, että iteroimalla neliöinti. $i$ $0<i<M$ $t^{2^{i}}\equiv 1{\pmod {p}}$
3. Anna , ja anna palata syklin alkuun. $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$

Kun vertailuratkaisu on löydetty, toinen vertailuratkaisu löytyy muodossa . $R$ $pR$

Esimerkki

Tehdään vertailu . on pariton, ja koska , 10 on neliöllinen jäännös Eulerin kriteerin mukaan . $x^{2}\equiv 10{\pmod {13}}$ $p=13$ $10^{\frac {13-1}{2}}=10^{6}\equiv 1{\pmod {13}}$

Vaihe 1: niin , . ${\displaystyle p-1=12=3\cdot 2^{2))$ $Q=3$ $S=2$
Vaihe 2: Ota - neliöllinen ei-jäännös (koska (jälleen Eulerin kriteerin mukaan)). Laitetaan $z=2$ $2^{\frac {13-1}{2}}=-1{\pmod {13}}$ $c=2^{3}\equiv 8{\pmod {13)).$
Vaihe 3: $R=10^{2}\equiv -4,\;t\equiv 10^{3}\equiv -1{\pmod {13)),M=2.$
Vaihe 4: Aloita silmukka: niin yksinkertaisesti sanottuna . $t\not \equiv 1{\pmod {13}}$ $0<i<2$ $i=1$
- Anna sitten . $b\equiv 8^{2^{2-1-1}}\equiv 8{\pmod {13}}$ $b^{2}\equiv 8^{2}\equiv -1{\pmod {13}}$
- Laitetaan , ja . $R=-4\cdot 8\equiv 7{\pmod {13}}$ $t\equiv -1\cdot -1\equiv 1{\pmod {13))$ $M=1$
- Käynnistä silmukka uudelleen, koska silmukka on valmis, saamme $t\equiv 1{\pmod {13}}$ $R\equiv 7{\pmod {13)).$

Koska , täältä saamme tietysti 2 vertailuratkaisua. $7^{2}=49\equiv 10{\pmod {13}}$ $(\pm 7)^{2}\equiv 6^{2}\equiv 10{\pmod {13))$

Todiste

Anna . Anna nyt ja huomioi se . Viimeinen vertailu pysyy totta algoritmin pääsilmukan jokaisen iteraation jälkeen. Jos jossain vaiheessa , niin algoritmi päättyy . $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}}$

Jos , Harkitse neliöllistä ei- jäännösmoduulia . Olkoon , sitten ja , mikä osoittaa, että järjestys on . $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}$

Vastaavasti saamme sen , joten järjestys jakautuu , joten järjestys on . Koska on neliö modulo , niin se on myös neliö, mikä tarkoittaa, että . $t^{2^{S}}\equiv 1{\pmod {p}}$ $t$ $2^{S}$ $t$ $2^{S'}$ $n$ $s$ $t\equiv n^{Q}{\pmod {p}}$ $S'<S$

Oletetaan, että ja , ja . Kuten ennenkin, se säilytetään; kuitenkin tässä rakentamisessa sekä ja on järjestys . Tästä seuraa, että on järjestys , missä . $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'$

Jos , niin , ja algoritmi pysähtyy palauttaen . Muussa tapauksessa käynnistetään silmukka uudelleen samanlaisilla määritelmillä , kunnes saadaan , joka on yhtä suuri kuin 0. Koska naturalien sekvenssi on tiukasti pienenevä, algoritmi päättyy. $S''=0$ $t'\equiv 1{\pmod {p}}$ $R\equiv \pm r'{\pmod {p}}$ $b',r'',c'',t''$ $S^{(j)'}$ $S^{(j)'}$

Algoritmin nopeus

Tonelli-Shanks-algoritmi toimii keskimäärin (kaikilla mahdollisilla syötteillä (neliölliset jäännökset ja ei-jäännökset))

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

modulo kertolasku, jossa on binääriesityksen numeroiden lukumäärä ja binääriesityksen numeroiden lukumäärä . Jos vaadittu neliöllinen ei-jäännös lasketaan tarkistamalla satunnaisesti valitusta , onko se neliöllinen ei-jäännös, niin tämä vaatii keskimäärin kahden Legendre-symbolin laskemisen [2] . Kaksi laskettujen Legendre-symbolien keskimääräisenä lukumääränä selitetään seuraavasti: todennäköisyys, että se on neliöllinen jäännös on - todennäköisyys on suurempi kuin puolet, joten keskimäärin kestää noin kaksi tarkistusta, onko se neliöllinen jäännös. $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$

Tämä osoittaa, että käytännössä Tonelli-Shanks-algoritmi toimii erittäin hyvin, jos moduuli on satunnainen, eli kun se ei ole erityisen suuri suhteessa binääriesityksen numeroiden määrään . Cipolla-algoritmi toimii paremmin kuin Tonelli-Shanks-algoritmi silloin ja vain jos . Jos sen sijaan Sutherlandin algoritmia käytetään diskreetin logaritmin suorittamiseen 2- Sylow-aliryhmälle , tämä sallii lausekkeen kertolaskujen määrän korvaamisen asymptoottisesti rajatulla arvolla [3] . Todellakin, riittää löytää sellainen , joka tyydyttää silloinkin (huomaa, että se on 2:n kerrannainen, koska se on neliöllinen jäännös). $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$

Algoritmi vaatii neliöllisen ei-jäännöksen löytämisen . Tällä hetkellä ei ole olemassa determinististä algoritmia , joka löytäisi sellaisen pituuden polynomiajassa . Jos yleistetty Riemannin hypoteesi kuitenkin pitää paikkansa, on olemassa neliöllinen ei-jäännös , [4] , joka on helppo löytää tarkistamalla määrätyissä rajoissa polynomiajassa . Tämä on tietysti pahimman tapauksen arvio, koska, kuten yllä on esitetty, riittää, että tarkastetaan keskimäärin 2 satunnaista neliöllisen ei-jäämän löytämiseksi. $z$ $s$ $z$ ${\displaystyle z<2\ln ^{2}{p))$ $z$ $z$

Sovellus

Tonelli-Shanks-algoritmia voidaan käyttää pisteiden etsimiseen jäännöskentän elliptisellä käyrällä . Sitä voidaan käyttää myös laskelmiin Rabinin salausjärjestelmässä .

Yleistys

Tonelli-Shanks-algoritmi voidaan yleistää mihin tahansa sykliseen ryhmään (sen sijaan ) ja :nnen asteen juurien löytämiseen mielivaltaiselle luonnolliselle , erityisesti : nnen asteen juurien laskemiseen äärellisessä kentässä [5] . ${\displaystyle \mathbb {F} _{p}^{\times ))$ $k$ $k$ $k$

Jos samassa syklisessä ryhmässä on useita laskettavia neliöjuuria, jotka eivät ole kovin suuria, voidaan algoritmin parantamiseksi ja yksinkertaistamiseksi ja sen nopeuden lisäämiseksi tehdä taulukko elementtien neliöiden neliöjuurista seuraavasti: $S$

Erottelemme kahden tehot : Olkoon sellainen, että , on outoa. $p-1$ $Q,S$ $p-1=2^{S}Q$ $K$
Anna . $R\equiv n^{\frac {Q+1}{2)){\pmod {p)),t\equiv n^{Q}\equiv R^{2}/n{\pmod {p }}$
Etsitään juuri suhdetaulukosta ja laitetaan $b$ $b^{2}\equiv t$ $R\equiv R/b$
Paluu . $R$

Muistiinpanot

↑ Oded Goldreich, Computational monimutkaisuus: käsitteellinen näkökulma , Cambridge University Press, 2008, s. 588.
↑ Gonzalo Tornaria , Neliöjuuret modulo p (linkki ei saatavilla) , sivu 2.
↑ Sutherland, Andrew V. (2011), Rakenteen laskenta ja diskreetit logaritmit äärellisissä Abelin p -ryhmissä , Mathematics of Computation , osa 80: 477–500 , DOI 10.1090/s0025-57235-10-20
↑ Bach, Eric (1990), Primaliteettitestauksen ja niihin liittyvien ongelmien eksplisiittiset rajat , Mathematics of Computation osa 55 (191): 355–380 , DOI 10.2307/2008811
↑ LM Adleman, K. Manders, G. Miller: 1977, "On take roots in finite fields". Julkaisussa: 18th IEEE Symposium on Foundations of Computer Science. s. 175-177.

Kirjallisuus

Nesterenko A. Yu. Lukuteoreettiset menetelmät kryptografiassa. - Moskova. - 2012. - ISBN 978-5-94506-320-4 .
Ishmukhametov Sh. T. Faktorisointimenetelmät luonnollisille lukuille. - Kazanin yliopisto. – 2011.
Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery . Johdatus lukuteoriaan. – 5. - Wiley, 1991. - ISBN 0-471-62546-9 .
Daniel Shanks. Viiden numeron teoreettiset algoritmit. Toisen Manitoban numeerisen matematiikan konferenssin julkaisut. 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 - Matematiikka 115: RESSOL-algoritmi .

Linkit

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

Lukuteoreettiset algoritmit
Yksinkertaisuustestit	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saksi Nightingale - Strassen
Alkulukujen löytäminen	Iterointi jakajien yli Eratosthenesin seula Atkinin seula Seula Sundarama
Faktorisointi	Iterointi jakajien yli Fermat menetelmä p −1 Pollardin menetelmä Pollardin ρ-algoritmi Lehmannin menetelmä Elliptisen käyrän menetelmä (Lenstran algoritmi) Dixonin algoritmi Neliömäinen seula
Diskreetti logaritmi	Gelfond-Shanks -algoritmi Polig-Hellman-algoritmi Pollardin ρ-menetelmä Pollardin kenguru-algoritmi Adlemanin algoritmi COS-algoritmi
GCD:n löytäminen	Eukleideen algoritmi Kehittynyt algoritmi Binäärinen algoritmi
Modulo-aritmetiikka	Montgomeryn algoritmi Kiinan jäännöslause
Lukujen kerto- ja jakolasku	Karatsuba-algoritmi Toom-Cook-algoritmi Schönhage-Strassen-algoritmi Fuhrer-algoritmi Harvey-van der Hoeven-algoritmi Burnickel-Ziegler-algoritmi
Neliöjuuren laskeminen	Tonelli-Shanks-algoritmi Berlekamp-Rabin-algoritmi