Rationel sigte

En rationel sigte er en generel algoritme til faktorisering af heltal til primfaktorer . Algoritmen er et specialtilfælde af den generelle talfeltsigtemetode . Selvom den er mindre effektiv end den generelle algoritme, er den konceptuelt enklere. Algoritmen kan hjælpe med at forstå, hvordan den generelle talfeltsigtemetode fungerer.

Metode

Antag, at vi forsøger at faktorisere et sammensat tal n . Vi definerer grænsen for B og grunden af faktorer (som vi vil betegne med P ), mængden af alle primtal mindre end eller lig med B . Vi leder derefter efter et positivt heltal z , således at både z og z+n er B -glat , det vil sige, at alle deres primtal divisorer er indeholdt i P . Vi kan derfor skrive for passende beføjelser $a_{k}$

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

og også for passende vi har $b_{k}$

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

Men og er modulo sammenlignelige , så ethvert sådant heltal z , som vi finder, giver et modulo multiplikationslink (mod n ) blandt alle elementer i P , dvs. $z$ $z+n$ $n$

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

(hvor a i og b i er ikke-negative heltal.)

Når vi har genereret nok af disse forhold (normalt nok til, at antallet af sådanne forhold er lidt større end størrelsen af P ), kan vi bruge lineære algebrametoder til at multiplicere disse forskellige forhold på en sådan måde, at potenserne af alle primfaktorer vender ude at være lige. Dette vil give os en sammenlignelighed af kvadrater modulo af formen a 2 ≡ b 2 (mod n ), som kan konverteres til en faktorisering af tallet n , n = gcd ( a - b , n ) × gcd ( a + b , n ). En sådan nedbrydning kan være triviel (det vil sige n = n × 1), i hvilket tilfælde man skal prøve igen med en anden kombination af forhold. Hvis vi er heldige, får vi et ikke-trivielt par divisorer af n , og algoritmen vil afslutte.

Eksempel

Lad os faktorisere tallet n = 187 ved hjælp af en rationel sigte. Lad os prøve tallet B =7, hvor mængden P = {2,3,5,7} tjener som basis for faktorer. Det første trin er at kontrollere, om tallet n er deleligt med tal fra mængden P . Det er klart, at i det tilfælde, hvor n er delelig med en af disse primtal, har vi fundet en løsning. 187 er dog ikke deleligt med 2, 3, 5 eller 7. I næste trin leder vi efter passende z- værdier , 2, 5, 9 og 56 er passende tal. De fire z- værdier giver forholdene 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)

Nu kombinerer vi disse forhold på forskellige måder og ender med lige kræfter. For eksempel,

(1)×(4): Efter at have ganget disse forhold og annulleret den fælles faktor 7 (hvilket vi kan gøre, da 7, som er et medlem af P , er coprime til n [1] ). Sammenligningen er simplificeret til 2 4 ≡ 3 8 (mod n ), eller 4 2 ≡ 81 2 (mod n ). Vi får dekomponeringen 187 = gcd(81-4.187) × gcd(81+4.187) = 11×17.

Alternativt har ligning (3) allerede den ønskede form:

(3): Den lyder på 3 2 ≡ 14 2 (mod n ), hvilket giver udvidelsen 187 = gcd(14-3.187) × gcd(14+3.187) = 11×17.

Begrænsninger af algoritmen

En rationel sigte kan ligesom en generel sigte af et talfelt ikke opnå en dekomponering af tal af formen p m , hvor p er et primtal og m er et heltal. Problemet er ikke for stort - statistisk set er sådanne tal sjældne, og derudover er der en enkel og hurtig proces til at kontrollere, at et givent tal har en sådan form. Tilsyneladende er den mest elegante metode at kontrollere, om for 1 < b < log(n), ved hjælp af heltalsversionen af Newtons rodmetode [2] $\lgulv n^{1/b}\rgulv ^{b}=n$

Det største problem er at finde tallene z , således at både z og z + n er B -glatte . For et givet B falder andelen af B -glatte tal hurtigt med talstørrelsen. Så hvis n er stor (f.eks. hundrede cifre), vil det være svært eller næsten umuligt at finde nok z til at få algoritmen til at fungere. Fordelen ved den generelle talfeltsigte-algoritme er, at man skal finde jævne tal af orden n 1/ d for et positivt heltal d (normalt 3 eller 5), i stedet for orden n som krævet af denne algoritme.

Noter

↑ Bemærk, at fælles faktorer generelt ikke kan annulleres ved sammenligning, men i dette tilfælde kan de annulleres, fordi alle primtal i faktorgrundlaget er coprime til n . Se invers multiplikation i modulær aritmetik
↑ R. Crandall, J. Papadopoulos, Om implementeringen af AKS-klasse primalitetstest Arkiveret 5. oktober 2012 på Wayback Machine

Litteratur

AK Lenstra, HW Lenstra, Jr., MS Manasse, JM Pollard. Faktoriseringen af det niende Fermat-tal // Matematik. Comp. - 1993. - Udgave. 61 . - S. 319-349 . . En forhåndsvisning af artiklen er tilgængelig på
Udviklingen af Number Field Sieve / AK Lenstra, HW Lenstra. - New York: Springer-Verlag, 1993. - T. 1554. - (Lecture Notes in Mathematics).

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme