Kvadratsiktsmetod

Quadratic sieve-algoritm ( förkortning QS) är en faktoriseringsmetod för stort antal som utvecklades av Pomeranz 1981. Under lång tid överträffade den andra faktoriseringsmetoder för heltal av allmän form som inte har primtalare, vars ordning är mycket mindre (för tal som har primtalare mycket mindre är faktoriseringsmetoden på elliptiska kurvor snabbare ). Den kvadratiska siktmetoden är en variant av faktorbasmetoden (en generalisering av Fermats faktoriseringsmetod ). Denna metod anses vara den näst snabbaste (efter den allmänna sifferfältsmetoden ). ${\sqrt {n}}$ $n$ ${\sqrt {n}}$ ). Och hittills är det snabbast för heltal upp till 100 decimalsiffror och är mycket enklare än den allmänna talfältssiktmetoden . Detta är en universell faktoriseringsalgoritm, eftersom dess utförandetid enbart beror på storleken på det faktoriserade numret och inte på dess speciella struktur och egenskaper. [ett]

Huvudmål

Algoritmen försöker hitta sådana kvadrater av tal som är lika i modul (faktoriserbart tal), vilket ofta leder till faktorisering . Algoritmen fungerar i två steg: datainsamlingsstadiet, där den samlar in information som kan leda till jämlikhet mellan kvadrater; och ett databearbetningssteg, där den lägger all insamlad information i en matris och bearbetar den för att erhålla en jämlikhet av kvadrater. Det första steget kan lätt parallelliseras över många processer, men det andra steget kräver stora mängder minne och är svårt att parallellisera. $n$ $n$

En enkel metod för att hitta lika kvadrater är att välja ett slumpmässigt tal, kvadrera det och hoppas att resten efter att ha dividerat med är kvadraten på något annat tal. Till exempel . Denna metod hittar lika stora kvadrater endast i sällsynta fall för stora , men om den hittar dessa siffror kan vi anta att faktoriseringen är fullständig. Denna metod liknar Fermats faktoriseringsmetod . $n$ $80^{2}{\pmod {5959}}=441=21^{2}$ $n$

Den kvadratiska siktmetoden är en modifiering av Dixons faktoriseringsmetod .

Beräkningslängd för en kvadratisk sikt ( - faktoriserbart antal): $n$

$O(exp((1+o(1)){\sqrt {\log n\log \log n))))$ . [2]

Tillvägagångssätt

Låt x mod y vara resten av x dividerat med y. I Fermat-faktoriseringsmetoden väljer vi individuellt talet a så att en 2 mod n är en kvadrat. Men den siffran är svår att få fram. I en kvadratisk sikt beräknar vi en 2 mod n för vissa a , och hittar sedan en delmängd vars produkt är en kvadrat. Detta kommer att jämföra kvadraterna.

Till exempel, 41 2 mod 1649 = 32, 42 2 mod 1649 = 115 och 43 2 mod 1649 = 200. Inget av resultaten är en kvadrat, utan resultatet av produkten (32)(200) = 6400 = 80 2 . Å andra sidan, med tanke på den tidigare produkten mod 1649, får vi att (32)(200) = (41 2 )(43 2 ) = ((41)(43)) 2 . Eftersom (41)∙(43) mod 1649 = 114 har vi en kvadratjämförelse: 114 2 ≡ 80 2 (mod 1649).

Men hur löser vi problemet genom att fixa en uppsättning tal och hitta en delmängd, produkten av elementen, varav en kvadrat är? Låt oss börja med begreppet en vektor av exponenter. Till exempel har vi talet 504. Dess nedbrytning i primtalsfaktorer är som följer 504 = 2 3 3 2 5 0 7 1 . Vi skulle kunna representera denna expansion som en vektor av exponenter (3,2,0,1) som fångar potenserna av primtal 2, 3, 5 och 7 som är involverade i expansionen. Siffran 490, analogt, skulle ha en vektor (1,0,1,2). Multiplikation av tal är detsamma som elementvis addition av deras exponentvektorer, det vill säga produkten 504 ∙ 490 har vektorn (4,2,1,3).

Lägg nu märke till att ett tal är en kvadrat om varje element i dess exponentvektor är jämnt . Till exempel, när vi adderar vektorerna (3,0,0,1) och (1,2,0,1) får vi (4,2,0,2). Detta säger oss att produkten av talen 56 ∙ 126 är en kvadrat. Faktum är att vi inte bryr oss om de exakta värdena vi får i vektorn, så länge som varje element i den resulterande vektorn är jämnt. Av denna anledning tar vi varje element mod 2 och lägger till elementen mod 2: (1,0,0,1) + (1,0,0,1) = (0,0,0,0).

Vårt problem har alltså tagit följande form: givet en uppsättning vektorer (0,1), hitta en delmängd som kompletteras med en nollvektor med hjälp av mod 2-addition. Detta är ett linjärt algebraproblem, det vill säga det är nödvändigt att hitta linjärt beroende vektorer. Det följer av den linjära algebrasatsen att så länge antalet vektorer är större än antalet element i varje vektor måste ett sådant beroende existera. Vi kan effektivt hitta linjärt beroende vektorer, till exempel genom att placera de ursprungliga vektorerna som kolumner i en matris och sedan använda Gauss-metoden , som lätt kan anpassas för att arbeta med heltal mod 2. När vi väl har hittat linjärt beroende vektorer multiplicerar vi helt enkelt siffror, motsvarande dessa vektorer och få kvadraten vi letar efter.

Men att kvadrera en uppsättning slumptal mod n resulterar i ett stort antal distinkta primtalsfaktorer, långa vektorer och en stor matris. För att bli av med detta problem letar vi specifikt efter tal så att en 2 mod n bara har små primtalsfaktorer (sådana tal kallas jämna tal ). De är svårare att hitta, men med hjälp av sådana tal undviks stora vektorer och matriser.

Huvudidén med metoden

Som faktorbas tar vi uppsättningen av primtal som består av och alla sådana udda primtal som inte överskrider en given gräns (som väljs utifrån optimalitetsöverväganden), vilket är en kvadratisk rest modulo . $B$ $p=2$ $sid$ $P$ $n$ $sid$

Uppsättningen heltal som -tal söks i ( -tal är ett heltal som endast är delbart med primtal från ) ser ut så här: $S$ $B$ $B$ $B$

$S=\left\{t^{2}-n|[{\sqrt {n}}]+1\leq t\leq [{\sqrt {n}}]+A\right\}$

Vidare, istället för att ta en efter en och dividera den med primtal från , tas var och en en efter en och delbarheten med (och dess makter) kontrolleras samtidigt för alla . Du kan använda sikten från Eratosthenes för att skapa en lista över alla primtal som inte överstiger . $s\in S$ $B$ $p\in B$ $sid$ $s\in S$ $sid$ $A$

Algoritm

1. Gränser och storleksordningar väljs (nedan kallade ) så att . $P$ $A$ $e^{\sqrt {\log {n}\log {\log {n))))$ $L(n)$ $P<A<P^{2}$

2. För , ,... skrivs heltal i ordning i kolumnen . $t=[{\sqrt {n}}]+1$ $\left[{\sqrt {n}}\right]+2$ $\left[{\sqrt {n}}\right]+A$ $t^{2}-n$

3. För varje udda primtal beräknas Legendre-symbolen - villkoret kontrolleras . Om den inte uppfylls tas den bort från faktorbasen. $p\leq P$ $\left({n \over p}\right)=1$ $sid$

4. Om vi antar att det är ett så udda primtal som är en kvadratisk rest modulo , löses ekvationen för 1,2,.... Värdena tas i stigande ordning tills det visar sig att ekvationen inte har några lösningar som är jämförbara i modul med något av talen i regionen . $sid$ $n$ $sid$ ${\displaystyle t^{2}\equiv n{\pmod {p^{\beta ))))$ $\beta =$ $\beta$ $t$ ${\displaystyle p^{\beta ))$ $\left[{\sqrt {n}}\right]+1\leq t\leq \left[{\sqrt {n}}\right]+A$

Låt vara den största av sådana siffror för vilka det finns ett nummer med egenskapen . $\beta$ $t$ ${\displaystyle t^{2}\equiv n{\pmod {p^{\beta ))))$

Låt och lösningar och . $t_{1}$ $t_{2}$ ${\displaystyle t^{2}\equiv n{\pmod {p^{\beta ))))$ ${\displaystyle t_{2}\equiv -t_{1}{\pmod {p^{\beta ))))$

5. Med samma värde visas listan över värden som erhölls i steg 2. I kolumnen som motsvarar , sätt 1 mot alla värden som skiljer sig från från med någon multipel av . Därefter ersätts 1 med 2 för alla sådana värden som skiljer sig från med en multipel , och så vidare tills . Då görs samma sak med istället för . Det största möjliga antalet i en kolumn är . $sid$ $t^{2}-n$ $sid$ $t^{2}-n$ $t$ $t_{1}$ $sid$ $t^{2}-n$ $t$ $t_{1}$ $p^{2}$ $\beta$ $t_{2}$ $t_{1}$ $\beta$

6. När du lägger till ytterligare en enhet till numret i kolumnen i steg 5 delas motsvarande nummer med och resultatet sparas. $t^{2}-n$ $sid$

7. I kolumnen under at, sätt helt enkelt 1 mot med udda och motsvarande divideras med 2. När ekvationen är löst och lösningen fortsätter i samma veva som med udda . $p=2$ $n\neq 1{\pmod {8}}$ $t^{2}-n$ $t$ $t^{2}-n$ $n\equiv 1{\pmod {8}}$ ${\displaystyle t^{2}=n{\pmod {2^{\beta ))))$ $sid$

8. När alla angivna åtgärder utförs för alla primtal som inte överstiger , bör alla tal kasseras utom de som förvandlas till 1 efter att ha dividerat med alla potenser som inte överstiger . Som ett resultat får vi en tabell där kolumnen kommer att innehålla alla sådana värden från intervallet , som är ett -tal, och de återstående kolumnerna kommer att motsvara de värden för vilka - en kvadratisk rest. $P$ $t^{2}-n$ $sid$ $P$ $bi}$ $t$ $\left[{\left[{\sqrt {n}}\right]+1,\left[{\sqrt {n}}\right]+A}\höger]$ $t^{2}-n$ $B$ $p\leq P$ $n$

9. Därefter används den generaliserade Fermat-faktoriseringsmetoden (faktorbasmetoden ).

Hur den kvadratiska siktmetoden optimerar sökningen efter lika kvadrater

Den kvadratiska siktmetoden 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 2 ≡ y 2 (mod n ). Han väljer en uppsättning primtal som kallas faktorbasen och försöker hitta x så att den minsta återstoden y(x) = x 2 mod n faktoriserar faktorbasen. Sådana y sägs vara jämna med avseende på faktorbasen.

Att faktorisera värdet av y(x) över faktorbasen tillsammans med värdet av x kallas beroende . Kvadratsilen påskyndar processen att hitta beroenden genom att välja x nära kvadratroten ur n . Detta garanterar att talet y(x) blir mindre och därför mer sannolikt att det blir jämnt .

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

Ett annat sätt att öka sannolikheten för att vara ett jämnt tal är att öka storleken på faktorbasen. Men det är då nödvändigt att hitta åtminstone en mer jämn koppling än antalet primtal i basen för att säkerställa att ett linjärt samband existerar.

Exempel

Detta exempel visar en kvadratisk standardsikt utan logaritmiska optimeringar. Anta att vi måste faktorisera talet N = 15347, därför är det minsta talet vars kvadrat är större än N 124. Så y ( x ) = ( x + 124) 2 − 15347.

Datainsamling

Eftersom N är litet behövs bara 4 primtal. De första 4 primtalen p för vilka 15347 har en kvadratrot modulo p är 2, 17, 23 och 29 (med andra ord är 15347 den kvadratiska resten för dessa primtal). Dessa siffror kommer att ligga till grund för den kvadratiska sållen.

Vi bygger nu vår sikt från och börjar med att sikta processen för varje primtal i basen, och väljer att sikta den första Y(X) 0 ≤ X < 100 : $V_{X}$ $Y(X)=(X+\lceil {\sqrt {N))\rceil )^{2}-N=(X+124)^{2}-15347$

