Rationell såll

Inom matematiken är den rationella sikten en allmän algoritm för att faktorisera heltal till primtalsfaktorer . Det är ett specialfall av den allmänna nummerfältssilen . Även om den är mindre effektiv än den allmänna algoritmen, är den konceptuellt enklare. Det fungerar som ett hjälpsamt första steg för att förstå hur den allmänna nummerfältssilen fungerar.

Metod

Anta att vi försöker faktorisera det sammansatta talet n . Vi väljer en bunden B , och identifierar faktorbasen (som vi kommer att kalla P ), mängden av alla primtal mindre än eller lika med B . Därefter söker vi efter positiva heltal z så att både z och z+n är B - jämna — dvs alla deras primtalsfaktorer är i P . Vi kan därför skriva, för lämpliga exponenter $a_{i}$ ,

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

och likaså, för lämplig $b_{i}$ , har vi

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

Men $\displaystyle z}$ (mod n { och $z+n$ är kongruenta modulo $n$ , så varje sådant heltal z som vi hittar ger en multiplikativ relation ) bland elementen i P , dvs

$\prod _{p_{i}\in P}p_{i}^{a_{i}}\ equiv \prod _{p_{i}\in P}p_{i}^{b_{i}}{\pmod {n}}$

(där a _i och bi ₎ är icke-negativa heltal.

När vi har genererat tillräckligt många av dessa relationer (det räcker i allmänhet att antalet relationer är några fler än storleken på P ), kan vi använda linjär algebras metoder för att multiplicera dessa olika relationer på ett sådant sätt att exponenterna för primtal är alla jämna. Detta ger oss en kongruens av kvadrater av formen a ² ≡b ² (mod n ), som kan omvandlas till en faktorisering av n = gcd ( a - b , n )×gcd( a + b , n ). Denna faktorisering kan visa sig vara trivial (dvs n = n ×1), i vilket fall vi måste försöka igen med en annan kombination av relationer; men med tur kommer vi att få ett icke-trivialt par av faktorer av n , och algoritmen kommer att avslutas.

Exempel

Vi kommer att faktorisera heltal n = 187 med hjälp av den rationella sikten. Vi provar godtyckligt värdet B =7, vilket ger faktorbasen P = {2,3,5,7}. Det första steget är att testa n för delbarhet med var och en av medlemmarna i P ; klart om n är delbart med ett av dessa primtal, så är vi redan klara. Men 187 är inte delbart med 2, 3, 5 eller 7. Därefter söker vi efter lämpliga värden på z ; de första är 2, 5, 9 och 56. De fyra lämpliga värdena på z ger fyra multiplikativa relationer (mod 187):

$2^{1}3^{0}5^{0}7^{0}=2\equiv 189=2^{0} 3^{3}5^{0}7^{1}$

 

 

 

 

()

$2^{0}3^{0}5^{1}7^{0}=5\equiv 192=2^{6} 3^{1}5^{0}7^{0}$

 

 

 

 

()

$2^{0}3^{2}5^{0}7^{0}=9\equiv 196=2^{2} 3^{0}5^{0}7^{2}$

 

 

 

 

()

$2^{3}3^{0}5^{0}7^{1}=56\equiv 243=2^{0} 3^{5}5^{0}7^{0}$

 

 

 

 

()

Det finns nu flera väsentligt olika sätt att kombinera dessa och sluta med jämna exponenter. Till exempel,

• ( 1 )×( 4 ): Efter att ha multiplicerat dessa och raderat den gemensamma faktorn 7 (vilket vi kan göra eftersom 7, som är en medlem av P , redan har bestämts vara coprime med n ), minskar detta till 2 ⁴ ≡ 38 (mod n ) eller 4 ² ≡ 812 ⁽ mod n ⁾ . Den resulterande faktoriseringen är 187 = gcd(81-4,187) × gcd(81+4,187) = 11×17.

Alternativt är ekvation ( 3 ) redan i rätt form:

• ( 3 ): Detta säger 3 ² ≡ 14 ² (mod n ), vilket ger faktoriseringen 187 = gcd(14-3,187) × gcd(14+3,187) = 11×17.

Begränsningar av algoritmen

Den rationella sikten, liksom den allmänna talfältssilen, kan inte faktorisera tal av formen p ^m , där p är ett primtal och m är ett heltal. Detta är dock inte ett stort problem - sådana siffror är statistiskt sällsynta, och dessutom finns det en enkel och snabb process för att kontrollera om ett givet nummer är av denna form. Den mest eleganta metoden är förmodligen att kontrollera om $\lfloor n^{1/b}\rfloor ^{b}=n$ gäller för någon 1 < b < log(n) använder en heltalsversion av Newtons metod för rotextraktionen.

Det största problemet är att hitta ett tillräckligt antal z så att både z och z + n är B -släta. För varje givet B minskar andelen tal som är B -släta snabbt med storleken på talet. Så om n är stort (säg hundra siffror) kommer det att vara svårt eller omöjligt att hitta tillräckligt med z för att algoritmen ska fungera. Fördelen med den allmänna talfältssikten är att man bara behöver söka efter jämna tal av ordningen n ^{1/ d} för något positivt heltal d (typiskt 3 eller 5), snarare än av ordningen n som krävs här.

• AK Lenstra, HW Lenstra, Jr., MS Manasse och JM Pollard, The Factorization of the Ninth Fermat Number, Math. Comp. 61 (1993), 319-349. Tillgänglig på [2] .
• AK Lenstra, HW Lenstra, Jr. (red.) The Development of the Number Field Sieve, Lecture Notes in Mathematics 1554, Springer-Verlag, New York, 1993.