Yleinen lukukenttäseulamenetelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 7. joulukuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 9 muokkausta .

Yleislukukenttäseulamenetelmä ( englanniksi general number field seve , GNFS) on kokonaislukujen tekijöiden jakomenetelmä . Se on tehokkain faktorointialgoritmi yli 110 desimaalin tarkkuudelle. Algoritmin monimutkaisuus arvioidaan heuristisella kaavalla [1]

\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\oikea)(\log n)^{\frac{1}{3}}(\log \log n)^{\frac{2}{3}}\right) =L_n\left[\frac{1}{3},\sqrt[3]{\frac{64}{9}}\oikea]

Menetelmä on yleistys lukukenttäseulan erikoismenetelmästä: kun jälkimmäinen sallii vain tietyntyyppisten lukujen faktoroinnin, yleinen menetelmä toimii kokonaislukujen joukossa, lukuun ottamatta alkulukujen potenssia (jotka faktoroidaan triviaalisesti juurtumassa).

Historia

Vuonna 1988 englantilainen matemaatikko John Pollard kuvasi uuden menetelmän erityismuodon ( ) kokonaislukujen laskemiseen havainnollistaen sitä seitsemännen Fermat-luvun laajennuksella . Toisin kuin neliöllinen seulamenetelmä , jossa seulonta suoritetaan kaikkien kokonaislukujen renkaalle, menetelmässä ehdotettiin kokonaislukujen renkaan käyttöä lukukentän päällä . Käsikirjoituksen mukana oli Andrew Odlyzkolle kirje, ja myös Richard Brent , John Brillhart Hendrik Lenstra , Klaus Schnorr H. Suyama saivat kopiot . Tässä kirjeessä Pollard ehdotti, että tätä menetelmää voitaisiin ehkä käyttää yhdeksännen Fermat-luvun laajentamiseen . [2] $2^n \pm C$ $F_7 = 2^{128}+1$ $Z([2^{3/2}])$ $K(2^{3/2})$

Vuonna 1990 A. Lenstra , H. Lenstra, Mark Manasse ja Pollard kuvailivat uuden menetelmän ensimmäistä laajamittaista toteutusta muutamilla parannuksilla. He osoittivat, että algoritmi toimii nopeammin tietyntyyppisillä luvuilla kuin kaikki muut tunnetut tekijänmuodostusmenetelmät. Paperi käsittelee myös Joe Buhlerin ja Karl Pomeransin ideaa parantaa menetelmää kokonaislukujen hajottamiseen ja hahmotellaan ratkaisua tähän ongelmaan. [3]

Myöhemmin Leonard Max Adleman ehdotti neliömerkin käyttämistä neliöiden etsimiseen numerokentästä. Tämä tarjosi vaihtoehtoisen ratkaisun Buchlerin ja Pomerancen esittämään ongelmaan ja paransi lukukenttäseulan arvioitua käyntiaikaa, kun sitä sovellettiin ei-erityistyyppisiin lukuihin. [neljä]

Samana vuonna A. Lenstra, H. Lenstra, Manasse ja Pollard esittelivät yhdeksännen Fermat-luvun laajennuksen numerokenttämenetelmällä. Vastaavassa paperissa käsitellään monia tämän hajoamisen yksityiskohtia. [5]

Lopuksi Buchler, H. Lenstra ja Pomerance kuvasivat teoksessa "Kokonaislukujen kertominen numerokenttäseulalla" lukukenttäseulamenetelmää sovellettuina lukuihin, joilla ei välttämättä ole erityistä muotoa. [6] Tämä algoritmin toteutus sisälsi vaiheen, jossa laskettiin erittäin suuria lukuja. Jean-Marc Kuwaignes kuvaili työssään tapaa kiertää tämä. [7]

Menetelmän varhaisen kehittämisen tulokset tiivistettiin A. Lenstran ja H. Lenstran toimittamiin artikkelikokoelmaan. [8] Kokoelmaan sisältyi muun muassa Bernsteinin ja A. Lenstran artikkeli, jossa kuvataan toista algoritmin parannettua toteutusta. Artikkeli sisällytettiin kokoelmaan otsikolla "Numerokenttäseulan yleinen menetelmä". [9]

Menetelmän ydin

Numerokenttäseulamenetelmää (sekä erityistä että yleistä) voidaan pitää parannuksena yksinkertaisempaan menetelmään, rationaaliseen seulamenetelmään tai neliöseulamenetelmään. Niiden kaltaiset algoritmit vaativat sujuvan järjestysnumeron löytämisen . Näiden lukujen koko kasvaa eksponentiaalisesti . Numerokenttäseulamenetelmä puolestaan edellyttää sileiden lukujen löytämistä, jotka ovat koon suhteen subeksponentiaalisia . Koska nämä luvut ovat pienempiä, on todennäköisempää, että tämän kokoinen luku on sileä, minkä vuoksi numerokenttäseulamenetelmä on niin tehokas. Laskelmien kiihtyvyyden saavuttamiseksi menetelmän puitteissa ne suoritetaan numeerisilla kentillä , mikä monimutkaistaa algoritmia verrattuna yksinkertaisempaan rationaaliseen seulaan. ${\sqrt {n}}$ $n$ $n$

Perusperiaatteet

Fermatin tekijöiden jakomenetelmä luonnollisten parittomien lukujen n tekijöihin jakamiseen , joka koostuu kokonaislukujen x ja y löytämisestä siten, että , joka johtaa luvun tekijöihin jakamiseen . $x^{2}-y^{2}=n$ $n=(xy)\cdot (x+y)$
Sellaisen kokonaislukujoukon osajoukon löytäminen, jonka tulo on neliö [10]
Tekijäkannan laatiminen: joukko , jossa p i ovat alkulukuja siten, että joillekin B . $\{ -1, p_1, p_2, \pisteet, p_n\}$ $p_i \leqslant B$
Seulonta tehdään kuten Eratosthenesin seula (tämä menetelmä saa nimensä). Seula on tekijäkannan alkuluvut ja niiden potenssit. Seulottaessa numeroa ei "viivata yli", vaan se jaetaan seulan numerolla. Jos tuloksena luku osoittautui ykköseksi, niin se on B - sileä.
Pääajatuksena on, että sen sijaan, että iteroitaisiin lukujen yli ja tarkastettaisiin, ovatko niiden neliöt jaollisia modulo n alkuluvuilla tekijäkannasta, vaan kantaluvun alkuluvut lajitellaan ja heti kaikille muodon luvuille tarkistetaan, ovatko ne jaollinen tällä alkuluvulla tai sen potenssilla . $x^{2} - n$

Algoritmi

Antaa olla pariton yhdistelmäluku, joka kerrotaan. $n$

Valitsemme redusoitumattoman polynomin asteen (sillä siitä ei tule voittoa neliöseulamenetelmään verrattuna). $d\ge 3$ $d = 2$
Valitsemme kokonaisluvun siten, että , ja laajennamme kantaan n : $m$ $\lfloor n^{1/(d+1)} \rfloor < m < \lfloor n^{1/d} \rfloor$ $m$ $n = m^d + a_{d-1}m^{d-1} + \pisteet + a_0$ (yksi)
Yhdistetään laajennukseen (1) polynomi, joka on pelkistymätön kokonaislukukertoimien polynomien renkaassa $\mathbb Z[x]$ $f_1(x) = x^d + a_{d-1}x^{d-1} + \pisteet + a_0$
Määrittelemme seulontapolynomin homogeeniseksi polynomiksi kahdessa muuttujassa ja : $F_1(a,b)$ $a$ $b$ $F_{1}(a,b)=b^{d}\cdot f_{1}(a/b)=a^{d}+a_{d-1}a^{d-1}b +a_{d-2}a^{d-2}b^{2}+...+a_{0}b^{d}$ (2)
Määrittelemme toisen polynomin ja sitä vastaavan homogeenisen polynomin . $f_2(x) = x - m$ $F_2(a,b) = a - bm$
Valitaan kaksi positiivista lukua ja määrittämällä seulonta-alue (eng. seula alue ): $L_1$ $L_2$ $SR = \{1 \le b \le L_1, -L_2 \le a \le L_2 \}$
Olkoon juuri . Tarkastellaan polynomirengasta . Määritellään joukko nimeltä algebrallinen tekijäkanta , joka koostuu ensimmäisen kertaluvun polynomeista, joiden muoto on normi (2), joka on alkuluku. Nämä polynomit ovat yksinkertaisia kenttiä, joita ei voida hajottaa algebrallisten kokonaislukujen renkaaseen . Rajataan polynomien normien absoluuttiset arvot vakiosta . $\theta$ $f_1(x)$ $\mathbb Z[\theta]$ $FB_1$ $a - b \theta$ $K = \mathbb Q[\theta]$ $FB_1$ $B_1$
Määritellään rationaalinen tekijäkanta , joka koostuu kaikista ylhäältä vakiolla rajatuista alkuluvuista . $FB_2$ $B_2$
Määrittelemme joukon, jota kutsutaan neliömerkkien tekijäkantaksi . Se on joukko ensimmäisen kertaluvun polynomeja , joiden normi on alkuluku. Ehto on täytettävä . $FB_3$ $c - d \theta$ $FB_1 \cap FB_3 = \tyhjä$
Suoritetaan polynomien seulonta tekijäkannan mukaan ja kokonaislukujen seulonta tekijäkannan mukaan . Tuloksena saadaan joukko , joka koostuu sileistä pareista , eli sellaisista pareista , jotka gcd (a,b) = 1, polynomi ja luku ja laajennetaan kokonaan ja vastaavasti. $\{a - b \theta \mid (a,b) \in SR\}$ $FB_1$ $\{a - bm \mid (a,b) \in SR\}$ $FB_2$ $M$ $(a, b)$ $(a, b)$ $a - b \theta$ $a-bm$ $FB_1$ $FB_2$
Etsi sellainen osajoukko $S\subseteq M$ $\prod_{(a,b) \in S} Nr(a - b\theta) = H^2 , H \in \mathbb Z ; ~~ \prod_{(a,b) \in S} (a - bm) = B^2 , B \in \mathbb Z$
Määritellään polynomi $g(\theta) = {f_1'}^2(\theta) \cdot \prod_{(a,b) \in S} (a - b \theta)$ missä on johdannainen $f_1'(x)$ $f_1(x)$
Polynomi on täydellinen neliö polynomien renkaassa . Olkoon sitten juuri ja olla juuri . $g(\theta)$ $\mathbb Z(\theta)$ $\alpha(\theta)$ $g(\theta)$ $B$ $B^2$
Rakennamme kuvauksen korvaamalla polynomin luvulla . Tämä kuvaus on algebrallisten kokonaislukujen renkaan rengashomomorfismi renkaaseen , josta saamme suhteen: $\phi \colon \theta \to m$ $\alpha(\theta)$ $\alpha(m)$ $\mathbb Z_K$ $\mathbb Z$ $A^2 = {g(m)}^2 \equiv {\phi(g(\alpha))}^2 \equiv \phi ({f_1'}^2(\theta) \cdot \prod_{(a, b) \in S} (a - b \theta)) \equiv {f_1'}^2(m)\cdot \prod_{(a,b) \in S} (a - bm) \equiv {f_1'} ^2(m) \cdot C^2 \pmod n$
Anna . Etsitään sellainen lukupari , että . Sitten luvun jakaja löydetään laskemalla gcd(n, A ± B), kuten tehdään esimerkiksi neliöseulamenetelmässä. $B = f'(m) \cdot C$ $(A, B)$ $A \equiv B \pmod n$ $n$

Yksityiskohtainen kuvaus algoritmista löytyy esimerkiksi kohdista [11] ja [12] .

Toteutukset

Vuoteen 2007 asti menestyksekkäimpana toteutuksena pidettiin Alankomaiden matematiikan ja tietotekniikan keskuksen (CWI) kehittämää ja jakamaa ohjelmistoa , jota jaettiin omalla lisenssillä .

Vuonna 2007 Jason Papadopoulos toteutti algoritmin lopullisen käsittelyosan niin, että se toimi nopeammin kuin CWI-versio. Tämä koodi on osa msieve-kirjastoa. Msieven ovat kirjoittaneet C -kielellä Papadopoulos ja muut projektissa mukana olevat ja se sisältää yleisen lukukentän seulamenetelmän ja neliöllisen seulamenetelmän toteutukset. Jaettu julkisten oikeuksien alaisina . Tukee hajautettua tietojenkäsittelyä. Msieven uusin versio löytyy kirjoittajan sivustolta .

Jotkut muut yleisen numerokentän seulamenetelmän toteutukset:

NFS@Home Arkistoitu 7. joulukuuta 2012 Wayback Machinessa - tutkimusprojekti, jonka tavoitteena oli suurten lukujen faktorointi yleislukukenttäseulamenetelmällä käyttämällä projektiin kytkettyjen tietokoneiden verkkoa seulomiseen.
GGNFS arkistoitu 14. maaliskuuta 2013 Wayback Machinessa , jaettu GPL :n alla .
pGNFS Arkistoitu 15. helmikuuta 2013 Wayback Machinessa
tekijä gnfs Arkistoitu 12. lokakuuta 2012 Wayback Machinessa
CADO-NFS Arkistoitu 28. elokuuta 2011 Wayback Machinessa
kmGNFS Arkistoitu 21. lokakuuta 2021 Wayback Machinessa

Saavutukset

Vuonna 1996 RSA-130- luvun hajotelma saatiin käyttämällä algoritmia . Myöhemmin menetelmällä esimerkiksi luvut RSA-140 [13] ja RSA-155 [14] tekijöihin jaotettiin . Jälkimmäisen hajoaminen kesti yli 8000 mailia vuotta. 9. toukokuuta 2005 F. Bahr, M. Bohm, Jens Franke ja T. Kleinjung ilmoittivat hajottaneensa RSA-200- luvun käyttämällä yleistä lukukenttäseulamenetelmää.

Vuonna 2009 joukko tutkijoita Sveitsistä, Japanista, Ranskasta, Alankomaista, Saksasta ja Yhdysvalloista onnistui laskemaan dataa, joka oli salattu 768-bittisellä RSA -salausavaimella. [15] Kuten työn kuvauksesta seuraa, avainarvot laskettiin yleisellä numerokenttäseulan menetelmällä. Tutkijoiden mukaan heidän työnsä jälkeen vain vähintään 1024 bitin pituisia RSA-avaimia voidaan pitää luotettavana salausjärjestelmänä. [16]

Katso myös

Muistiinpanot

↑ Pomerance, Carl. Tarina kahdesta seulasta (englanniksi) // Notices of the AMS : Journal. - 1996. - Voi. 43 , no. 12 . - s. 1473-1485 .
↑ JM Pollard (1988), Factoring kuutioluvuilla
↑ A. K. Lenstra, H. W. Lenstra, Jr., MS Manasse, J. M. Pollard (1990), The number field seve , s. 564-572, ISBN 0-89791-361-2
↑ Leonard M. Adleman (1991), Lukujen faktorointi käyttämällä yksittäisiä kokonaislukuja , s. 64-71, ISBN 0-89791-397-3
↑ A. K. Lenstra, H. W. Lenstra, Jr., MS Manasse, J. M. Pollard. Yhdeksännen Fermat-luvun faktorointi // Math . Comp. : päiväkirja. - 1993. - Voi. 61 . - s. 319-349 . - doi : 10.1090/S0025-5718-1993-1182953-4 .
↑ JP Buhler, HW Lenstra, Carl Pomerance. Kokonaislukujen faktorointi lukukentän seulalla (epämääräinen) // Matematiikan luentomuistiinpanot. - 1993. - T. 1554 . - S. 50-94 . - doi : 10.1007/BFb0091539 .
↑ Jean-marc Couveignes. Neliöjuuren laskeminen numerokenttäseulalle (määrittämätön) // Matematiikan luentomuistiinpanot. - 1993. - T. 1554 . - S. 95-102 . - doi : 10.1007/BFb0091540 .
↑ A. K. Lenstra, H. W. Lenstra (1993), The Development of the Number Field Sieve , Springer, ISBN 9783540570134
↑ Jean-marc Couveignes. Yleinen lukukenttäseulan toteutus (määrätön) // Matematiikan luentomuistiinpanot. - 1993. - T. 1554 . - S. 103-126 . - doi : 10.1007/BFb0091541 .
↑ I. V. Agafonova Suurten kokonaislukujen faktorointi ja kryptografia Arkistokopio 26. helmikuuta 2015 Wayback Machinessa .
↑ Briggs M. (1998), An Introduction to the General Number Field Sieve , < http://www.math.vt.edu/people/brown/doc/briggs_gnfs_thesis.pdf > Arkistoitu 8. elokuuta 2017 Wayback Machinessa
↑ Ishmukhametov Sh. T. Luonnollisten lukujen faktorointimenetelmät . - Kazan: Kazan. un.. - 2011. - 190 s.
↑ Cavallar S., Dodson B., Lenstra AK, Leyland PC, Lioen WM, Montgomery PL, Murphy B., te Riele HJJ, Zimmerman P. RSA-140:n faktorointi numerokenttäseulalla / CWI-raportti MAS-R9925, syyskuu 1999.
↑ Cavallar S., Lioen WM, Riele HJJ, Dodson B., Lenstra AK, Montgomery PL, Murphy B. et ai. 512-bittisen RSA-moduulin faktorointi / CWI-raportti MAS-R0007, helmikuu 2000.
↑ RSA-768:n tekijöitä koskeva ilmoitus Arkistoitu 13. huhtikuuta 2014 Wayback Machinessa
↑ RSA-768 factorization Arkistoitu 13. joulukuuta 2012 Wayback Machinessa