b'\n_START_ARTICLE_\nYleinen lukukuntaseula\n_START_SECTION_\nMenetelm\xc3\xa4\n_START_PARAGRAPH_\nValitaan kaksi jaotonta polynomia f(x) ja g(x), joilla on yhteinen juuri m (mod n). N\xc3\xa4m\xc3\xa4 polynomit ovat kertalukua m, vaikka niiden asteet ovat pienet luvut d ja e. Toistaiseksi ei ole pystytty kehitt\xc3\xa4m\xc3\xa4\xc3\xa4n algoritmia, joka todistettavasti osaisi antaa parhaimmat polynomit, mutta yleens\xc3\xa4 valinta tehd\xc3\xa4\xc3\xa4n ottamalla jokin d-asteinen polynomi ja esitet\xc3\xa4\xc3\xa4n n m-kantaisessa lukuj\xc3\xa4rjestelm\xc3\xa4ss\xc3\xa4, miss\xc3\xa4 m on luvun n1/d kertaluku. T\xc3\xa4m\xc3\xa4n tavoitteena on saada f:n ja g:n kertoimet mahdollisimman pieniksi. Toistaiseksi parhaiten t\xc3\xa4m\xc3\xa4 onnistuu Murphyn ja Brentin kehitt\xc3\xa4m\xc3\xa4ll\xc3\xa4 menetelm\xc3\xa4ll\xc3\xa4 ()._NEWLINE_Seuraavaksi tarkastellaan lukukunnassa renkaita Z[r1] ja Z[r2], miss\xc3\xa4 r1 ja r2 ovat f:n ja g:n juuria, ja etsit\xc3\xa4\xc3\xa4n arvot a ja b siten, ett\xc3\xa4 r = b\xe1\xb5\x88\xc2\xb7f(a/b) ja s = b\xe1\xb5\x89\xc2\xb7g(a/b) ovat sileit\xc3\xa4 lukuja valitun "alkulukukokoelman" suhteen. Jos a ja b ovat pieni\xc3\xa4, r ja s ovat my\xc3\xb6s pieni\xc3\xa4 (mutta v\xc3\xa4hint\xc3\xa4\xc3\xa4n kertalukua m), ja ne ovat kumpikin sileit\xc3\xa4 suuremmalla todenn\xc3\xa4k\xc3\xb6isyydell\xc3\xa4._NEWLINE_Kun n\xc3\xa4it\xc3\xa4 pareja on l\xc3\xb6ydetty tarpeeksi monta, voidaan Gaussin eliminoimismenetelm\xc3\xa4ll\xc3\xa4 kiinte\xc3\xa4 r ja s saada neli\xc3\xb6iksi samaan aikaan (tosin k\xc3\xa4yt\xc3\xa4nn\xc3\xb6ss\xc3\xa4 otetaan jokin nopeampi menetelm\xc3\xa4, esimerkiksi Lanczos). Samalla menetelm\xc3\xa4ll\xc3\xa4 ne voidaan saada lukukunnan normin suhteen neli\xc3\xb6iksi. Jokainen r on a- r1*b:n normi ja vastaavien tekij\xc3\xb6iden a- r1*b tulo on neli\xc3\xb6 Z[r1]:ss\xc3\xa4 (tulo Z[r1]:n tunnetuista tekij\xc3\xb6ist\xc3\xa4), joten t\xc3\xa4st\xc3\xa4 luvusta voidaan ottaa "neli\xc3\xb6juuri". T\xc3\xa4m\xc3\xa4 esitet\xc3\xa4\xc3\xa4n tyypillisesti algebrallisena lukuna. Samoin saadaan, ett\xc3\xa4 tekij\xc3\xb6iden a- r2*b tulo on neli\xc3\xb6 Z[r2]:ssa, jonka "neli\xc3\xb6juuri" on my\xc3\xb6s laskettavissa._NEWLINE_Koska m on sek\xc3\xa4 f:n, ett\xc3\xa4 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\xc3\xa4m\xc3\xa4 homomorfismit kuvaavat saadut "neli\xc3\xb6juuret" (joita ei esitet\xc3\xa4 tyypillisesti rationaalilukuina) niiden kokonaislukuesityksille. Nyt tulo muotoa a-m*b mod n olevista tekij\xc3\xb6ist\xc3\xa4 voidaan esitt\xc3\xa4\xc3\xa4 kahdella tapaa neli\xc3\xb6n\xc3\xa4, joista kumpikin homomorfismi antaa toisen. Siten l\xc3\xb6ydet\xc3\xa4\xc3\xa4n kaksi lukua x ja y, joille x\xc2\xb2-y\xc2\xb2 on jaollinen n:ll\xc3\xa4 ja v\xc3\xa4hint\xc3\xa4\xc3\xa4n 50\xc2\xa0%:n todenn\xc3\xa4k\xc3\xb6isyydell\xc3\xa4 saadaan selville jokin n:n tekij\xc3\xa4 laskemalla n:n ja x-y:n suurin yhteinen tekij\xc3\xa4.'