Rationell såll

En rationell sikt är en allmän algoritm för att faktorisera heltal till primtalsfaktorer . Algoritmen är ett specialfall av den allmänna talfältssiktmetoden . Även om den är mindre effektiv än den allmänna algoritmen, är den konceptuellt enklare. Algoritmen kan hjälpa till att förstå hur den allmänna talfältssiktmetoden fungerar.

Metod

Antag att vi försöker faktorisera ett sammansatt tal n . Vi definierar gränsen för B och basen av faktorer (som vi kommer att beteckna med P ), mängden av alla primtal mindre än eller lika med B . Vi letar sedan efter ett positivt heltal z så att både z och z+n är B -släta , det vill säga alla deras primtalsdelare finns i P . Vi kan därför skriva för lämpliga krafter $a_{k}$

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

och även för lämpliga vi har $b_{k}$

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

Men och är modulo-jämförbara , så varje sådant heltal z som vi hittar ger en modulo multiplikationslänk (mod n ) bland alla element 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örsnamn {(mod} \;n\operatörsnamn {)}

(där a i och b i är icke-negativa heltal.)

När vi har genererat tillräckligt många av dessa förhållanden (vanligtvis tillräckligt för att antalet sådana förhållanden är något större än storleken på P ), kan vi använda linjära algebrametoder för att multiplicera dessa olika förhållanden på ett sådant sätt att potenserna för alla primfaktorer vänder ut att vara jämn. Detta ger oss en jämförbarhet av kvadrater modulo av formen a 2 ≡ b 2 (mod n ), som kan omvandlas till en faktorisering av talet n , n = gcd ( a - b , n ) × gcd ( a + b , n ). En sådan nedbrytning kan vara trivial (det vill säga n = n × 1), i vilket fall man bör försöka igen med en annan kombination av förhållanden. Om vi har tur får vi ett icke-trivialt par av divisorer av n och algoritmen kommer att avslutas.

Exempel

Låt oss faktorisera talet n = 187 med hjälp av en rationell sikt. Låt oss prova talet B =7, för vilket mängden P = {2,3,5,7} fungerar som bas för faktorer. Det första steget är att kontrollera om talet n är delbart med tal från mängden P . Det är tydligt att i fallet när n är delbart med ett av dessa primtal har vi hittat en lösning. 187 är dock inte delbart med 2, 3, 5 eller 7. I nästa steg letar vi efter lämpliga z- värden , 2, 5, 9 och 56 är lämpliga tal. De fyra z- värdena ger kvoterna 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 kombinerar vi dessa förhållanden på olika sätt och slutar med jämna styrkor. Till exempel,

(1)×(4): Efter att ha multiplicerat dessa förhållanden och annullerat den gemensamma faktorn 7 (vilket vi kan göra eftersom 7, som är en medlem av P , är coprime till n [1] ). Jämförelsen är förenklad till 2 4 ≡ 3 8 (mod n ), eller 4 2 ≡ 81 2 (mod n ). Vi får sönderdelningen 187 = gcd(81-4.187) × gcd(81+4.187) = 11×17.

Alternativt har ekvation (3) redan den önskade formen:

(3): Det står 3 2 ≡ 14 2 (mod n ), vilket ger expansionen 187 = gcd(14-3.187) × gcd(14+3.187) = 11×17.

Begränsningar för algoritmen

En rationell såll, som en allmän såll av ett talfält, kan inte erhålla en nedbrytning av tal av formen p m , där p är ett primtal och m är ett heltal. Problemet är inte för stort - statistiskt sett är sådana siffror sällsynta och dessutom finns det en enkel och snabb process för att kontrollera att ett givet tal har en sådan form. Tydligen är den mest eleganta metoden att kontrollera om för 1 < b < log(n), med hjälp av heltalsversionen av Newtons rotmetod [2] $\lfloor n^{1/b}\rfloor ^{b}=n$

Det största problemet är att hitta siffror z så att både z och z + n är B -släta . För varje givet B, minskar andelen B -jämna tal snabbt med nummerstorleken. Så om n är stort (säg hundra siffror) kommer det att vara svårt eller nästan omöjligt att hitta tillräckligt med z för att få algoritmen att fungera. Fördelen med den allmänna talfältssiktalgoritmen är att man måste hitta jämna tal av ordning n 1/ d för något positivt heltal d (vanligtvis 3 eller 5), istället för ordning n som krävs av denna algoritm.

Anteckningar

↑ Observera att gemensamma faktorer i allmänhet inte kan annulleras genom jämförelse, men i det här fallet kan de annulleras eftersom alla primtal i faktorbasen är coprime till n . Se invers multiplikation i modulär aritmetik
↑ R. Crandall, J. Papadopoulos, Om implementeringen av AKS-klass primalitetstester Arkiverad 5 oktober 2012 på Wayback Machine

Litteratur

AK Lenstra, HW Lenstra, Jr., MS Manasse, JM Pollard. Faktoriseringen av det nionde fermatnumret // Math. Comp. - 1993. - Utgåva. 61 . - S. 319-349 . . En förhandsversion av artikeln finns tillgänglig på
Utvecklingen av nummerfältssikten / AK Lenstra, HW Lenstra. - New York: Springer-Verlag, 1993. - T. 1554. - (Lecture Notes in Mathematics).

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm