Racionális szita

A racionális szita egy általános algoritmus egész számok prímtényezőkké alakítására . Az algoritmus az általános számmező szita módszer speciális esete . Bár kevésbé hatékony , mint az általános algoritmus, fogalmilag egyszerűbb. Az algoritmus segíthet megérteni, hogyan működik az általános számmező szita módszer.

Módszer

Tegyük fel, hogy egy n összetett számot próbálunk tizedesre sorolni . Meghatározzuk B határát és a tényezők bázisát (amit P -vel fogunk jelölni), a B -nél kisebb vagy azzal egyenlő prímek halmazát . Ezután keresünk egy z pozitív egész számot , amelyre mind z , mind z+n B -sima , azaz minden prímosztóját P tartalmazza . Ezért írhatunk megfelelő képességekre $a_{k}$

$z=\prod _{p_{i}\in P}p_{i}^{a_{i}}$ ,

és megfelelőnek is van nálunk $b_{k}$

$z+n=\prod _{p_{i}\in P}p_{i}^{b_{i))$ .

De az és modulo összehasonlíthatóak , így minden olyan z egész szám , amelyet találunk, egy modulo szorzókapcsolatot (mod n ) ad P minden eleme között , azaz. $z$ $z+n$ $n$

\prod _{p_{i}\in P}p_{i}^{a_{i}}\equiv \prod _{p_{i}\in P}p_{i}^{b_{i} }\;\operátornév {(mod} \;n\operátornév {)}

(ahol a i és b i nemnegatív egész számok.)

Ha ezekből az arányokból elegendő mennyiséget generáltunk (általában annyit, hogy az ilyen arányok száma valamivel nagyobb, mint P ), lineáris algebrai módszerekkel megszorozhatjuk ezeket a különböző arányokat úgy, hogy az összes prímtényező hatványa megforduljon. egyenletesnek kell lennie. Ez megadja az a 2 ≡ b 2 (mod n ) alakú modulo négyzetek összehasonlíthatóságát , amely átváltható az n szám faktorizálására , n = gcd ( a - b , n ) × gcd ( a + b , n ). Egy ilyen bontás lehet triviális (azaz n = n × 1), ebben az esetben meg kell próbálni újra egy másik aránykombinációval. Ha szerencsénk van, kapunk n nem triviális osztópárt, és az algoritmus leáll.

Példa

Tényezőzzük az n = 187 számot racionális szita segítségével. Próbáljuk meg a B =7 számot , amelyhez a P = {2,3,5,7} halmaz szolgál a tényezők alapjául. Első lépésként ellenőrizzük, hogy az n szám osztható-e a P halmazból származó számokkal . Nyilvánvaló, hogy abban az esetben, ha n osztható ezen prímszámok egyikével, találtunk megoldást. A 187 azonban nem osztható 2-vel, 3-mal, 5-tel vagy 7-tel. A következő lépésben keressük a megfelelő z értékeket , 2, 5, 9 és 56 a megfelelő számok. A négy z -érték megadja a modulo arányokat 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)

Most különféle módokon kombináljuk ezeket az arányokat, és egyenletes erőket kapunk. Például,

(1)×(4): Ezeknek az arányoknak a szorzata és a 7 közös tényező törlése után (amit megtehetünk, mivel a 7, mivel P tagja , koprím n -re [1] ). Az összehasonlítást 2 4 ≡ 3 8 (mod n ), vagy 4 2 ≡ 81 2 (mod n ) értékre egyszerűsítjük. A 187 = gcd(81-4.187) × gcd(81+4.187) = 11×17 bontást kapjuk.

Alternatív megoldásként a (3) egyenlet már rendelkezik a kívánt formában:

(3): 3 2 ≡ 14 2 (mod n ), ami a 187 = gcd(14-3.187) × gcd(14+3.187) = 11×17 kiterjesztést adja.

Az algoritmus korlátai

A racionális szita, akárcsak egy számmező általános szitája, nem tudja elérni a p m alakú számok dekompozícióját , ahol p prímszám, m pedig egész szám. A probléma nem túl nagy – statisztikailag ritkák az ilyen számok, ráadásul van egy egyszerű és gyors folyamat annak ellenőrzésére, hogy egy adott számnak van-e ilyen formája. Úgy tűnik, a legelegánsabb módszer annak ellenőrzése, hogy 1 < b < log(n)-e , a Newton-féle gyökérmetódus egész számú változatával [2] $\lfloor n^{1/b}\rfloor ^{b}=n$

A legnagyobb probléma a z számok megtalálása úgy, hogy z és z + n is B -sima . Bármely adott B esetén a B -sima számok aránya gyorsan csökken a szám méretével. Tehát ha n nagy (mondjuk száz számjegy), akkor nehéz vagy szinte lehetetlen lesz elegendő z -t találni ahhoz , hogy az algoritmus működjön. Az általános számmező szita algoritmus előnye, hogy valamilyen d pozitív egészhez (általában 3 vagy 5) kell n 1/ d rendű sima számokat találni , ahelyett , hogy az algoritmus n sorrendű lenne .

Jegyzetek

↑ Megjegyzendő, hogy a közös tényezőket általában nem lehet törölni összehasonlítással, de ebben az esetben törölhetők, mert a faktorbázis minden prímje n -re koprím . Lásd az inverz szorzást a moduláris aritmetikában
↑ R. Crandall, J. Papadopoulos, Az AKS-osztályú elsődlegességi tesztek végrehajtásáról Archiválva : 2012. október 5. a Wayback Machine -nél

Irodalom

AK Lenstra, HW Lenstra, Jr., MS Manasse, JM Pollard. A kilencedik Fermat-szám faktorizálása // Math. Összeg. - 1993. - Kiadás. 61 . - S. 319-349 . . A cikk előnézeti változata a következő címen érhető el
A számmező szita fejlesztése / AK Lenstra, HW Lenstra. - New York: Springer-Verlag, 1993. - T. 1554. - (Matematikai előadásjegyzetek).

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus