Yleinen lukukuntaseula

Wikipedia
Loikkaa: valikkoon, hakuun

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

O\left(\exp\left(\left(\begin{matrix}\frac{64}{9}\end{matrix} n\right)^{1\over3} (\log n)^{2\over3}\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ä). Toisaaltä 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 \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 n1/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ä[muokkaa | muokkaa wikitekstiä]

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 n1/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 aja b siten, että r = bd·f(a/b) ja s = be·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 x2-y2 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[muokkaa | muokkaa wikitekstiä]

Lähteet[muokkaa | muokkaa wikitekstiä]

  • 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[muokkaa | muokkaa wikitekstiä]

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