Tonelli-Shanks algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. március 7-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A Tonelli-Shanks algoritmus (Shanks RESSOL algoritmusnak nevezte) a moduláris aritmetikához tartozik, és összehasonlítások megoldására szolgál.

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

ahol a másodfokú maradék modulo , és egy páratlan prímszám . $n$ $p$ $p$

A Tonelli-Shanks algoritmus nem használható összetett modulokhoz; négyzetgyökök keresése modulo kompozit számításilag egyenértékű a faktorizációval [1] .

Ennek az algoritmusnak egy egyenértékű, de valamivel bonyolultabb változatát Alberto Tonelli fejlesztette ki 1891-ben. Az itt tárgyalt algoritmus verzióját Daniel Shanks önállóan fejlesztette ki 1973-ban.

Algoritmus

Bemeneti adatok : — páratlan prímszám, — egész szám , amely egy négyzetes maradék modulo , más szóval , ahol a Legendre szimbólum . $p$ $n$ $p$ $\left({\frac {n}{p}}\right)=1$ $\left(\frac{a}{b}\right)$

Az algoritmus eredménye : olyan maradék , amely kielégíti az összehasonlítást . $R$ $R^{2}\equiv n{\pmod {p}}$

Kettő hatványait választjuk ki -ból , azaz legyen , ahol páratlan, . Figyeljük meg, hogy ha , akkor a megoldást a képlet határozza meg . Ezután feltételezzük . $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$
Kiválasztunk egy tetszőleges másodfokú nemmaradékot , azaz a Legendre szimbólumot , és beállítjuk a . $z$ $\left({\frac {z}{p}}\right)=-1$ $c\equiv z^{Q}{\pmod {p))$
Hadd is $R\equiv n^{\frac {Q+1}{2}}{\pmod {p)),$ $t\equiv n^{Q}{\pmod {p)),$ $M=S.$
Végrehajtjuk a ciklust:
1. Ha , akkor az algoritmus visszatér . $t\equiv 1{\pmod {p}}$ $R$
2. Ellenkező esetben a ciklusban megtaláljuk a legkisebb , -t , így a négyzetesítés iterálásával. $én$ $0<i<M$ $t^{2^{i}}\equiv 1{\pmod {p}}$
3. Hagyjuk , és térjünk vissza a ciklus elejére. $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$

Az összehasonlító megoldás megtalálása után a második összehasonlító megoldást a következőképpen találjuk meg . $R$ $pR$

Példa

Tegyünk egy összehasonlítást . páratlan, és mivel , 10 egy másodfokú maradék az Euler-kritérium szerint . $x^{2}\equiv 10{\pmod {13}}$ $p=13$ $10^{\frac {13-1}{2}}=10^{6}\equiv 1{\pmod {13}}$

1. lépés: tehát , . ${\displaystyle p-1=12=3\cdot 2^{2))$ $Q=3$ $S=2$
2. lépés: Vegyük – másodfokú nem-maradék (mert (ismét Euler-kritérium szerint)). Tegyük fel $z=2$ $2^{\frac {13-1}{2}}=-1{\pmod {13}}$ $c=2^{3}\equiv 8{\pmod {13)).$
3. lépés: $R=10^{2}\equiv -4,\;t\equiv 10^{3}\equiv -1{\pmod {13)),M=2.$
4. lépés: Indítsa el a ciklust: tehát , egyszerűen fogalmazva . $t\not \equiv 1{\pmod {13}}$ $0<i<2$ $i=1$
- Akkor hagyd . $b\equiv 8^{2^{2-1-1}}\equiv 8{\pmod {13}}$ $b^{2}\equiv 8^{2}\equiv -1{\pmod {13}}$
- Tegyük fel , , és . $R=-4\cdot 8\equiv 7{\pmod {13}}$ $t\equiv -1\cdot -1\equiv 1{\pmod {13))$ $M=1$
- Indítsuk újra a ciklust, mivel a ciklus befejeződött, megkapjuk $t\equiv 1{\pmod {13}}$ $R\equiv 7{\pmod {13)).$

Mivel nyilvánvalóan innen 2 összehasonlító megoldást kapunk. $7^{2}=49\equiv 10{\pmod {13}}$ $(\pm 7)^{2}\equiv 6^{2}\equiv 10{\pmod {13))$

Bizonyítás

Hadd . Most pedig jegyezd meg . Az utolsó összehasonlítás igaz marad az algoritmus fő hurkának minden iterációja után. Ha egy ponton , akkor az algoritmus a -val fejeződik be . $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}}$

Ha , akkor vegyük figyelembe a másodfokú nem-maradék modulo . Legyen , majd és , ami azt mutatja, hogy a sorrend . $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}$

Hasonlóképpen azt kapjuk, hogy , tehát a sorrend osztódik , tehát a sorrend . Mivel egy négyzet modulo , akkor ez is négyzet, ami azt jelenti, hogy . $t^{2^{S}}\equiv 1{\pmod {p}}$ $t$ $2^{S}$ $t$ $2^{S'}$ $n$ $p$ $t\equiv n^{Q}{\pmod {p}}$ $S'<S$

Tegyük fel, hogy és , és . A korábbiakhoz hasonlóan megőrzik; azonban ebben a konstrukcióban mindkét és rendje van . Ebből következik a sorrend , ahol . $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'$

Ha , akkor , és az algoritmus leáll, visszatérve . Ellenkező esetben hasonló definíciókkal indítjuk újra a ciklust, amíg 0-t nem kapunk. Mivel a természetesek sorozata szigorúan csökken, az algoritmus véget ér. $S''=0$ $t'\equiv 1{\pmod {p}}$ $R\equiv \pm r'{\pmod {p}}$ $b',r'',c'',t''$ $S^{(j)'}$ $S^{(j)'}$

Algoritmus sebessége

A Tonelli-Shanks algoritmus átlagosan teljesít (minden lehetséges bemeneten (négyzetes maradékok és nem maradékok))

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

modulo szorzások, ahol a számjegyek száma a bináris reprezentációban , és az egyesek száma a bináris reprezentációban . Ha a szükséges másodfokú nem-maradékot úgy számítjuk ki, hogy egy véletlenszerűen kiválasztott nem-maradékot másodlagos nem-maradékról van szó, akkor ehhez átlagosan két Legendre szimbólum kiszámítása szükséges [2] . A kiszámított Legendre szimbólumok átlagos számaként kettőt a következőképpen magyarázzuk: annak a valószínűsége, hogy négyzetes maradékról van szó - a valószínűsége nagyobb, mint a fele, így átlagosan körülbelül két ellenőrzésre lesz szükség, hogy másodfokú maradékról van-e szó. $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$

Ez azt mutatja, hogy a gyakorlatban a Tonelli-Shanks algoritmus nagyon jól fog működni, ha a modulus véletlenszerű, vagyis ha nem különösebben nagy a bináris reprezentáció számjegyeinek számához képest . A Cipolla algoritmus akkor és csak akkor teljesít jobban, mint a Tonelli-Shanks algoritmus . Ha azonban ehelyett Sutherland algoritmusát használjuk a diszkrét logaritmus végrehajtására a 2- Sylow alcsoporton , ez lehetővé teszi, hogy a kifejezésben a szorzások számát egy aszimptotikusan korlátos értékkel helyettesítsük [3] . Valóban, elég találni egy olyat, amely még akkor is kielégít (megjegyzendő, hogy ez 2 többszöröse, mivel ez egy másodfokú maradék). $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$

Az algoritmus megköveteli egy másodfokú nem maradékot . Jelenleg nincs olyan determinisztikus algoritmus , amely a hosszúságú polinomidőben megtalálná ezt . Ha azonban igaz az általánosított Riemann-hipotézis , akkor van egy négyzetes nem-maradék , [4] , amelyet könnyű megtalálni a polinomidőben megadott határokon belüli ellenőrzéssel . Ez természetesen a legrosszabb eset becslése, mivel, mint fentebb látható, elegendő átlagosan 2 véletlenszerű ellenőrzést ellenőrizni, hogy négyzetes nem-maradékot találjunk. $z$ $p$ $z$ ${\displaystyle z<2\ln ^{2}{p))$ $z$ $z$

Alkalmazás

A Tonelli-Shanks algoritmus használható egy maradékmező feletti elliptikus görbén lévő pontok keresésére . Használható számításokhoz a Rabin kriptorendszerben is .

Általánosítás

A Tonelli-Shanks algoritmus általánosítható tetszőleges ciklikus csoportra (a helyett ) és egy tetszőleges természetes th-edik fok gyökeinek megtalálására , különösen a th-edik fok gyökeinek kiszámítására egy véges mezőben [5] . $\mathbb {F} _{p}^{\times }$ $k$ $k$ $k$

Ha ugyanabban a ciklikus csoportban sok és nem túl nagy négyzetgyök van, akkor az algoritmus javítása és egyszerűsítése, valamint sebességének növelése érdekében az elemek négyzetgyökeinek táblázata elkészíthető a következőképpen: $S$

Kettő hatványait különítjük el a következőben: legyen olyan, hogy , legyen páratlan. $p-1$ $Q,S$ $p-1=2^{S}Q$ $K$
Hadd . $R\equiv n^{\frac {Q+1}{2)){\pmod {p)),t\equiv n^{Q}\equiv R^{2}/n{\pmod {p }}$
Keressük meg a gyökeret az aránytáblázatból, és tegyük $b$ $b^{2}\equiv t$ $R\equiv R/b$
Vissza . $R$

Jegyzetek

↑ Oded Goldreich, Számítási komplexitás: fogalmi perspektíva , Cambridge University Press, 2008, p. 588.
↑ Gonzalo Tornaria , Négyzetgyökök modulo p (nem elérhető link) , 2. oldal.
↑ Sutherland, Andrew V. (2011), Struktúra számítás és diszkrét logaritmusok véges Abel- p - csoportokban , Mathematics of Computation 80. kötet: 477–500 , DOI 10.1090/s0025-57235-10-20
↑ Bach, Eric (1990), Explicit bounds for primality testing and related problems , Mathematics of Computation 55 (191): 355–380 , DOI 10.2307/2008811
↑ LM Adleman, K. Manders, G. Miller: 1977, "A véges mezők gyökerezéséről". In: 18. IEEE Symposium on Foundations of Computer Science. p. 175–177.

Irodalom

Nesterenko A. Yu. Számelméleti módszerek a kriptográfiában. - Moszkva. - 2012. - ISBN 978-5-94506-320-4 .
Ishmukhametov Sh. T. Faktorizációs módszerek természetes számokra. — Kazany Egyetem. – 2011.
Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery . Bevezetés a számelméletbe. — 5. - Wiley, 1991. - ISBN 0-471-62546-9 .
Daniel Shanks. Öt szám elméleti algoritmusok. 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 - Matematika 115: A RESSOL algoritmus .

Linkek

Python implementáció http://eli.thegreenplace.net/2009/03/07/computing-modular-square-roots-in-python

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus