Rationaalinen seula

Rationaalinen seula on yleinen algoritmi kokonaislukujen laskemiseksi alkutekijöiksi . Algoritmi on yleislukukenttäseulamenetelmän erikoistapaus . Vaikka se on vähemmän tehokas kuin yleinen algoritmi, se on käsitteellisesti yksinkertaisempi. Algoritmi voi auttaa ymmärtämään, kuinka yleinen lukukenttäseulamenetelmä toimii.

Menetelmä

Oletetaan, että yritämme kertoa yhdistelmäluvun n . Määrittelemme B : n rajan ja tekijöiden kannan (jotka merkitsemme P ), kaikkien alkulukujen joukon, jotka ovat pienempiä tai yhtä suuria kuin B . Etsimme sitten positiivista kokonaislukua z siten, että sekä z että z+n ovat B -sileät , eli kaikki niiden alkujakajat sisältyvät P :hen . Voimme siksi kirjoittaa sopivilla tehoilla

,

ja myös sopiva meillä on

.

Mutta ja ovat modulovertailukelpoisia , joten mikä tahansa sellainen kokonaisluku z , jonka löydämme, antaa modulo-kertolinkin (mod n ) P :n kaikkien elementtien kesken , ts.

(jossa a i ja b i ovat ei-negatiivisia kokonaislukuja.)

Kun näitä suhteita on generoitu tarpeeksi (yleensä niin paljon, että tällaisten suhteiden lukumäärä on hieman suurempi kuin P :n koko ), voimme lineaaristen algebramenetelmien avulla kertoa nämä erilaiset suhteet siten, että kaikkien alkutekijöiden potenssit kääntyvät. tasaiseksi. Tämä antaa meille vertailukelpoisuuden neliöille modulo , jotka ovat muotoa a 2 ≡ b 2 (mod n ), joka voidaan muuntaa luvun n kertoimeksi , n = gcd ( a - b , n ) × gcd ( a + b , n ). Tällainen hajottaminen voi olla triviaali (eli n = n × 1), jolloin kannattaa yrittää uudelleen toisella suhdeyhdistelmällä. Jos olemme onnekkaita, saamme ei-triviaalin n: n jakajaparin ja algoritmi päättyy.

Esimerkki

Jaetaan luku n = 187 rationaalisen seulan avulla. Kokeillaan lukua B =7, jolle joukko P  = {2,3,5,7} toimii tekijöiden perustana. Ensimmäinen askel on tarkistaa, onko luku n jaollinen joukon P luvuilla . On selvää, että tapauksessa, jossa n on jaollinen jollakin näistä alkuluvuista, olemme löytäneet ratkaisun. 187 ei kuitenkaan ole jaollinen 2:lla, 3:lla, 5:llä tai 7:llä. Seuraavassa vaiheessa etsitään sopivia z -arvoja , sopivia lukuja ovat 2, 5, 9 ja 56. Neljä z -arvoa antavat suhteet modulo 187:

• 2 1 3 0 5 0 7 0 = 2 ≡ 189 = 2 0 3 3 5 0 7 1 .............(1)
• 2 0 3 0 5 1 7 0 = 5 ≡ 192 = 2 6 3 1 5 0 7 0 .............(2)
• 2 0 3 2 5 0 7 0 = 9 ≡ 196 = 2 2 3 0 5 0 7 2 .............(3)
• 2 3 3 0 5 0 7 1 = 56 ≡ 243 = 2 0 3 5 5 0 7 0 .............(4)

Nyt yhdistämme nämä suhteet eri tavoin ja päädymme tasaisiin tehoihin. Esimerkiksi,

• (1)×(4): Kertomalla nämä suhteet ja kumoamalla yhteisen kertoimen 7 (mikä voimme tehdä, koska 7, joka on P :n jäsen , on koprime arvoon n [1] ). Vertailu yksinkertaistetaan arvoon 2 4 ≡ 3 8 (mod n ) tai 4 2 ≡ 81 2 (mod n ). Saamme hajotuksen 187 = gcd(81-4.187) × gcd(81+4.187) = 11×17.

Vaihtoehtoisesti yhtälöllä (3) on jo haluttu muoto:

• (3): Se on 3 2 ≡ 14 2 (mod n ), mikä antaa laajennuksen 187 = gcd(14-3.187) × gcd(14+3.187) = 11×17.

Algoritmin rajoitukset

Rationaalinen seula, kuten lukukentän yleinen seula, ei voi saada lukujen hajotusta muotoa p m , jossa p on alkuluku ja m on kokonaisluku. Ongelma ei ole liian suuri - tilastollisesti tällaiset luvut ovat harvinaisia ​​ja lisäksi on yksinkertainen ja nopea prosessi tarkistaa, että tietyllä numerolla on tällainen muoto. Ilmeisesti tyylikkäin tapa on tarkistaa, onko 1 < b < log(n), käyttämällä Newtonin juurimenetelmän kokonaislukuversiota [2]

Suurin ongelma on löytää lukuja z siten, että sekä z että z + n ovat B -sileitä . Minkä tahansa B: n kohdalla B -sileiden lukujen osuus pienenee nopeasti numerokoon mukaan. Joten jos n on suuri (esimerkiksi sata numeroa), on vaikeaa tai lähes mahdotonta löytää tarpeeksi z :tä, jotta algoritmi toimisi. Yleisen lukukenttäseula-algoritmin etuna on, että jollekin positiiviselle kokonaisluvulle d (yleensä 3 tai 5) täytyy löytää tasaisia ​​kertalukua n 1/ d olevia lukuja tämän algoritmin vaatiman kertaluvun n sijaan .

Muistiinpanot

1. ↑ Huomaa, että yleisiä tekijöitä ei yleensä voi peruuttaa vertailulla, mutta tässä tapauksessa ne voidaan peruuttaa, koska kaikki tekijäkannan alkuluvut ovat n : n koprimeja . Katso käänteinen kertolasku modulaarisessa aritmetiikassa
2. ↑ R. Crandall, J. Papadopoulos, AKS-luokan primiteettitestien toteutuksesta Arkistoitu 5. lokakuuta 2012 Wayback Machinessa

Kirjallisuus

• AK Lenstra, HW Lenstra, Jr., MS Manasse, JM Pollard. Yhdeksännen Fermat-luvun faktorointi // Math. Comp. - 1993. - Numero. 61 . - S. 319-349 . . Artikkelin esikatseluversio on saatavilla osoitteessa
• Numerokenttäseulan kehitys / AK Lenstra, HW Lenstra. - New York: Springer-Verlag, 1993. - T. 1554. - (Matematiikan luentomuistiinpanot).