Varren neliömuotomenetelmä

Shanksin neliömuotojen menetelmä on neliömuotojen käyttöön perustuva kokonaislukujen faktorointimenetelmä , jonka Daniel Shanks [1] kehitti vuonna 1975 Fermatin faktorointimenetelmän kehityksenä .

32-bittisissä tietokoneissa tähän menetelmään perustuvat algoritmit ovat kiistattomia johtajia lukujen välillä - ja todennäköisesti pysyvät sellaisina. [2] Tämä algoritmi voi jakaa melkein minkä tahansa 18-numeroisen yhdistelmäluvun alle millisekunnissa. Algoritmi on erittäin yksinkertainen, kaunis ja tehokas. Lisäksi tähän algoritmiin perustuvia menetelmiä käytetään apuvälineenä suurten lukujen jakajien, kuten Fermat-lukujen , laajentamisessa . $10^{{10}}$ $10^{18}$

Historia

Algoritmin toinen nimi on SQUFOF ( englannin lyhenne on SQUARE FORm Factorization), joka tarkoittaa neliömuotoista tekijöitä . Tämä lähestymistapa on ollut varsin menestyksekäs vuosien varrella, ja sen seurauksena kirjallisuudesta löytyy tästä aiheesta useita erilaisia muunnelmia ja toteutuksia. [3] Useimmat menetelmät ovat monimutkaisia ja hämmentäviä, varsinkin kun menetelmä on toteutettava tietokoneella. Tämän seurauksena monet algoritmien muunnelmat eivät sovellu toteutukseen. Vuonna 1975 Daniel Shanks ehdotti kuitenkin algoritmin luomista, joka voidaan toteuttaa ja käyttää paitsi tietokoneessa myös yksinkertaisessa matkapuhelimessa.

Vaikka Shanks on kuvannut muita algoritmeja kokonaislukujen tekijöihin jakamiseen, hän ei ole julkaissut mitään SQUFOF-sivustolla. Hän piti aiheesta luentoja ja selitti menetelmänsä perusolemuksen melko pienelle ihmisjoukolle. Joissakin muiden tutkijoiden kirjoituksissa [4] [3] [5] [6] käsiteltiin algoritmia, mutta yksikään niistä ei sisällä yksityiskohtaista analyysiä. On myös mielenkiintoista, että Shanks tekee menetelmässään melkoisen määrän olettamuksia [7] , jotka valitettavasti jäivät ilman todisteita. Julkaisussa [8] esitetään joidenkin kokeiden tulokset, jotka osoittavat, että monet olettamukset ovat paikoillaan. Lopulta Shanks pystyi luomaan SQUFOFin näiden yksinkertaistavien oletusten perusteella.

Apumääritelmät

Jotta ymmärtäisimme, kuinka tämä algoritmi toteutetaan, on tarpeen tietää vähimmäistiedot tässä menetelmässä käytetyistä matemaattisista objekteista, nimittäin neliömuodoista . Binäärinen neliömuoto on polynomi kahdessa muuttujassa ja : $x$ $y$

f(x,y)=ax^{2}+bxy+cy^{2}={\begin{pmatrix}x&y\end{pmatrix}}{\begin{pmatrix}a&b\\0&c\end{ pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}.

Shanks - menetelmä käyttää vain epämääräisiä muotoja . Tarkoitamme kvadraattisen muodon erottajaa . Sanomme, että neliömuoto edustaa kokonaislukua , jos on sellaisia kokonaislukuja, että yhtälö on tosi: . Jos yhtälö on tosi , niin esitystä kutsutaan primitiiviseksi . $\Delta$ $f$ $m\in \mathbb {Z}$ $x_{0},y_{0}$ ${\displaystyle f(x_{0},y_{0})=ax_{0}^{2}+bx_{0}y_{0}+cy_{0}^{2))$ $\gcd(x_{0},y_{0})=1$

Minkä tahansa määrittelemättömän neliömuodon kohdalla pelkistysoperaattori voidaan määritellä seuraavasti: $f={\begin{pmatrix}a,&b,&c\end{pmatrix}}$

\rho {\begin{pmatrix}a,&b,&c\end{pmatrix}}={\begin{pmatrix}c,&r(-b,c),&{\frac {r(-b,c )^{2}-\Delta }{4c}}\end{pmatrix}}

, jossa määritellään kokonaislukuna , joka määritellään yksiselitteisesti ehdoilla: [8]

r(-b,c)

r

$r+b\equiv 0\mod (2c)$
$-|c|<r<|c|,\quad if\quad {\sqrt {\Delta }}<|c|$
${\sqrt {\Delta }}-2|c|<r<{\sqrt {\Delta }},\quad if\quad |c|<{\sqrt {\Delta }}$

Tulos, kun operaattoria käytetään lomakkeeseen kerran, kirjoitetaan muodossa . Operaattori määritellään myös: $\rho$ $f$ $n$ $\rho ^{n}(f)$ $\rho ^{-1}$

\rho ^{-1}{\begin{pmatrix}a,&b,&c\end{pmatrix}}={\begin{pmatrix}{\frac {r(-b,c)^{2}- \Delta }{4c}},&r(-b,c),&c\end{pmatrix}}

, jossa määritellään samalla tavalla kuin edellisessä tapauksessa. Huomaa, että operaattoreiden soveltamisen seurauksena neliölliseen muotoon , jossa on diskriminantti , tuloksena olevilla neliömuodoilla on myös diskriminantti .

r(-b,c)

\rho ^{-1}

\rho

f={\begin{pmatrix}a,&b,&c\end{pmatrix}}

\Delta

\Delta

Carl Gauss löysi menetelmän tätä muotoa vastaavan pelkistetyn muodon saamiseksi, ja se koostuu pelkistysoperaattorin peräkkäisestä soveltamisesta, kunnes se pelkistyy. $g=\rho (f)$ $f$

Lause.

Jokainen muoto vastaa jotakin pelkistettyä muotoa, ja mikä tahansa pelkistetty muoto on yhtä suuri kuin jokin positiivinen muoto . Jos - pienennetään, se myös pienenee. $f$ $f$ $\rho ^{k}(f)$ $k$ $f$ $\rho (f)$

Lisäksi kaikkien neliömuotojen operaatioiden selkeää ymmärtämistä varten tarvitsemme neliön, vierekkäisten ja moniselitteisten neliömuotojen käsitteet

Vaihtoehdot

Shanks-menetelmän ideana on verrata hajotettavaa lukua toisen asteen binäärimuodolla diskriminantilla , jolla sitten suoritetaan sarja ekvivalentteja muunnoksia ja siirtyminen muodosta moniselitteiseen muotoon . Sitten tulee jakaja . $n$ $f$ $D=4n$ $f$ ${\näyttötyyli (a',b',c')}$ $\gcd(a',b')$ $n$

Ensimmäinen variantti toimii tietyn negatiivisen diskriminantin positiivisten ja määrällisten binääristen neliömuotojen kanssa, ja muotoluokkaryhmästä se löytää ambig-muodon , joka antaa diskriminantin faktorisoinnin. Ensimmäisen vaihtoehdon monimutkaisuus riippuu laajennetun Riemannin hypoteesin totuudesta . [9] $O(n^{1/5+\varepsilon })$

Toinen variantti on SQUFOF, joka käyttää luokkaryhmää binäärisiä neliömuotoja, joissa on positiivinen diskriminantti. Se löytää myös ambig-muodon ja tekijöihin erottavan tekijän. SQUFOF:n monimutkaisuus vastaa aritmeettisia operaatioita; algoritmi toimii kokonaislukujen kanssa, jotka eivät ylitä . Eksponentiaalisen monimutkaisuuden omaavien faktorointialgoritmien joukossa SQUFOF:ia pidetään yhtenä tehokkaimmista. [9] $O(n^{1/4+\varepsilon })$ $2{\sqrt {n))$

Lähentymispisteet

Shanksin itsensä tekemien laskelmien mukaan algoritmin ensimmäisen ja toisen syklin iteraatioiden lukumäärä määräytyy luvun tekijöiden lukumäärän mukaan ja on suunnilleen yhtä suuri: $w$ $n$

${\frac {C}{2^{w}-2}}\cdot n^{1/4},$

jossa on vakio, joka on suunnilleen 2,4 ensimmäisen iteraatiojakson aikana. [kymmenen] $C$

Algoritmin kuvaus

Tarkemmin sanottuna algoritmi voidaan kirjoittaa seuraavasti: [11]

Syöte: Pariton yhdistelmäluku kertoimiin. Jos korvaamme Now'lla Viimeinen ominaisuus on välttämätön, jotta neliömuodon determinantti olisi perustava, mikä varmistaa menetelmän konvergenssin. $n$ $n\!\!\!\mod 4=1,$ $n$ $2n.$ $n\!\!\!\mod 4=2;3.$

Tulos: Ei-triviaali jakaja . $n$

1. Määrittele alkuperäinen neliömuoto , jossa erotteleva , jossa .

f=(1,2b,b^{2}-D)

D=4n

b={\mathcal {b}}{\sqrt {n}}{\mathcal {c}}

2. Suoritetaan pienennyssykliä, kunnes muoto muuttuu neliömäiseksi.

f=\rho (f)

f

3. Laske neliöjuuri

{\displaystyle f:~g=(a^{\prime },b^{\prime },c^{\prime })=f^{1/2))

4. Suoritetaan vähennyssykliä, kunnes toisen kertoimen arvo stabiloituu . Tämän silmukan iteraatioiden lukumäärän tulisi olla suunnilleen puolet ensimmäisen silmukan iteraatioiden lukumäärästä. Viimeinen arvo antaa luvun jakajan (mahdollisesti triviaali).

p=\rho (g)

b_{i+1}'=b_{i}'

m

a^{\prime }

n

Algoritmin toteutus

Nyt kuvailemme tietokoneella toteutuksen algoritmia. [11] Huomaa, että vaikka algoritmin teoreettinen osa liittyy toisen asteen muotojen ekvivalenttisiin muunnoksiin, algoritmin käytännön osa perustuu jatkuvan murtoluvun kertoimien laskemiseen ilman muotoja. Jokainen silmukan iteraatio vastaa yhtä toimintoa, jossa vähennysoperaattori sovelletaan vastaavaan muotoon. Tarvittaessa voit palauttaa vastaavat lomakkeet käyttämällä kaavoja: $P,Q,r$ $f_{k}=(a_{k},b_{k},c_{k})$ $(a_{k},b_{k},c_{k})=((-1)^{k-1}Q_{k-1},2P_{k},(-1)^{k }Q_{k})$

Syöttö: Yhdistelmänumero $n$

Tulos: Ei-triviaali jakaja $n$

Algoritmin alustus.
- Katsotaan, onko se täydellinen neliö. Jos kyllä, laske ja lopeta laskenta. Muussa tapauksessa siirrytään seuraavaan kohtaan. $n$ $d={\sqrt {n)),$
- Jos sitten korvaamme sanalla Define $n\equiv 1(mod4),$ $n$ $2n.$ $D=4n,~q_{0}={\mathcal {b}}{\sqrt {D}}{\mathcal {c}}.$
- Määritä parametrien alkuarvot $P,Q,r:$

$P_{0}=0,~Q_{0}=1,~r_{0}=P_{1}={\mathcal {b}}{\sqrt {n}}{\mathcal {c}} ,~Q_{1}=n-r_{0}^{2},r_{1}={\mathcal {b}}2r_{0}/Q_{1}{\mathcal {c}}.$

Ensimmäinen sykli
- $P_{k}=r_{k-1}\cdot Q_{k-1}-P_{k-1},~Q_{k}=Q_{k-2}+(P_{k-1} -P_{k})\cdot r_{k-1},r_{k}={\mathcal {b}}{\frac {P_{k}+{\mathcal {b}}{\sqrt {n}} {\mathcal {c}}}{Q_{k}}}{\mathcal {c}},~k\geq 2.$
- Jatkamme kertoimien laskemista, kunnes löydämme Q_k, joka on täydellinen neliö. Tämän pitäisi tapahtua jossain Let for kokonaisluku Siirrytään seuraavaan sykliin. ${\displaystyle P_{k},~Q_{k}~r_{k))$ $k.$ $Q_{k}=d^{2}$ $d>0.$

Toinen sykli.
- aloitetaan uusien parametrien laskentasykli.Toisen syklin toteutuskaavat pysyvät samoina kuin ennenkin. Vain parametrien alkuarvot muuttuvat $P_{j}^{\prime },~Q_{j}^{\prime },~r_{j}^{\prime }.$ $P^{\prime },~Q^{\prime },~r^{\prime }:$
- $P_{0}^{\prime }=-P_{k},~Q_{0}^{\prime }=d,~r_{0}^{\prime }={\mathcal {b)) {\frac {P_{0}^{\prime }+{\mathcal {b}}{\sqrt {n}}{\mathcal {c}}}{Q_{0}^{\prime }}}{\ matemaattinen {c)),~P_{1}^{\prime }=r_{0}^{\prime }\cdot Q_{0}^{\prime }-P_{0}^{\prime },~Q_ {1}^{\prime }=(N-P_{1}^{\prime 2})/Q_{0}^{\prime }.$
- Laskemista tulee jatkaa, kunnes kaksi peräkkäistä arvoa ovat yhtä suuret. Sitten arvo antaa luvun halutun jakajan.Shanks- algoritmin kuvaus on valmis. ${\displaystyle P_{j}^{\prime },~P_{j+1}^{\prime ))$ $Q_{j}$ $n.$

Kuten jo mainittiin, tämä ei ole tämän algoritmin ainoa toteutus. Löydät myös algoritmin toteutuksen täältä [8]

Esimerkki luvun tekijöistä

Käytämme tätä menetelmää luvun kertomiseen [8] $N=22117019$

Sykli #1
$F_{i}$
$i$	$(-1)^{i-1}Q_{i-1}$	$2\cdot P_{i}$	$(-1)^{i}Q_{i}$
$0$	$-8215$	$2\cdot 4702$	$yksi$
$yksi$	$yksi$	$2\cdot 4702$	$-8215$
$2$	$-8215$	$2\cdot 3513$	$1190$
$3$	$1190$	$2\cdot 3627$	${\displaystyle-7531}$
$neljä$	${\displaystyle-7531}$	$2\cdot 3904$	$913$
$5$	$913$	$2\cdot 4313$	$-3850$
$6$	$-3850$	$2\cdot 3387$	$2765$
$7$	$2765$	$2\cdot 2143$	${\displaystyle-6338}$
$kahdeksan$	${\displaystyle-6338}$	$2\cdot 4195$	$713$
$9$	$713$	$2\cdot 4361$	$-4346$
$kymmenen$	$-4346$	$2\cdot 4331$	$773$
$yksitoista$	$773$	$2\cdot 4172$	$-6095$
$12$	$-6095$	$2\cdot 1923$	$3022$
$13$	$3022$	$2\cdot 4121$	${\displaystyle-1699}$
$neljätoista$	${\displaystyle-1699}$	$2\cdot 4374$	$1757$
$viisitoista$	$1757$	$2\cdot 4411$	${\displaystyle-1514}$
$16$	${\displaystyle-1514}$	$2\cdot 4673$	$185$
$17$	$185$	$2\cdot 4577$	${\displaystyle-6314}$
$kahdeksantoista$	${\displaystyle-6314}$	$2\cdot 1737$	$3025$

Jakso #2
$G_{i}$
$i$	$(-1)^{i-1}Q_{i-1}^{\prime }$	${\displaystyle 2\cdot P_{i}^{\prime ))$	$(-1)^{i}Q_{i}^{\prime }$
$0$	$-55$	$2\cdot 4652$	$8653$
$yksi$	$8653$	$2\cdot 4001$	$-706$
$2$	$-706$	$2\cdot 4471$	$3013$
$3$	$3013$	$2\cdot 4568$	$-415$
$neljä$	$-415$	$2\cdot 4562$	$3145$
$5$	$3145$	$2\cdot 1728$	${\displaystyle-6083}$
$6$	${\displaystyle-6083}$	$2\cdot 4355$	$518$
$7$	$518$	$2\cdot 4451$	$-4451$
$kahdeksan$	$-4451$	$2\cdot 4451$	$518$

Nyt voit nähdä toisessa jaksossa, että tästä syystä numero $P_{7}^{\prime }=P_{8}^{\prime }.$ $N=22117019=4451\cdot 4969.$

Sovellukset

Tätä algoritmia käytetään monissa NFS- ja QS -toteutuksissa pienten apulukujen tekijöihin laskemiseen, joita syntyy, kun otetaan huomioon suuri kokonaisluku. Joka tapauksessa SQUFOF:ia käytetään pääasiassa auttaja-algoritmina tehokkaammissa tekijöiden jakamisalgoritmeissa, ja siksi SQUFOF:ia käytetään yleensä sellaisten vaatimattomien lukujen kertoiluun, joissa ei ole pieniä alkujakajia. Tällaiset luvut ovat yleensä muutaman eri alkuluvun tulo. [8] .

Muistiinpanot

↑ Lisätietoja tämän menetelmän historiasta ja sen yhteydestä jatkuvaan murtolukumenetelmään on Goverin ja Wagstaffin artikkelissa (J. Gover, SS Wagstaff).
↑ Yike Guo, 1999 , High Performance Data Mining: Skaalausalgoritmit, sovellukset ja järjestelmät.
↑ 1 2 Hans Riesel, 1994 , Alkuluvut ja tietokonemenetelmät faktorointiin. Birkhauser, toinen painos.
↑ Henri Cohen, 1996 , Laskennallisen algebrallisen lukuteorian kurssi.
↑ D.A. Buell, 1989 , Binary Quadratic Forms.
↑ Samuel S. Wagstaff Jr., 2003 , Numeroteoreettisten salausten kryptaanalyysi.
↑ Esimerkiksi ruudussa SQUARE FORM FACTORIZATION JASON E. GOWER JA SAMUEL S. WAGSTAFF, JR. Oletus 4.12. sivulla 20, oletus 4.5 sivulla 16, myös algoritmien monimutkaisuuslauseita todettaessa jne.
↑ 1 2 3 4 5 NELIÖMUOTOTEKOITUS, 2003 , NELIÖMUOTOTEKOITUS.
↑ 1 2 Vasilenko, 2003 , Numeroteoreettiset algoritmit kryptografiassa.
↑ Ishmukhametov, 2011 , Faktorisointimenetelmät luonnollisille lukuille: Oppikirja.
↑ 1 2 Ishmukhametov, 2011 , Faktorisointimenetelmät luonnollisille lukuille: Oppikirja s. 79-80.

Kirjallisuus

Vasilenko O. N. Lukuteoreettiset algoritmit kryptografiassa . - Moskova: MTSNMO, 2003. - S. 75 - 76. - 328 s. — ISBN 5-94057-103-4 . Arkistoitu 27. tammikuuta 2007 Wayback Machinessa
Ishmukhametov Sh. T. Luonnollisten lukujen kertolaskumenetelmät: Oppikirja . - Kazan: Kazanin yliopisto, 2011. - S. 74 - 82. - 190 s.
D.A. Buell. Binaariset neliömuodot (uuspr.) . - New York: Springer-Verlag , 1989. - S. 197 - 199. - 247 s. - ISBN 0-387-97037-1 .
Hans Riesel. Alkuluvut ja tietokonemenetelmät faktorointiin. Birkhauser, toinen painos . - Ruotsi: Birkhauser, 1994. - P. s. 186 - 192. - ISBN 978-0-8176-8297-2 .
Henri Cohen. Laskennallisen algebrallisen lukuteorian kurssi . - Springer-Verlag , 1996. - S. 433 - 437. - 534 s. — ISBN 3-540-55640-0 .
Jason E. Gower ja Samuel S. Wagstaff, JR. NELIÖMUOTOTEKOITUS . - Moskova: MTSNMO, 2003. - S. 1-16, 35-36. – 38 s. — ISBN 5-94057-103-4 .
Samuel S. Wagstaff Jr. Numeroteoreettisten salausten kryptaanalyysi . - CRC Press , 2003. - 318 s. — ISBN 978-1584881537 .
Yike Guo, RL Grossman. Suorituskykyinen tiedonlouhinta : Skaalausalgoritmit, sovellukset ja järjestelmät . - Kluwer Academic Publishers , 1999. - S. 111. - ISBN 0-7923-7745-1 .

Katso myös

Kokonaislukujen faktorointi

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