Racionální síto

Racionální síto je obecný algoritmus pro rozklad celých čísel na prvočinitele . Algoritmus je speciálním případem metody obecného číselného pole síta . I když je méně účinný než obecný algoritmus, je koncepčně jednodušší. Algoritmus může pomoci porozumět tomu, jak funguje metoda obecného síta číselného pole.

Metoda

Předpokládejme, že se pokoušíme faktorizovat složené číslo n . Definujeme hranici B a bázi faktorů (kterou budeme označovat P ), množinu všech prvočísel menších nebo rovných B . Pak hledáme kladné celé číslo z takové, že z i z+n jsou B -hladké , to znamená, že všechny jejich prvotřídní dělitele jsou obsaženy v P . Můžeme tedy psát pro vhodné mocniny $a_{k}$

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

a také pro vhodné máme $b_{k}$

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

Ale a jsou modulo srovnatelné , takže každé takové celé číslo z , které najdeme, dává modulo násobící odkaz ( mod n ) mezi všemi prvky P , tj. $z$ $z+n$ $n$

\prod _{p_{i}\in P}p_{i}^{a_{i}}\equiv \prod _{p_{i}\in P}p_{i}^{b_{i} }\;\operatorname {(mod} \;n\operatorname {)}

(kde ai a b i jsou nezáporná celá čísla. )

Když jsme vygenerovali dostatek těchto poměrů (obvykle dost, že počet takových poměrů je o něco větší než velikost P ), můžeme použít metody lineární algebry k vynásobení těchto různých poměrů takovým způsobem, že mocniny všech prvočinitelů se změní. být vyrovnaný. Tím získáme srovnatelnost čtverců modulo tvaru a 2 ≡ b 2 (mod n ), které lze převést na faktorizaci čísla n , n = gcd ( a - b , n ) × gcd ( a + b , n ). Takový rozklad může být triviální (tj. n = n × 1), v takovém případě bychom to měli zkusit znovu s jinou kombinací poměrů. Pokud budeme mít štěstí, dostaneme netriviální dvojici dělitelů n a algoritmus skončí.

Příklad

Rozložme číslo n = 187 na faktor pomocí racionálního síta. Zkusme číslo B =7, pro které jako základ faktorů slouží množina P = {2,3,5,7}. Prvním krokem je zkontrolovat, zda je číslo n dělitelné čísly z množiny P . Je jasné, že v případě, kdy n je dělitelné jedním z těchto prvočísel, jsme našli řešení. 187 však není dělitelné 2, 3, 5 nebo 7. V dalším kroku hledáme vhodné hodnoty z , vhodná čísla jsou 2, 5, 9 a 56. Čtyři hodnoty z dávají poměry 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)

Nyní tyto poměry různými způsoby kombinujeme a končíme se sudými mocninami. Například,

(1)×(4): Po vynásobení těchto poměrů a zrušení společného faktoru 7 (což můžeme udělat, protože 7 je členem P , je coprime k n [1] ). Porovnání je zjednodušeno na 2 4 ≡ 3 8 (mod n ), nebo 4 2 ≡ 81 2 (mod n ). Dostaneme rozklad 187 = gcd(81-4,187) × gcd(81+4,187) = 11×17.

Alternativně rovnice (3) již má požadovaný tvar:

(3): Čte 3 2 ≡ 14 2 (mod n ), což dává expanzi 187 = gcd(14-3.187) × gcd(14+3.187) = 11×17.

Omezení algoritmu

Racionální síto, stejně jako obecné síto číselného pole, nemůže získat rozklad čísel tvaru p m , kde p je prvočíslo a m je celé číslo. Problém to není příliš velký – statisticky jsou taková čísla vzácná a navíc existuje jednoduchý a rychlý proces kontroly, zda dané číslo má takový tvar. Zřejmě nejelegantnější metodou je zkontrolovat, zda pro 1 < b < log(n), pomocí celočíselné verze Newtonovy kořenové metody [2] $\lfloor n^{1/b}\rfloor ^{b}=n$

Největší problém je najít čísla z taková, že z i z + n jsou B -hladké . Pro každé dané B se podíl B -hladkých čísel rychle snižuje s velikostí čísla. Pokud je tedy n velké (řekněme sto číslic), bude obtížné nebo téměř nemožné najít dostatek z , aby algoritmus fungoval. Výhodou algoritmu obecného síta pole čísel je, že je třeba najít hladká čísla řádu n 1/ d pro nějaké kladné celé číslo d (obvykle 3 nebo 5), místo řádu n , jak to vyžaduje tento algoritmus.

Poznámky

↑ Všimněte si, že společné faktory nelze obecně zrušit srovnáním, ale v tomto případě je lze zrušit, protože všechna prvočísla v základu faktoru jsou coprime k n . Viz inverzní násobení v modulární aritmetice
↑ R. Crandall, J. Papadopoulos, O implementaci testů primality třídy AKS Archivováno 5. října 2012 na Wayback Machine

Literatura

AK Lenstra, HW Lenstra, Jr., MS Manasse, JM Pollard. Faktorizace devátého Fermatova čísla // Matematika. Comp. - 1993. - Vydání. 61 . - S. 319-349 . . Náhledová verze článku je k dispozici na
Vývoj číselného pole síta / AK Lenstra, HW Lenstra. - New York: Springer-Verlag, 1993. - T. 1554. - (Poznámky z přednášky z matematiky).

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin