Neliöllinen seulamenetelmä

Kvadraattinen seula-algoritmi ( lyhenne QS) on Pomeranzin vuonna 1981 kehittämä suurilukuisten tekijöiden laskentamenetelmä. Se ylitti pitkään muut tekijöiden jakamismenetelmät yleisen muodon kokonaisluvuille, joilla ei ole alkujakajia, joiden järjestys on paljon pienempi (lukujen , joiden alkujakajat ovat paljon pienemmät, tekijöihin jakomenetelmä elliptisille käyrille on nopeampi ). Neliöllinen seulamenetelmä on muunnelma tekijäpohjamenetelmästä (yleistys Fermat'n faktorointimenetelmästä ). Tätä menetelmää pidetään toiseksi nopeimpana ( yleisen lukukenttäseulamenetelmän jälkeen ). Ja toistaiseksi se on nopein kokonaisluvuille 100 desimaalin numeroon asti ja on paljon yksinkertaisempi kuin yleinen lukukenttäseulamenetelmä . Tämä on universaali tekijöiden jakamisalgoritmi, koska sen suoritusaika riippuu yksinomaan faktoroidun luvun koosta, ei sen erityisestä rakenteesta ja ominaisuuksista. [yksi] ${\sqrt {n}}$ $n$ ${\sqrt {n}}$

Päätavoitteet

Algoritmi yrittää löytää sellaisia lukujen neliöitä, joiden moduuli on yhtä suuri (kerroitettava luku), mikä usein johtaa tekijöihin . Algoritmi toimii kahdessa vaiheessa: tiedonkeruuvaihe, jossa se kerää tietoa, joka voi johtaa neliöiden yhtäläisyyteen; ja tietojenkäsittelyvaihe, jossa se laittaa kaiken kerätyn tiedon matriisiin ja käsittelee sen neliöiden yhtäläiseksi saamiseksi. Ensimmäinen vaihe voidaan rinnastaa helposti monien prosessien kesken, mutta toinen vaihe vaatii suuria määriä muistia ja sitä on vaikea rinnastaa. $n$ $n$

Yksi yksinkertainen tapa löytää yhtäläiset neliöt on valita satunnaisluku, neliöttää se ja toivoa, että jakojäännös on jonkun muun luvun neliö. Esimerkiksi . Tämä menetelmä löytää yhtä suuret neliöt vain harvoissa tapauksissa , mutta jos se löytää nämä luvut, voimme olettaa, että tekijöiden jakaminen on valmis. Tämä menetelmä on samanlainen kuin Fermatin tekijöiden jakomenetelmä . $n$ $80^{2}{\pmod {5959}}=441=21^{2}$ $n$

Kvadraattinen seulamenetelmä on muunnos Dixonin tekijöiden jakamismenetelmästä .

Laskennan kesto kvadraattiselle seulalle ( - tekijöiksi muutettava luku): $n$

$O(exp((1+o(1)){\sqrt {\log n\log \log n))))$ . [2]

Lähestymistapa

Olkoon x mod y jäännös x:stä jaettuna y:llä. Fermat - faktorointimenetelmässä valitaan yksittäin luku a niin, että 2 mod n on neliö. Mutta sitä numeroa on vaikea saada. Laskemme neliöseulassa 2 mod n jollekin a ja etsimme sitten osajoukon, jonka tulo on neliö. Tämä vertaa neliöitä.

Esimerkiksi 41 2 mod 1649 = 32, 42 2 mod 1649 = 115 ja 43 2 mod 1649 = 200. Kumpikaan tulos ei ole neliö, vaan tuotteen tulos (32)(200) = 6400 = 80 2 . Toisaalta, kun otetaan huomioon edellinen tuotemodi 1649, saadaan, että (32)(200) = (41 2 )(43 2 ) = ((41)(43)) 2 . Koska (41)∙(43) mod 1649 = 114, meillä on neliövertailu: 114 2 ≡ 80 2 (mod 1649).

Mutta kuinka ratkaisemme ongelman korjaamalla joukon lukuja ja etsimällä osajoukon, alkioiden tulon, jonka neliö on? Aloitetaan eksponenttivektorin käsitteestä . Esimerkiksi meillä on luku 504. Sen hajoaminen alkutekijöiksi on seuraava 504 = 2 3 3 2 5 0 7 1 . Voisimme esittää tämän laajennuksen eksponenttivektorina (3,2,0,1), joka kaappaa laajennukseen osallistuvien alkulukujen 2, 3, 5 ja 7 potenssit. Numerolla 490 olisi analogisesti vektori (1,0,1,2). Lukujen kertolasku on sama kuin niiden eksponenttivektoreiden elementtikohtainen yhteenlasku, eli tulolla 504 ∙ 490 on vektori (4,2,1,3).

Huomaa nyt, että luku on neliö, jos jokainen sen eksponenttivektorin elementti on parillinen . Esimerkiksi lisäämällä vektorit (3,0,0,1) ja (1,2,0,1) saadaan (4,2,0,2). Tämä kertoo meille, että lukujen 56 ∙ 126 tulo on neliö. Itse asiassa emme välitä tarkoista arvoista, jotka saamme vektorissa, kunhan jokainen elementti tuloksena olevassa vektorissa on parillinen. Tästä syystä otamme jokaisen elementin mod 2 ja lisäämme elementit mod 2: (1,0,0,1) + (1,0,0,1) = (0,0,0,0).

Siten ongelmamme on saanut seuraavan muodon: jos on annettu joukko vektoreita (0,1), etsi osajoukko, joka on täydennetty nollavektoriksi mod 2 -lisäyksen avulla. Tämä on lineaarinen algebratehtävä, eli on tarpeen löytää lineaarisesti riippuvat vektorit. Lineaarialgebran lauseesta seuraa, että niin kauan kuin vektorien lukumäärä on suurempi kuin kunkin vektorin elementtien lukumäärä, tällaisen riippuvuuden on oltava olemassa. Voimme löytää tehokkaasti lineaarisesti riippuvia vektoreita esimerkiksi sijoittamalla alkuperäiset vektorit matriisin sarakkeiksi ja käyttämällä Gaussin menetelmää , joka on helppo mukauttaa toimimaan kokonaislukujen mod 2 kanssa. Kun olemme löytäneet lineaarisesti riippuvat vektorit, kerromme yksinkertaisesti numeroita, jotka vastaavat näitä vektoreita, ja saamme etsimämme neliön.

Kuitenkin satunnaislukujoukon mod n neliöinti johtaa suureen määrään erillisiä alkutekijöitä, pitkiä vektoreita ja suuren matriisin. Päästäksemme eroon tästä ongelmasta etsimme erityisesti lukuja, joissa 2 mod n : llä on vain pienet alkutekijät (tällaisia lukuja kutsutaan sileiksi lukuiksi ). Niitä on vaikea löytää, mutta tällaisten lukujen avulla vältetään suuret vektorit ja matriisit.

Menetelmän pääidea

Tekijäkannaksi otamme joukon alkulukuja, jotka koostuvat ja kaikista sellaisista parittomista alkuluvuista , jotka eivät ylitä tiettyä rajaa (joka valitaan optiminäkökohdista), joka on neliöllinen jäännös modulo . $B$ $p = 2$ $s$ $P$ $n$ $s$

Kokonaislukujoukko , josta haetaan -lukuja ( -luku on kokonaisluku, joka on jaollinen vain alkuluvuilla alkaen ) näyttää tältä: $S$ $B$ $B$ $B$

$S=\left\{t^{2}-n|[{\sqrt {n}}]+1\leq t\leq [{\sqrt {n}}]+A\right\}$

Lisäksi sen sijaan, että otettaisiin yksitellen ja jaettaisiin se alkuluvuilla luvusta , kukin otetaan yksitellen ja jaollisuus arvolla (ja sen potenssit) tarkistetaan samanaikaisesti kaikille . Voit käyttää Eratosthenesin seulaa muodostamaan luettelon kaikista alkuluvuista, jotka eivät ylitä . $s\in S$ $B$ $p\in B$ $s$ $s\in S$ $s$ $A$

Algoritmi

1. Rajat ja suuruusluokat valitaan (jäljempänä ) siten, että . $P$ $A$ $e^{\sqrt {\log {n}\log {\log {n))))$ $L(n)$ $P<A<P^{2}$

2. Jos , ,…, kokonaisluvut kirjoitetaan sarakkeeseen . $t=[{\sqrt {n}}]+1$ $\left[{\sqrt {n}}\right]+2$ $\left[{\sqrt {n}}\right]+A$ $t^{2}-n$

3. Jokaiselle parittomalle alkuluvulle lasketaan Legendre-symboli - ehto tarkistetaan . Jos se ei täyty, se poistetaan tekijäkannasta. $p\leq P$ $\left({n \over p}\right)=1$ $s$

4. Jos oletetaan, että tämä on niin pariton alkuluku, joka on neliöllinen jäännösmoduuli , yhtälö 1,2,… on ratkaistu. Arvot otetaan nousevassa järjestyksessä, kunnes käy ilmi, että yhtälöllä ei ole moduuliltaan vertailukelpoisia ratkaisuja minkään alueen luvun kanssa . $s$ $n$ $s$ ${\displaystyle t^{2}\equiv n{\pmod {p^{\beta ))))$ $\beta =$ $\beeta$ $t$ ${\displaystyle p^{\beta ))$ $\left[{\sqrt {n}}\right]+1\leq t\leq \left[{\sqrt {n}}\oikea]+A$

Antaa olla suurin sellaisista luvuista, joille on olemassa numero omaisuuden kanssa . $\beeta$ $t$ ${\displaystyle t^{2}\equiv n{\pmod {p^{\beta ))))$

Anna ja ratkaisut ja . $t_{1}$ $t_{2}$ ${\displaystyle t^{2}\equiv n{\pmod {p^{\beta ))))$ ${\displaystyle t_{2}\equiv -t_{1}{\pmod {p^{\beta ))))$

5. Samalla arvolla näytetään vaiheessa 2 saatujen arvojen luettelo . Aseta sarakkeessa 1 kaikki arvot , jotka eroavat arvosta jollakin kerrannaisuudella . Sen jälkeen 1 korvataan 2:lla kaikille sellaisille arvoille , jotka eroavat monikerrasta , ja niin edelleen, kunnes . Sitten sama tehdään kanssa . Suurin mahdollinen luku sarakkeessa on . $s$ $t^{2}-n$ $s$ $t^{2}-n$ $t$ $t_{1}$ $s$ $t^{2}-n$ $t$ $t_{1}$ $p^{2}$ $\beeta$ $t_{2}$ $t_{1}$ $\beeta$

6. Kun vaiheessa 5 lisätään toinen yksikkö sarakkeen numeroon, vastaava luku jaetaan ja tulos tallennetaan. $t^{2}-n$ $s$

7. Alle at: n sarakkeessa yksinkertaisesti laitetaan 1 vastaan pariton ja vastaava jaetaan 2:lla. Kun yhtälö on ratkaistu ja ratkaisu jatkuu samaan tapaan kuin pariton kanssa . $p = 2$ $n\neq 1{\pmod {8}}$ $t^{2}-n$ $t$ $t^{2}-n$ $n\equiv 1{\pmod {8}}$ ${\displaystyle t^{2}=n{\pmod {2^{\beta ))))$ $s$

8. Kun kaikki ilmoitetut toimenpiteet suoritetaan kaikille alkuluvuille, jotka eivät ylitä , kaikki luvut tulee hylätä lukuun ottamatta niitä, jotka muuttuivat 1:ksi sen jälkeen, kun ne on jaettu kaikilla potenssilla, jotka eivät ylitä . Tämän seurauksena saamme taulukon, jossa sarake sisältää kaikki tällaiset arvot väliltä , joka on -luku, ja loput sarakkeet vastaavat niitä arvoja , joille - neliöllinen jäännös. $P$ $t^{2}-n$ $s$ $P$ $b_{i}$ $t$ $\left[{\left[{\sqrt {n}}\right]+1,\left[{\sqrt {n}}\right]+A}\right]$ $t^{2}-n$ $B$ $p\leq P$ $n$

9. Seuraavaksi käytetään yleistettyä Fermat-faktorointimenetelmää (factor base method ).

Kuinka neliöllinen seulamenetelmä optimoi yhtäläisten neliöiden haun

Neliöllinen seulamenetelmä yrittää löytää kokonaislukupareja x ja y(x) (missä y(x) on x:n funktio ) , jotka täyttävät paljon heikomman ehdon kuin x 2 ≡ y 2 (mod n ). Hän valitsee alkulukujoukon, jota kutsutaan tekijäkantaiseksi , ja yrittää löytää x : n siten, että pienin jäännös y(x) = x 2 mod n tekee tekijäkannan tekijöille. Tällaisten y :iden sanotaan olevan tasaisia tekijäkannan suhteen.

Y(x):n arvon faktorointia tekijäkannan yli yhdessä x:n arvon kanssa kutsutaan riippuvuudeksi . Neliöseula nopeuttaa riippuvuuksien etsintäprosessia valitsemalla x :n lähellä n: n neliöjuurta . Tämä takaa, että luku y(x) on pienempi ja siksi todennäköisemmin tasainen .

y(x)=\left(\left\lceil {\sqrt {n))\right\rceil +x\oikea)^{2}-n{\hbox{ (jossa }}x{\hbox{ on pieni kokonaisluku)}}

y(x)\noin 2x\left\lceil {\sqrt {n))\right\rceil

Toinen tapa lisätä todennäköisyyttä olla tasainen luku on suurentaa tekijäkannan kokoa. Tällöin on kuitenkin tarpeen löytää vähintään yksi tasaisempi yhteys kuin kantalukujen lukumäärä, jotta voidaan varmistaa lineaarisen suhteen olemassaolo.

Esimerkki

Tämä esimerkki esittää standardin neliöllisen seulan ilman logaritmisia optimointeja. Oletetaan, että meidän täytyy kertoa luku N = 15347, joten pienin luku, jonka neliö on suurempi kuin N , on 124. Joten y ( x ) = ( x + 124) 2 − 15347.

Tiedonkeruu

Koska N on pieni, tarvitaan vain 4 alkulukua. Ensimmäiset 4 alkulukua p , joille 15347:llä on neliöjuuren modulo p , ovat 2, 17, 23 ja 29 (toisin sanoen 15347 on näiden alkulukujen neliöllinen jäännös ). Nämä luvut muodostavat neliöllisen seulan perustan.

Rakennamme nyt siivilämme ja aloitamme seulomalla prosessin jokaiselle kantaluvun alkuluvulle valitsemalla seulomaan ensimmäisen Y(X) 0 ≤ X < 100 : $V_{X}$ $Y(X)=(X+\lceil {\sqrt {N))\rceil )^{2}-N=(X+124)^{2}-15347$

{\begin{aligned}V&={\begin{bmatrix}Y(0)&Y(1)&Y(2)&Y(3)&Y(4)&Y(5)&\cdots &Y(99)\end {bmatrix}}\\&={\begin{bmatrix}29&278&529&782&1037&1294&\cdots &34382\end{bmatrix}}\end{aligned}}

Seuraava vaihe on seulonta . Ratkaisemme yhtälön jokaiselle p: lle tekijäkannassamme $\lhakasulku 2,17,23,29\rhakasulke$

Y(X)\equiv (X+\lceil {\sqrt {N))\rceil )^{2}-N\equiv 0{\pmod {p))

löytääksesi taulukosta V merkintöjä, jotka ovat jaollisia p :llä .

Sillä päätämme löytää ratkaisun . $p = 2$ $(X+124)^{2}-15347\equiv 0{\pmod {2))$ $X\equiv {\sqrt {15347}}-124\equiv 1{\pmod {2}}$

Joten alkaen X=1 askeleella 2, jokainen merkintä on jaollinen 2:lla. Kunkin merkinnän jakaminen kahdella antaa

V={\begin{bmatrix}29&139&529&391&1037&647&\cdots &17191\end{bmatrix}}

Vastaavasti jäljellä oleville alkuluvuille p yhtälö on ratkaistu. Huomaa, että jokaiselle p > 2 tulee 2 tuloksena olevaa lineaariyhtälöä, koska modulo on 2 neliöjuurta. $\lhakasulku 17,23,29\rhakasulke$ $X\equiv {\sqrt {15347}}-124{\pmod {p}}$

{\begin{aligned}X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 3{\pmod {17}}\\&&\equiv 9-124&\equiv 4{\pmod {17}}\\X&\equiv {\sqrt {15347}}-124&\equiv 11-124&\equiv 2{\pmod {23}}\\&&\equiv 12-124&\equiv 3{\pmod {23} }\\X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 0{\pmod {29}}\\&&\equiv 21-124&\equiv 13{\pmod {29}}\\ \end{aligned}}

Jokainen yhtälö johtaa siihen, että se on jaollinen p :llä, kun x = a , a + p , a +2 p jne. V : n jakaminen p : llä a , a + p , a +2 p , a +3 p jne. alkuluku perusteesta löydämme sileät luvut . $X\equiv a{\pmod {p}}$ $V_{x}$

V={\begin{bmatrix}1&139&23&1&61&647&\cdots &17191\end{bmatrix}}

V :n alkio, joka on yhtä suuri kuin 1, vastaa tasaista lukua. Koska , , ja kierretään luvulla 1, niin: $V_{0}$ $V_{3}$ $V_{71}$

X +124	Y	tekijät
124	29	2 0 • 17 0 • 23 0 • 29 1
127	782	2 1 • 17 1 • 23 1 • 29 0
195	22678	2 1 • 17 1 • 23 1 • 29 1

Matriisikäsittely

Harkitse tasa-arvoja:

{\begin{aligned}29&=2^{0}\cdot 17^{0}\cdot 23^{0}\cdot 29^{1}\\782&=2^{1}\cdot 17^ {1}\cdot 23^{1}\cdot 29^{0}\\22678&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{1}\\\ loppu{tasattu}}

ja kirjoita alkulukujen indikaattorit matriisin muodossa ja ratkaise järjestelmä : ${\pmod {2}}$

S\cdot {\begin{bmatrix}0&0&0&1\\1&1&1&0\\1&1&1&1\end{bmatrix}}\equiv {\begin{bmatrix}0&0&0&0\end{bmatrix}}{\pmod {2}}

Hänen ratkaisunsa:

S={\begin{bmatrix}1&1&1\end{bmatrix}}

Siten kaikkien kolmen yhtälön tulo on neliö (mod N).

{\displaystyle 29\cdot 782\cdot 22678=22678^{2))

{\displaystyle 124^{2}\cdot 127^{2}\cdot 195^{2}=3070860^{2))

algoritmi löytää

22678^{2}\equiv 3070860^{2}{\pmod {15347))

Nyt lasketaan GCD(3070860 - 22678, 15347) = 103, ei-triviaali jakaja on 15347, toinen on 149.

Faktorisointitietueet

Ennen yleisen numerokentän seulan (NFS) löytämistä QS tunnettiin nopeimpana yleiskäyttöisenä tekijänlaskenta-algoritmina. Tällä hetkellä elliptisen käyrän faktorointialgoritmilla on sama ajoaika kuin QS:llä (jos n on vain kahden alkuluvun tulo), mutta käytännössä QS on nopeampi, koska se käyttää yksittäisiä tarkkuusoperaatioita pitkien aritmeettisten operaatioiden sijaan , joita käytetään elliptisen käyrän menetelmässä.

2. huhtikuuta 1994 RSA -129 faktorisoitiin käyttämällä QS-menetelmää. Se oli pituuden luku 129, tulos kahden alkuluvun tulosta, joista toisen pituus on 64 ja toisen pituuden 65. Tässä tapauksessa tekijäkanta koostui 524339 alkuluvusta. Tiedonkeruuvaihe tuotti 5 000 MIPS . Kerätyt tiedot veivät 2 Gt . Matriisikäsittelyvaihe kesti 45 tuntia Bellcoressa-ovsky (nyt Telcordia Technologies) MasPar- supertietokoneessa . Se oli tuolloin suurin luku, jonka yleiskäyttöinen algoritmi pystyi kertomaan. Vasta 10. huhtikuuta 1996 he pystyivät kertomaan luvun, jonka pituus oli 130 RSA , käyttämällä NFS-menetelmää.

Kirjallisuus

Koblitz NA Lukuteorian ja kryptografian kurssi (uuspr.) . - Springer-Verlag , 1987. - S. 180-182.
Gerver JL Suurien lukujen faktorinointi neliöseulalla . — Matematiikka. Comp., 1983. Voi. 41. - s. 287-294.

Muistiinpanot

↑ Carl Pomerance, Joidenkin kokonaislukufaktorointialgoritmien analyysi ja vertailu, teoksessa Computational Methods in Number Theory, osa I, HW Lenstra, Jr. ja R. Tijdeman, toim., Math. Center Tract 154, Amsterdam, 1982, s. 89-139.
↑ Pomerance, Carl . Tarina kahdesta seulasta (joulukuu 1996), s. 1473–1485. Arkistoitu 11. marraskuuta 2020. Haettu 10. joulukuuta 2011.

Richard Crandall ja Carl Pomerance . Alkuluvut : Laskennallinen näkökulma . – 1. - Springer, 2001. - ISBN 0-387-94777-9 . Kohta 6.1: Neliöllinen seulafaktorointimenetelmä, ss. 227-244.