Kvadratisk sil

Den kvadratiska sållalgoritmen ( QS ) är en heltalsfaktoriseringsalgoritm och i praktiken den näst snabbaste metoden som är känd (efter den allmänna talfältssikten) . Det är fortfarande snabbast för heltal under 100 decimalsiffror eller så, och är betydligt enklare än talfältssilen. Det är en faktoriseringsalgoritm för allmänt ändamål, vilket innebär att dess körtid enbart beror på storleken på det heltal som ska faktoriseras, och inte på speciell struktur eller egenskaper. Den uppfanns av Carl Pomerance 1981 som en förbättring av Schroeppels linjära såll.

Grundläggande mål

Algoritmen försöker sätta upp en kongruens av kvadrater modulo n (heltalet som ska faktoriseras), vilket ofta leder till en faktorisering av n . Algoritmen fungerar i två faser: datainsamlingsfasen , där den samlar in information som kan leda till en kongruens av kvadrater; och databehandlingsfasen , där den lägger all data den har samlat in i en matris och löser den för att få en kongruens av kvadrater. Datainsamlingsfasen kan lätt parallelliseras till många processorer, men databehandlingsfasen kräver stora mängder minne och är svår att parallellisera effektivt över många noder eller om bearbetningsnoderna inte var och en har tillräckligt med minne för att lagra hela matrisen. Block Wiedemann-algoritmen kan användas i fallet med ett fåtal system som vart och ett kan hålla matrisen.

Den naiva metoden för att hitta en kongruens av kvadrater är att välja ett slumpmässigt tal, kvadrera det, dividera med n och hoppas att den minst icke-negativa resten är en perfekt kvadrat . Till exempel, $80^{2}\equiv 441=21^{2}{\pmod {5959}}$ . Detta tillvägagångssätt finner en kongruens av kvadrater endast sällan för stort n , men när det hittar en, oftare än inte, är kongruensen icke-trivial och faktoriseringen är fullständig. Detta är ungefär grunden för Fermats faktoriseringsmetod .

Den kvadratiska sikten är en modifiering av Dixons faktoriseringsmetod .

Den allmänna körtiden som krävs för kvadratsikten (för att faktorisera ett heltal n ) är

$e^{(1+o(1)){\sqrt {\ln n\ln \ln n}}}=L_{n}\left[1/2,1\right]$

i L-notationen .

Konstanten e är basen för den naturliga logaritmen.

Tillvägagångssättet

För att faktorisera heltal n , innebär Fermats metod en sökning efter ett enda tal a , n ^1/2 < a < n −1 , så att resten av en ² dividerat med n är en kvadrat. Men dessa är svåra att hitta. Den kvadratiska sikten består av att beräkna resten av en ² / n för flera a och sedan hitta en delmängd av dessa vars produkt är en kvadrat. Detta kommer att ge en kongruens av kvadrater.

Överväg till exempel att försöka faktorisera talet 1649. Vi har: $41^{2}\equiv 32,42^{2}\ equiv 115,43^{2}\equiv 200{\pmod {1649}}$ . Inget av heltalen $32,115,200$ är en kvadrat, men produkten $32\cdot 200=80^{2}$ är en kvadrat. Det hade vi också

$32\cdot 200\equiv 41^{2}\cdot 43(4 1c2} )^{2}\equiv 114^{2}{\pmod {1649}}$

sedan $41\cdot 43\equiv 114{\pmod {1649}}$ . Observationen att $32\cdot 200=80^{2}$ ger alltså en kongruens av kvadrater

$114^{2}\equiv 80^{2}{\pmod {1649}}.$

Därför $114^{2}-80^{2}=(114+80)\cdot -80)=194\cdot 34=k\cdot 1649$ för något heltal $k$ . Vi kan då faktorisera

${\displaystyle 1649=\gcd(194,1649)\cdot \gcd(34,1649)=94,1649)=9$

använda den euklidiska algoritmen för att beräkna den största gemensamma divisorn .

