Yleinen lukukuntaseula

Matematiikassa yleinen lukukuntaseula (GNFS) on tehokkain tunnettu algoritmi suurten kokonaislukujen jakamiseen alkutekijöidensä tuloksi. Siltä kestää

${\displaystyle O\left(\exp \left(\left({\begin{matrix}{\frac {64}{9}}\end{matrix}}n\right)^{1 \over 3}(\log n)^{2 \over 3}\right)\right)}$

askelta jakaa n-numeroinen luku tekijöihin. Algoritmi on yleisempi kuin erityinen lukukuntaseula: siinä missä jälkimmäinen voi jakaa vain tiettyjä lukuja tekijöihin, yleinen lukukuntaseula voi jakaa tekijöihin kaikki paitsi alkuluvun potensseja. Sana lukukuntaseula viittaa yleensä nimenomaan yleiseen lukukuntaseulaan.

Lukukuntaseulat (sekä erityinen että yleinen) voidaan ymmärtää laajennuksena yksinkertaisemmasta rationaaliseulasta. Rationaaliseulaa käytettäessä luvun n tekijöihin jakamiseen on välttämätöntä etsiä niin sanottuja sileitä kertalukua n olevia lukuja (eli lukuja, joiden alkutekijät ovat pieniä). Toisaalta näitä lukuja on vähän, joten rationaaliseula on varsin käyttökelvoton tekijöihinjakamisalgoritmi. Tosin siitä kehitetyt neliöseulat ovat tehokkaita koska ne toimivat noin ${\displaystyle {\sqrt {n}}}$ kokoisilla luvuilla – MPQS on edelleen nopein menetelmä noin 60–120-numeroisiin lukuihin, rajakohta riippuu toteutustavasta.

Yleinen lukukuntaseula sen sijaan vaatii lukujen etsimistä lukuun n^1/d saakka, missä d on jokin ykköstä suurempi kokonaisluku. Koska isot luvut ovat paljon pienemmällä todennäköisyydellä sileitä kuin pienet luvut, johtuu tästä yleisen lukukuntaseulan tehokkuus kokonaislukujen tekijöihinjakamisalgoritmina. Mutta saavuttaakseen tämän nopeuseron, on algoritmin suoritettava laskut lukukunnissa. Tuloksena saadaan melko monimutkainen algoritmi verrattuna rationaaliseulaan.

Menetelmä

Valitaan kaksi jaotonta polynomia f(x) ja g(x), joilla on yhteinen juuri m (mod n). Nämä polynomit ovat kertalukua m, vaikka niiden asteet ovat pienet luvut d ja e. Toistaiseksi ei ole pystytty kehittämään algoritmia, joka todistettavasti osaisi antaa parhaimmat polynomit, mutta yleensä valinta tehdään ottamalla jokin d-asteinen polynomi ja esitetään n m-kantaisessa lukujärjestelmässä, missä m on luvun n^1/d kertaluku. Tämän tavoitteena on saada f:n ja g:n kertoimet mahdollisimman pieniksi. Toistaiseksi parhaiten tämä onnistuu Murphyn ja Brentin kehittämällä menetelmällä (^[1]).

Seuraavaksi tarkastellaan lukukunnassa renkaita Z[r1] ja Z[r2], missä r1 ja r2 ovat f:n ja g:n juuria, ja etsitään arvot a ja b siten, että r = b^d·f(a/b) ja s = b^e·g(a/b) ovat sileitä lukuja valitun "alkulukukokoelman" suhteen. Jos a ja b ovat pieniä, r ja s ovat myös pieniä (mutta vähintään kertalukua m), ja ne ovat kumpikin sileitä suuremmalla todennäköisyydellä.

Kun näitä pareja on löydetty tarpeeksi monta, voidaan Gaussin eliminoimismenetelmällä kiinteä r ja s saada neliöiksi samaan aikaan (tosin käytännössä otetaan jokin nopeampi menetelmä, esimerkiksi Lanczos). Samalla menetelmällä ne voidaan saada lukukunnan normin suhteen neliöiksi. Jokainen r on a- r1*b:n normi ja vastaavien tekijöiden a- r1*b tulo on neliö Z[r1]:ssä (tulo Z[r1]:n tunnetuista tekijöistä), joten tästä luvusta voidaan ottaa "neliöjuuri". Tämä esitetään tyypillisesti algebrallisena lukuna. Samoin saadaan, että tekijöiden a- r2*b tulo on neliö Z[r2]:ssa, jonka "neliöjuuri" on myös laskettavissa.

Koska m on sekä f:n, että g:n juuri modulo n, on olemassa homomorfismit renkailta Z[r1] ja Z[r2] renkaalle Z/nZ, joka kuvaa r1:n ja r2:n m:lle, ja nämä homomorfismit kuvaavat saadut "neliöjuuret" (joita ei esitetä tyypillisesti rationaalilukuina) niiden kokonaislukuesityksille. Nyt tulo muotoa a-m*b mod n olevista tekijöistä voidaan esittää kahdella tapaa neliönä, joista kumpikin homomorfismi antaa toisen. Siten löydetään kaksi lukua x ja y, joille x²-y² on jaollinen n:llä ja vähintään 50 %:n todennäköisyydellä saadaan selville jokin n:n tekijä laskemalla n:n ja x-y:n suurin yhteinen tekijä.

Algoritmia käyttäviä ohjelmia

• GGNFS (GNU GPL -lisensoitu sovellus)
• pGNFS
• gnfs:ää käyttävä ohjelma
• msieve (Arkistoitu – Internet Archive), johon on sisäänrakennettu GNFS-algoritmi

Lähteet

• Lenstra, Arjen K.; Lenstra, H.W., Jr. (Eds.) (1993). The development of the number field sieve. Lecture Notes in Math. 1554. Springer-Verlag.
• Pomerance, Carl (1996). A Tale of Two Sieves. Notices of the AMS 1996, 1473–1485.
• Crandall, Richard; Pomerance, Carl, 2001, Prime Numbers: A Computational Perspective, Springer, 1st edition, ISBN 0-387-94777-9 Luku 6.2: Number field sieve, pp. 244–267.

Viitteet

1. Murphy, B.; Brent, R. P., On quadratic polynomials for the number field sieve. Australian Computer Science Communications 20 (1998), pp. 199–213 [1]