{\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 siktningen . För varje p i vår faktorbas löser vi ekvationen $\lbrace 2,17,23,29\rbrace$

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

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

För vi bestämmer oss för att få en lösning . $p=2$ $(X+124)^{2}-15347\equiv 0{\pmod {2))$ $X\equiv {\sqrt {15347}}-124\equiv 1{\pmod {2}}$

Så med utgångspunkt från X=1 med steget 2 kommer varje post att vara delbart med 2. Att dividera var och en av posterna 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 , löses likheten . Observera att för varje p > 2 kommer det att finnas 2 resulterande linjära ekvationer, på grund av närvaron av 2 kvadratrötter modulo. $\lbrace 17,23,29\rbrace$ $X\equiv {\sqrt {15347}}-124{\pmod {p}}$

{\begin{aligned}X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\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 likhet resulterar i att vara delbar med p när x = a , a + p , a +2 p , etc. Dividera V med p i a , a + p , a +2 p , a +3 p , etc., för varje primtal i grunden finner vi jämna tal . $X\equiv a{\pmod {p}}$ $V_{x}$

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

Ett element från V som är lika med 1 motsvarar ett jämnt tal. Eftersom , , och är lindade med 1, då: $V_{0}$ $V_{3}$ $V_{71}$

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

Matrisbearbetning

Tänk på jämlikheterna:

{\begin{aligned}29&=2^{0}\cdot 17^{0}\cdot 23^{0}\cdot 29^{1}\\782&=2^{1}\cdot 17^ {1}\cdot 23^{1}\cdot 29^{0}\\22678&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{1}\\\ end{aligned}}

och skriv ut indikatorerna för primtal i form av en matris och lös systemet : ${\pmod {2}}$

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}}

Hennes lösning:

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

Alltså är produkten av alla tre ekvationerna en kvadrat (mod N).

{\displaystyle 29\cdot 782\cdot 22678=22678^{2))

och

{\displaystyle 124^{2}\cdot 127^{2}\cdot 195^{2}=3070860^{2))

algoritmen hittar

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

Nu beräknar vi GCD(3070860 - 22678, 15347) = 103, den icke-triviala divisorn är 15347, den andra är 149.

Faktoriseringsrekord

Innan upptäckten av NFS ( general number field sieve) var QS känd som den snabbaste faktoriseringsalgoritmen för allmänna ändamål. För närvarande har den elliptiska kurvan faktoriseringsalgoritmen samma gångtid som QS (i fallet när n är produkten av endast två primtal), men i praktiken är QS snabbare, eftersom den använder enstaka precisionsoperationer istället för de långa aritmetiska operationerna som används i den elliptiska kurvmetoden.

Den 2 april 1994 faktoriserades RSA -129 med QS-metoden. Det var ett antal av längden 129, resultatet av produkten av två primtal, en av längden 64 och den andra av längden 65. I detta fall bestod faktorbasen av 524339 primtal. Datainsamlingsfasen producerade 5 000 MIPS . Den insamlade informationen upptog 2 GB . Matrisbearbetningssteget tog 45 timmar hos Bellcore-ovsky (nu Telcordia Technologies) på MasPar superdator . Det var det största antalet som kunde faktoriseras av en allmän algoritm vid den tiden. Först den 10 april 1996 kunde de faktorisera ett antal längder 130 RSA med hjälp av NFS-metoden.

Litteratur

Koblitz NA Kurs i talteori och kryptografi (neopr.) . - Springer-Verlag , 1987. - S. 180-182.
Gerver JL Factoring stora tal med en kvadratisk såll . — Matematik. Comp., 1983. Vol. 41. - s. 287-294.

Anteckningar

↑ Carl Pomerance, Analysis and Comparison of Some Integer Factoring Algorithms, in Computational Methods in Number Theory, Del I, HW Lenstra, Jr. och R. Tijdeman, red., Math. Center Tract 154, Amsterdam, 1982, sid 89-139.
↑ Pomerance, Carl . A Tale of Two Sieves (december 1996), s. 1473–1485. Arkiverad 11 november 2020. Hämtad 10 december 2011.

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