⁰ Så problemet har nu reducerats till: givet en uppsättning heltal, hitta en delmängd vars produkt är en kvadrat. Genom aritmetikens grundsats kan vilket positivt heltal som helst skrivas unikt som en produkt av primtal . Vi gör detta i ett vektorformat; till exempel är primtalsfaktoriseringen av 504 2 ³ 3 ² 5 7 ¹ , den representeras därför av exponentvektorn (3,2,0,1). Att multiplicera två heltal motsvarar sedan att addera deras exponentvektorer. Ett tal är en kvadrat när dess exponentvektor är jämn i varje koordinat. Till exempel, vektorerna (3,2,0,1) + (1,0,0,1) = (4,2,0,2), så (504)(14) är en kvadrat. Att söka efter en kvadrat kräver endast kunskap om pariteten för talen i vektorerna, så det räcker att beräkna dessa vektorer mod 2: (1,0,0,1) + (1,0,0,1) = (0 ,0,0,0). Så givet en uppsättning av (0,1)-vektorer måste vi hitta en delmängd som adderas till nollvektorn mod 2.

Detta är ett linjärt algebraproblem eftersom ringen $\mathbb {Z} /2\mathbb {Z}$ kan betraktas som Galois-fältet av ordning 2, det vill säga vi kan dividera med alla icke-noll tal (det finns bara ett, nämligen 1) vid beräkning av modulo 2. Det är en linjär algebras sats att med fler vektorer än varje vektor har poster så finns alltid ett linjärt beroende . Det kan hittas genom Gaussisk eliminering . Men att helt enkelt kvadrera många slumpmässiga tal mod n producerar ett mycket stort antal olika primtalsfaktorer , och så mycket långa vektorer och en mycket stor matris. Tricket är att leta specifikt efter siffror a så att en ² mod n bara har små primtalsfaktorer (de är jämna tal ). De är svårare att hitta, men att bara använda jämna siffror gör att vektorerna och matriserna blir mindre och mer lätthanterliga. Den kvadratiska sikten söker efter jämna tal med hjälp av en teknik som kallas siktning , som diskuteras senare, från vilken algoritmen har fått sitt namn.

Algoritmen

För att sammanfatta har den grundläggande kvadratiska sållalgoritmen dessa huvudsteg:

1. Välj en jämnhetsgräns B . Talet π( B ), som anger antalet primtal mindre än B , kommer att styra både längden på vektorerna och antalet vektorer som behövs.
2. Använd siktning för att lokalisera π( B ) + 1 siffror a _i så att b _i = ( a _i ² mod n ) är B -slät.
3. Faktorisera b _i och generera exponentvektorer mod 2 för var och en.
4. Använd linjär algebra för att hitta en delmängd av dessa vektorer som adderas till nollvektorn. Multiplicera motsvarande a _i tillsammans och ge resultatet mod n namnet a ; på samma sätt multiplicera b _i tillsammans vilket ger en B -slät kvadrat b ² .
5. Vi är nu kvar med likheten a ² = b ² mod n från vilken vi får två kvadratrötter av ( a ² mod n ), en genom att ta kvadratroten i heltal av b ² nämligen b , och den andra den a beräknade i steg 4.
6. Vi har nu den önskade identiteten: $(a+b)(ab)\equiv 0{\pmod {n}}$ . Beräkna GCD för n med skillnaden (eller summan) av a och b . Detta ger en faktor, även om det kan vara en trivial faktor ( n eller 1). Om faktorn är trivial, försök igen med ett annat linjärt beroende eller annan a .

Resten av den här artikeln förklarar detaljer och förlängningar av denna grundläggande algoritm.

Algoritmens pseudokod

      
        
        
              
               
                 algoritm  Kvadratisk sikt  är  Välj jämnhetsbunden $B$ låt $t=\pi (B)$ för $i\in {1,...,t+1}$ do  Välj $x\in \{0,\pm 1,\pm 2,...\}$$a_{i}=x+\lfloor {\sqrt {n} }\rgolv$$b_{i}=a_{i}^{2}-n$ (där ${\displaystyle b_{i}=\prod _{j=1}^{t}p_{j}^{e_{i,j}}} ) while (check-p_t-smooth($ b_i  )  = false)  do  Låt $v_{i}=(v_{i,1},v_{i,2},...,v_{i,t})=(e_{i,1}{\bmod {2}},e_{i ,2}{\bmod {2}},...,e_{i,t}{\bmod {2}})$ Hitta $T\subseteq \{1,2,...,t+1\}:\summa _{i\in T}v_{i }=0\in \mathbb {Z} _{2}$ låt $x=\prod _{i\in T}a_{i}{\bmod {n} }$ låt $y=\prod _{j=1}^{t}p_{j}^{\sum _{i \in t}e_{i,j}}{\bmod {n}}$ om $x\not \equiv -y{\bmod {n}}$ och ${\ displaystyle x\not \equiv y}$ returnera  sedan  gcd(x - y, n) , gcd(x + y, n)  else :  return to main loop. 

Hur QS optimerar att hitta kongruenser

Den kvadratiska sikten försöker hitta par av heltal x och y ( x ) (där y ( x ) är en funktion av x ) som uppfyller ett mycket svagare villkor än x ² ≡ y ² (mod n ). Den väljer en uppsättning primtal som kallas faktorbasen och försöker hitta x så att den minsta absoluta återstoden av y ( x ) = x ² mod n faktoriseras helt över faktorbasen. Sådana y- värden sägs vara jämna med avseende på faktorbasen.

Faktoriseringen av ett värde på y ( x ) som delas över faktorbasen, tillsammans med värdet på x , kallas en relation . Den kvadratiska sikten påskyndar processen att hitta relationer genom att ta x nära kvadratroten ur n . Detta säkerställer att y ( x ) blir mindre, och därmed har en större chans att bli jämn.

$y(x)=\left(\left\lceil {\sqrt {n}}\right\rceil + x\right)^{2}-n{\hbox{ (där }}x{\hbox{ är ett litet heltal)}}$

$y(x)\approx 2x\left\lceil {\sqrt {n}}\right\rceil$

Detta innebär att y är i storleksordningen 2 x [ √ n ]. Men det innebär också att y växer linjärt med x gånger kvadratroten ur n .

Ett annat sätt att öka chansen för jämnhet är att helt enkelt öka storleken på faktorbasen. Det är dock nödvändigt att hitta minst en jämn relation mer än antalet primtal i faktorbasen, för att säkerställa förekomsten av ett linjärt beroende.

Partiella relationer och cykler

Även om för någon relation y ( x ) inte är jämn, kan det vara möjligt att slå samman två av dessa partiella relationer för att bilda en fullständig, om de två y är produkter av samma primtal utanför faktorbasen. [Observera att detta är ekvivalent med att utöka faktorbasen.] Till exempel, om faktorbasen är {2, 3, 5, 7} och n = 91, finns det partiella relationer:

${21^{2}\equiv 7^{1}\cdot 11{\pmod {91}}}$

${29^{2}\equiv 2^{1}\cdot 11{\pmod {91}}}$

Multiplicera dessa tillsammans:

${(21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}\cdot 11 ^{2}{\pmod {91}}}$

och multiplicera båda sidor med (11 ⁻¹ ) ² modulo 91. 11 ⁻¹ modulo 91 är 58, så:

$(58\cdot 21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}{\ pmod {91}}$

$14^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}$

skapa en fullständig relation. En sådan fullständig relation (erhållen genom att kombinera partiella relationer) kallas en cykel . Ibland leder bildandet av en cykel från två partiella relationer direkt till en kongruens av kvadrater, men sällan.

Kontrollera jämnheten genom siktning

Det finns flera sätt att kontrollera jämnheten hos y :en. Det mest uppenbara är genom provdelning , även om detta ökar körtiden för datainsamlingsfasen. En annan metod som har viss acceptans är den elliptiska kurvmetoden (ECM). I praktiken används vanligtvis en process som kallas siktning . Om f ( x ) är polynomet $f(x)=x^{2}-n$ har vi

${\begin{aligned}f(x)&=x^{2}-n\\f(x+kp)&=( x+kp)^{2}-n\\&=x^{2}+2xkp+(kp)^{2}-n\\&=f(x)+2xkp+(kp)^{2}\equiv f (x){\pmod {p}}\end{aligned}}$

Att lösa f(x) ≡ 0 (mod p ) för x genererar alltså en hel sekvens av tal y för vilka y = f ( x ), som alla är delbara med p . Detta är att hitta en kvadratrotsmodulo ett primtal, för vilket det finns effektiva algoritmer, såsom Shanks–Tonelli-algoritmen . (Det är här den kvadratiska sikten har fått sitt namn: y är ett andragradspolynom i x , och siktningsprocessen fungerar som Eratosthenes Sieve .)

Silen börjar med att nollställa varje post i en stor grupp A [] bytes. För varje p löser du andragradsekvationen mod p för att få två rötter α och β , och lägg sedan till en approximation till log( p ) till varje post för vilken y ( x ) = 0 mod p ... det vill säga A [ kp + a ] och A [ kp + p ]. Det är också nödvändigt att lösa andragradsekvationen modulo små potenser av p för att känna igen tal som är delbara med små potenser av ett faktor-bas primtal.

I slutet av faktorbasen kommer varje A [] som innehåller ett värde över ett tröskelvärde på ungefär log( x ² − n ) att motsvara ett värde på y ( x ) som delas över faktorbasen. Informationen om exakt vilka primtal som delar y ( x ) har gått förlorad, men den har bara små faktorer, och det finns många bra algoritmer för att faktorisera ett tal som är känt för att bara ha små faktorer, såsom försöksdivision med små primtal, SQUFOF , Pollard rho och ECM, som vanligtvis används i någon kombination.

Det finns många y ( x ) värden som fungerar, så faktoriseringsprocessen i slutet behöver inte vara helt tillförlitlig; ofta fungerar processerna fel på säg 5 % av insatserna, vilket kräver en liten mängd extra siktning.

Exempel på grundsikt

Detta exempel kommer att visa standardkvadratsikt utan logaritmoptimeringar eller primpotenser. Låt talet som ska faktoriseras N = 15347, därför är taket för kvadratroten ur N 124. Eftersom N är litet räcker grundpolynomet: y ( x ) = ( x + 124) ² − 15347.

Datainsamling

Eftersom N är litet behövs bara 4 primtal. De första 4 primtalen p för vilka 15347 har en kvadratrot mod p är 2, 17, 23 och 29 (med andra ord, 15347 är en kvadratisk restmodulo var och en av dessa primtal). Dessa primer kommer att ligga till grund för siktning.

Nu konstruerar vi vår sikt $V_{X}$ av $Y(X)=(X+ \lceil {\sqrt {N}}\rceil )^{2}-N=(X+124)^{2}-15347$ och påbörja siktningsprocessen för varje prime i basen, välj att sikta de första 0 ≤ X < 100 av Y(X):

${\begin aligned}V&={\begin{bmatrix}Y(0)&Y(1)&Y(2)&Y(3)&Y(4)&Y(5)&\cdots &Y(99)\end{bmatrix}}\\& ={\begin{bmatrix}29&278&529&782&1037&1294&\cdots &34382\end{bmatrix}}\end{aligned}}$

Nästa steg är att utföra silen. För varje p i vår faktorbas $\lbrace 2,17,23,29\rbrace$ lös ekvationen

$Y(X)\equiv (X+\lceil {\sqrt {N}}\rceil )^{2}-N\ ekv. 0{\pmod {p}}$

för att hitta de poster i matrisen V som är delbara med p .

För $p=2$ lös $(X+124)^{2}-15347\equiv 0{\pmod {2}}$ för att få lösningen $X\equiv {\sqrt {15347}}-124\equiv 1{\pmod {2}}$ .

Alltså, med start vid X=1 och ökande med 2, kommer varje post att vara delbart med 2. Att dividera var och en av dessa poster med 2 ger

$V={\begin{bmatrix}29&139&529&391&1037&647&\cdots &17191\end{bmatrix}}$

På liknande sätt för de återstående primtal p i $\lbrace 17,23,29\rbrace$ ekvationen $X\equiv {\sqrt {\sqrt {15347} }-124{\pmod {p}}$ är löst. Observera att för varje p > 2 kommer det att finnas 2 resulterande linjära ekvationer på grund av att det finns 2 modulära kvadratrötter.

${\begin{aligned}X&\equiv {\sqrt {15347 15347 15347 e-15347 e \equiv 3{\pmod {17}}\\&&\equiv 9-124&\equiv 4{\pmod {17}}\\X&\equiv {\sqrt {15347}}-124&\equiv 11-124&\equiv 2 {\pmod {23}}\\&&\equiv 12-124&\equiv 3{\pmod {23}}\\X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 0{\pmod {29}}\\&&\equiv 21-124&\equiv 13{\pmod {29}}\\\end{aligned}}$

Varje ekvation $X\equiv a{\pmod {p}}$ resulterar i att $V_{x}$ är delbart med p vid x = a och varje p: te värde bortom den där. Genom att dividera V med p vid a , a + p , a +2 p , a +3 p , etc. för varje primtal i basen hittar man de jämna talen som är produkter av unika primtal (första potenser).

$V={\begin{bmatrix}1&139&23&1&61&647&\cdots &17191\end{bmatrix}}$

Varje inmatning av V som är lika med 1 motsvarar ett jämnt tal. Eftersom $V_{0}$ , $V_{3}$ och $V_{71}$ är lika med en, motsvarar detta:

X + 124	Y	faktorer
124	29	000 2 • 17 • 23 • 29 1
127	782	2 1 • 17 1 • 23 1 • 29 0
195	22678	2 1 • 17 1 • 23 1 • 29 1

Matrisbearbetning

Eftersom jämna tal Y har hittats med egenskapen ${\displaystyle Y\equiv Z^{2}{\pmod {N}}} ,$ följer resten av algoritmen ekvivalent med vilken annan variant av Dixons faktoriseringsmetod .

Skriva exponenterna för produkten av en delmängd av ekvationerna

$1 ⋅$

som en matris ${\displaystyle {\pmod {2}}} :$ ger

$\displaystyle S\cdot {\begin{bmatrix}0&0&0&1\\1&1&1&0\\1&1&1&1\end{bmatrix}}\equiv {\begin{ bmatrix}0&0&0&0\end{bmatrix}}{\pmod {2}}}$

En lösning på ekvationen ges av det vänstra nollutrymmet , helt enkelt

$S={\begin{bmatrix}1&1&1\end{bmatrix}}$

Produkten av alla tre ekvationerna ger alltså en kvadrat (mod N).

$29\cdot 782\cdot 22678=22678^{2}$

och

$124^{2}\cdot 127^{2}\cdot 195^{2}=3070860^{2}$

Så hittade algoritmen

$22678^{2}\equiv 3070860^{2}{\pmod {15347}}$

Testning av resultatet ger GCD(3070860 - 22678, 15347) = 103, en icke-trivial faktor på 15347, den andra är 149.

Denna demonstration bör också tjäna till att visa att den kvadratiska sikten endast är lämplig när n är stort. För ett antal så litet som 15347 är denna algoritm överdriven. Trial division eller Pollard rho kunde ha hittat en faktor med mycket mindre beräkning.

Flera polynom

används många olika polynom för y , eftersom endast ett polynom vanligtvis inte ger tillräckligt många ( x , y ) par som är jämna över faktorbasen. Polynomen som används måste ha en speciell form, eftersom de måste vara kvadrater modulo n . Polynomen måste alla ha en liknande form som originalet y ( x ) = x ² − n :

$y(x)=(Ax+B)^{2}-n\qquad A,B\in \mathbb {Z}$

Om vi ​​antar att $B^{2}-n$ är en multipel av A, så att $B^{2}-n=AC$ polynomet y(x) kan skrivas som $y(x)=A\cdot (Ax^{2}+2Bx+C)$ . Om A är en kvadrat måste bara faktorn $(Ax^{2}+2Bx+C)$ beaktas.

Detta tillvägagångssätt (kallat MPQS, Multiple Polynomial Quadratic Sieve) är idealiskt lämpat för parallellisering , eftersom varje processor som är involverad i faktoriseringen kan ges n , faktorbasen och en samling polynom, och den behöver inte kommunicera med den centrala processorn tills den är klar med sina polynom.

Stora primtal

En stor prime

Om, efter att ha dividerat med alla faktorer mindre än A , den återstående delen av talet (kofaktorn) är mindre än A ² , måste denna kofaktor vara primtal. I själva verket kan den läggas till faktorbasen genom att sortera listan med relationer i ordning efter kofaktor. Om y(a) = 7*11*23*137 och y(b) = 3*5*7*137, då är y(a)y(b) = 3*5*11*23 * 7 2 ^* 137 ² . Detta fungerar genom att minska tröskeln för ingångar i siktningsuppsättningen över vilken en fullständig faktorisering utförs.

Fler stora primtal

Att sänka tröskeln ytterligare och använda en effektiv process för att faktorisera y(x)-värden till produkter av även relativt stora primtal - ECM är utmärkt för detta - kan hitta relationer med de flesta av deras faktorer i faktorbasen, men med två eller t.o.m. tre större primtal. Cykelfynd tillåter sedan att kombinera en uppsättning relationer som delar flera primtal till en enda relation.

Parametrar från realistiskt exempel

För att illustrera typiska parameterval för ett realistiskt exempel på en verklig implementering inklusive multipla polynom och stora primtalsoptimeringar, kördes verktyget msieve på en 267-bitars semiprime , vilket producerade följande parametrar:

• Trial factoring cutoff: 27 bitar
• Siktintervall (per polynom): 393216 (12 block av storlek 32768)
• Jämnhet bunden: 1300967 (50294 primtal)
• Antal faktorer för polynom A- koefficienter: 10 (se Flera polynom ovan)
• Stor primtalsgräns: 128795733 (26 bitar) (se Stora primtal ovan)
• Hittade jämna värden: 25952 genom att sikta direkt, 24462 genom att kombinera tal med stora primtal
• Slutlig matrisstorlek: 50294 × 50414, reducerad genom filtrering till 35750 × 35862
• Icke-triviala beroenden hittades: 15
• Total tid (på en 1,6 GHz UltraSPARC III): 35 min 39 sekunder
• Maximalt minne som används: 8 MB

Factoring-rekord

Fram till upptäckten av nummerfältssikten ( NFS) var QS den asymptotiskt snabbaste kända factoringalgoritmen för allmänna ändamål. Nu Lenstra elliptisk kurvfaktorisering samma asymptotiska körtid som QS (i det fall där n har exakt två primfaktorer av samma storlek), men i praktiken är QS snabbare eftersom den använder enkelprecisionsoperationer istället för multiprecisionen operationer som används av den elliptiska kurvmetoden.

slutfördes faktoriseringen av RSA-129 med QS. Det var ett 129-siffrigt tal, produkten av två stora primtal, en av 64 siffror och den andra av 65. Faktorbasen för denna faktorisering innehöll 524339 primtal. Datainsamlingsfasen tog 5000 MIPS-år, utförd på distribuerat sätt över Internet. Data som samlades in uppgick till 2 GB . Databearbetningsfasen tog 45 timmar på Bellcores (nu Telcordia Technologies ) MasPar (massivt parallella) superdator. Detta var den största publicerade faktoriseringen av en allmän algoritm, tills NFS användes för att faktorisera RSA-130 , slutförd 10 april 1996. Alla RSA-tal som faktoriserats sedan dess har faktoriserats med hjälp av NFS.

Det aktuella QS-faktoriseringsrekordet är den 140-siffriga (463 bitar) RSA-140, som faktoriserades av Patrick Konsor i juni 2020 med cirka 6 000 kärntimmar under 6 dagar.

Genomföranden

• PPMPQS och PPSIQS
• mpqs
• SIMPQS är en snabb implementering av den självinitierande multipla polynomkvadratsikten skriven av William Hart. Den ger stöd för den stora prime-varianten och använder Jason Papadopoulos block Lanczos-kod för det linjära algebrastadiet. SIMPQS är tillgängligt som kommandot qsieve i SageMath datoralgebrapaketet eller kan laddas ner i källform. SIMPQS är optimerat för användning på Athlon- och Opteron-maskiner, men kommer att fungera på de flesta vanliga 32- och 64-bitarsarkitekturer. Det är skrivet helt i C.
• en factoring-applet av Dario Alpern, som använder den kvadratiska sikten om vissa villkor är uppfyllda.
• PARI /GP- datoralgebrapaketet inkluderar en implementering av den självinitierande multipla polynomkvadratsikten som implementerar den stora primtalsvarianten. Den anpassades av Thomas Papanikolaou och Xavier Roblot från en sikt skriven för LiDIA-projektet. Självinitieringsschemat är baserat på en idé från Thomas Sosnowskis avhandling.
• En variant av kvadratsikten finns i MAGMA datoralgebrapaketet. Den är baserad på en implementering av Arjen Lenstra från 1995, använd i hans "factoring per email"-program.
• msieve , en implementering av den kvadratiska sikten med flera polynomer med stöd för enkla och dubbla stora primtal, skriven av Jason Papadopoulos. Källkod och en Windows-binär finns tillgängliga.
• YAFU , skriven av Ben Buhrow, är förmodligen den snabbaste tillgängliga implementeringen av den kvadratiska sikten. Till exempel räknades RSA-100 in på mindre än 15 minuter på 4 kärnor av en 2,5 GHz Xeon 6248 CPU. Alla de kritiska subrutinerna använder sig av AVX2- eller AVX-512 SIMD -instruktioner för AMD- eller Intel-processorer. Den använder Jason Papadopoulos block Lanczos-kod. Källkod och binärer för Windows och Linux är tillgängliga.
• Ariel , en enkel Java-implementering av den kvadratiska sikten för didaktiska ändamål.
• Java -math-biblioteket innehåller förmodligen den snabbaste kvadratiska sikten skriven i Java (efterföljaren till PSIQS 4.0).
• Java QS , ett Java-projekt med öppen källkod som innehåller grundläggande implementering av QS. Släppt den 4 februari 2016 av Ilya Gazman
• C Quadratic Sieve , en factorizer skriven helt i C som innehåller implementering av självinitialiserande Quadratic Sieve. Projektet är inspirerat av en William Hart's FLINT factorizer. Källan som släpptes 2022 av Michel Leonard förlitar sig inte på externt bibliotek, den kan faktorisera 240-bitars nummer på en minut och 300-bitars nummer på 2 timmar.
• RcppBigIntAlgos -paketet av Joseph Wood tillhandahåller en effektiv implementering av den kvadratiska sikten med flera polynomer för programmeringsspråket R. Det är skrivet i C++ och kan bekvämt faktorisera 100-siffriga semiprimtal . Till exempel räknades RSA-100 in under 16 timmar på en 2,8 GHz Quad-Core Intel Core i7 persondator.

Se även

• Lenstra elliptisk kurvfaktorisering
• primalitetstest

•   Richard Crandall och Carl Pomerance (2001). Prime Numbers: A Computational Perspective (1:a upplagan). Springer. ISBN 0-387-94777-9 . Avsnitt 6.1: Den kvadratiska siktfaktoriseringsmetoden, s. 227–244.

•   Samuel S. Wagstaff, Jr. (2013). Glädjen med att faktorisera . Providence, RI: American Mathematical Society . s. 195–202. ISBN 978-1-4704-1048-3 .

Andra externa länkar

• Referensartikel "The Quadratic Sieve Factoring Algorithm" av Eric Landquist