Lenstra elliptisk-kurva faktorisering

Lenstra elliptiska kurvfaktorisering eller elliptisk kurvfaktoriseringsmetoden ( ECM ) är en snabb, subexponentiell körtid , algoritm för heltalsfaktorisering , som använder elliptiska kurvor . För generell factoring är ECM den tredje snabbaste kända factoringmetoden. Den näst snabbaste är den kvadratiska sikten med flera polynomer, och den snabbaste är sikten för det allmänna talfältet . Lenstras elliptiska kurvfaktorisering är uppkallad efter Hendrik Lenstra .

Praktiskt sett anses ECM vara en factoringalgoritm för speciella ändamål, eftersom den är mest lämpad för att hitta små faktorer. För närvarande är det fortfarande den bästa algoritmen för divisorer som inte överstiger 50 till 60 siffror , eftersom dess körtid domineras av storleken på den minsta faktorn p snarare än av storleken på talet n som ska faktoriseras. ECM används ofta för att ta bort små faktorer från ett mycket stort heltal med många faktorer; om det återstående heltal fortfarande är sammansatt, har det bara stora faktorer och faktoriseras med generella tekniker. Den största faktorn som hittills hittats med ECM har 83 decimalsiffror och upptäcktes den 7 september 2013 av R. Propper. Att öka antalet testade kurvor förbättrar chanserna att hitta en faktor, men det är de inte linjär med ökningen av antalet siffror.

Algoritm

Lenstras elliptiska kurvfaktoriseringsmetod för att hitta en faktor för ett givet naturligt tal $n$ fungerar enligt följande:

1. Välj en slumpmässig elliptisk kurva över $\mathbb {Z} /n\mathbb {Z}$ , med ekvationen av formen $y ^{2}=x^{3}+ax+b{\pmod {n}}$ tillsammans med en icke-trivial punkt $P(x_{0},y_{0})$ på den.

   Detta kan göras genom att först välja slumpmässigt ${\displaystyle x_{0},y_{0},a\in \mathbb {Z} /n\mathbb {Z} } ,$ och sedan inställning $b=y_{0}^{2}-x_{0}^{3}-ax_{0}{\pmod {n}}$ för att säkerställa att punkten är på kurvan.

2. Man kan definiera tillägg av två punkter på kurvan, för att definiera en grupp . Additionslagarna ges i artikeln om elliptiska kurvor .

   Vi kan bilda upprepade multiplar av en punkt $P$ : $[k]P=P+\ldots +P{\text{ (k gånger) }}$ . Adderingsformlerna innebär att man tar den modulära lutningen för ett ackord som sammanfogar $P$ och $Q$ , och därmed uppdelningen mellan restklasser modulo $n$ , utförd med den utökade euklidiska algoritmen . I synnerhet inkluderar division med vissa $v{\bmod {n}}$ beräkning av $\gcd(v,n)$ .

   Om vi ​​antar att vi beräknar en lutning av formen $u/v$ med $\gcd(u,v)=1$ , då om $v=0{\bmod {n}}$ blir resultatet av punktadditionen $\infty$ , punkten "i oändlighet" som motsvarar skärningspunkten för den "vertikala" linjen som förenar $P(x,y),P'(x,-y)$ och kurvan. Men om ${\displaystyle \gcd(v,n)\neq 1,n} ,$ kommer punktadditionen inte att ge en meningsfull punkt på kurvan; men, ännu viktigare, $\gcd(v,n)$ är en icke-trivial faktor av $n$ .

3. Beräkna $[k]P$ på den elliptiska kurvan ( ${\bmod {n}}$ ), där $k$ är en produkt av många små tal: säg, en produkt av små primtal upphöjda till små potenser, som i p-1-algoritmen , eller faktorial $B!$ för vissa inte för stora $B$ . Detta kan göras effektivt, en liten faktor i taget. Säg, för att få $[B!]P$ , beräkna först $[2]P$ , sedan $[3]([2]P)$ , sedan $[4]([3!]P)$ och så vidare. $B$ väljs för att vara tillräckligt liten så att $B$ -vis punkttillägg kan utföras inom rimlig tid.
   • Om vi ​​avslutar alla beräkningar ovan utan att stöta på icke-inverterbara element ( ${\bmod {n}}$ ), betyder det att de elliptiska kurvornas (moduloprimtal) ordning inte är tillräckligt jämn , så vi måste försök igen med en annan kurva och utgångspunkt.
   • Om vi ​​stöter på en $\gcd(v,n)\neq 1,n$ är vi klara: det är en icke-trivial faktor av $n$ .

Tidskomplexiteten beror på storleken på talets minsta primtal och kan representeras av exp[( √ 2 + o (1)) √ ln p ln ln p ] , där p är den minsta faktorn av n , eller ${\displaystyle L_{p}\left[{\frac {1}{2}},{\sqrt {2}}\right]} ,$ i L-notation .

Varför fungerar algoritmen?

Om p och q är två primtalsdelare av n , så innebär y ² = x ³ + ax + b (mod n ) samma ekvation även modulo p och modulo q . Dessa två mindre elliptiska kurvor med $\boxplus$ -tillägget är nu äkta grupper . Om dessa grupper har N _p och N _q element, respektive, för varje punkt P på den ursprungliga kurvan, enligt Lagranges sats , är k > 0 minimal så att $kP=\infty$ på kurvan modulo p innebär att k delar N _p ; dessutom, $N_{p}P=\infty$ . Det analoga påståendet gäller för kurvan modulo q . När den elliptiska kurvan väljs slumpmässigt N _p och N _q slumptal nära p + 1 respektive q + 1 (se nedan). Därför är det osannolikt att de flesta av primfaktorerna för N _p och N _q är desamma, och det är ganska troligt att när vi beräknar eP , kommer vi att stöta på någon kP som är ∞ modulo p men inte modulo q , eller tvärtom. När så är fallet existerar inte kP på den ursprungliga kurvan, och i beräkningarna hittade vi något v med antingen gcd( v , p ) = p eller gcd( v , q ) = q , men inte båda. Det vill säga, gcd( v , n ) gav en icke-trivial faktor på n .

ECM är i sin kärna en förbättring av den äldre p -1- algoritmen . p − är 1 -algoritmen hittar primtalsfaktorer p så att p − 1 b-potensjämn för små värden på b . För varje e , en multipel av p − 1, och vilken som helst ett relativt primtal till p , enligt Fermats lilla sats har vi en ^e ≡ 1 ( mod p ) . Då gcd ( a ^e − 1, n ) producerar en faktor på n . Algoritmen misslyckas dock när p -1 har stora primtalsfaktorer, som till exempel är fallet för tal som innehåller starka primtal .

ECM kommer runt detta hinder genom att betrakta gruppen av en slumpmässig elliptisk kurva över det finita fältet Z _p , snarare än att beakta den multiplikativa gruppen av Z _p som alltid har ordningen p − 1.

Ordningen för gruppen av en elliptisk kurva över Z _p varierar (ganska slumpmässigt) mellan p + 1 − 2 √ p och p + 1 + 2 √ p enligt Hasses sats , och är sannolikt jämn för vissa elliptiska kurvor. Även om det inte finns några bevis för att en jämn gruppordning kommer att hittas i Hasse-intervallet, genom att använda heuristiska probabilistiska metoder, Canfield–Erdős–Pomerance-satsen med lämpligt optimerade parameterval och L-notationen , kan vi förvänta oss att prova L [ √ 2 /2, √ 2 ] kurvor innan du får en jämn gruppordning. Denna heuristiska uppskattning är mycket tillförlitlig i praktiken.

Ett exempel

Följande exempel är från Trappe & Washington (2006), med några detaljer tillagda.

Vi vill faktorisera n = 455839. Låt oss välja den elliptiska kurvan y ² = x ³ + 5 x – 5, med punkten P = (1, 1) på den, och låt oss försöka beräkna (10!) P .

Tangentlinjens lutning vid någon punkt A =( x , y ) är s = (3 x ² + 5)/(2 y ) (mod n) . Med s kan vi beräkna 2 A . Om värdet på s är av formen a/b där b > 1 och gcd( a , b ) = 1, måste vi hitta den modulära inversen av b . Om det inte finns, gcd( n , b ) är en icke-trivial faktor av n .

Först beräknar vi 2 P . Vi har s ( P ) = s (1,1) = 4, så koordinaterna för 2 P = ( x′ , y′ ) är x′ = s ² – 2 x = 14 och y′ = s ( x – x ′ ) – y = 4(1 – 14) – 1 = –53, alla tal förstått (mod n ). Bara för att kontrollera att denna 2 P verkligen är på kurvan: (–53) ² = 2809 = 14 ³ + 5·14 – 5.

Sedan beräknar vi 3(2 P ). Vi har s (2 P ) = s (14,-53) = –593/106 (mod n ). Med den euklidiska algoritmen : 455839 = 4300·106 + 39, sedan 106 = 2·39 + 28, sedan 39 = 28 + 11, sedan 28 = 2·11 + 6, sedan 11 = 6 + 5, sedan 6 = 5 + 1. Därför gcd(455839, 106) = 1, och arbetar bakåt (en version av den utökade euklidiska algoritmen ): 1 = 6 – 5 = 2·6 – 11 = 2·28 – 5·11 = 7·28 – 5·39 = 7·106 – 19·39 = 81707·106 – 19·455839. Därav 106 ⁻¹ = 81707 (mod 455839) och –593/106 = –133317 (mod 455839). Givet denna s kan vi beräkna koordinaterna för 2(2 P ), precis som vi gjorde ovan: 4 P = (259851, 116255). Bara för att kontrollera att detta verkligen är en punkt på kurvan: y ² = 54514 = x ³ + 5 x – 5 (mod 455839). Efter detta kan vi beräkna $3(2P)=4P\boxplus 2P$ .

Vi kan på samma sätt beräkna 4! P och så vidare, men 8! P kräver invertering av 599 (mod 455839). Den euklidiska algoritmen ger att 455839 är delbart med 599, och vi har hittat en faktorisering 455839 = 599·761.

Anledningen till att detta fungerade är att kurvan (mod 599) har 640 = 2 ⁷ ·5 poäng, medan den (mod 761) har 777 = 3·7·37 poäng. Dessutom är 640 och 777 de minsta positiva heltalen k så att kP = ∞ på kurvan (mod 599) respektive (mod 761) . Sedan 8! är en multipel av 640 men inte en multipel av 777, vi har 8! P = ∞ på kurvan (mod 599), men inte på kurvan (mod 761), därför bröt den upprepade additionen ner här, vilket ger faktoriseringen.

Algoritmen med projektiva koordinater

Innan du betraktar det projektiva planet över $(\mathbb {Z} /n\mathbb {Z} )/\sim ,$ överväg först ett 'normalt' projektivt utrymme över ℝ: Istället för punkter, linjer genom origo studeras. En linje kan representeras som en punkt som inte är noll $(x,y,z)$ , under en ekvivalensrelation ~ ges av: $(x,y,z)\sim (x',y',z')$ ⇔ ∃ c ≠ 0 så att x' = c x , y' = cy . och cz z ' = Under denna ekvivalensrelation kallas rymden det projektiva planet $\mathbb {P} ^{2}$ ; poäng, betecknade med $(x:y:z)$ , motsvarar linjer i ett tredimensionellt utrymme som passerar genom origo. Observera att punkten $(0:0:0)$ inte existerar i detta utrymme eftersom för att dra en linje i alla möjliga riktningar krävs minst en av x',y' eller z' ≠ 0. Observera nu att nästan alla linjer går genom ett givet referensplan - såsom ( X , Y ,1)-planet, medan linjerna är exakt parallella med detta plan, har koordinater ( X,Y ,0), specificera riktningar unikt, som 'punkter i oändlighet' som används i det affina ( X,Y )-planet det ligger ovanför.

I algoritmen används endast gruppstrukturen för en elliptisk kurva över fältet ℝ. Eftersom vi inte nödvändigtvis behöver fältet ℝ, kommer ett ändligt fält också att ge en gruppstruktur på en elliptisk kurva. Att betrakta samma kurva och operation över $(\mathbb {Z} /n\mathbb {Z} )/\sim$ med n inte ett primtal ger dock ingen grupp. Elliptic Curve Method använder sig av felfallen i additionslagen.

Vi anger nu algoritmen i projektiva koordinater. Det neutrala elementet ges då av punkten vid oändligheten $(0:1:0)$ . Låt n vara ett (positivt) heltal och betrakta den elliptiska kurvan (en uppsättning punkter med någon struktur på den) $E(\mathbb {Z} /n\mathbb {Z} )=\{(x:y:z)\in \mathbb {P} ^{2} \ |\ y^{2}z=x^{3}+axz^{2}+bz^{3}\}$ .

1. Välj $x_{P},y_{P},a\in \mathbb {Z} /n\mathbb {Z}$ med en ≠ 0.
2. Beräkna $b=y_{P}^{2}-x_{P}^{3}-ax_{P}$ . Den elliptiska kurvan E är då i Weierstrass-form given av $y^{2}=x^{3}+ax+b$ och genom att använda projektiva koordinater ges den elliptiska kurvan genom den homogena ekvationen $ZY^{2}=X^{3}+aZ^{2}X+bZ^{3}$ . Den har punkten $P=(x_{P}:y_{P}:1)$ .
3. Välj en övre gräns $B\in \mathbb {Z}$ för denna elliptiska kurva. Anmärkning: Du hittar bara faktorer p om gruppordningen för den elliptiska kurvan E över $\mathbb {Z} /p\mathbb {Z}$ (betecknas med ${ \displaystyle \#E(\mathbb {Z} /p\mathbb {Z} )} )$ är B-slät , vilket betyder att alla primtalsfaktorer för $\#E(\mathbb {Z} /p\mathbb {Z} )$ måste vara mindre eller lika med B .
4. Beräkna $k={\rm {lcm}}(1,\dots ,B)$ .
5. Beräkna $kP:=P+P+\cdots +P$ ( k gånger) i ringen $E(\mathbb {Z} /n\mathbb {Z} )$ . Observera att om $\#E(\mathbb {Z} /n\mathbb {Z} )$ är B -slät och n är primtal (och därför $\mathbb {Z} /n\mathbb {Z}$ är ett fält) som $kP=(0:1:0)$ . Men om bara $\#E(\mathbb {Z} /p\mathbb {Z} )$ är B-jämn för någon divisor p av n , kanske produkten inte är ( 0:1:0) eftersom addition och multiplikation inte är väldefinierade om n är inte prime. I det här fallet kan en icke-trivial divisor hittas.
6. Om inte, gå tillbaka till steg 2. Om detta inträffar kommer du att märka detta när du förenklar produkten $kP.$

I punkt 5 sägs det att under rätt omständigheter kan en icke-trivial divisor hittas. Som påpekats i Lenstras artikel (Factoring Integers with Elliptic Curves) kräver additionen antagandet $\gcd(x_{1}-x_{2},n)=1$ . Om $P,Q$ inte är $(0:1:0)$ och distinkt (annars fungerar tillägg på liknande sätt, men är lite annorlunda), då fungerar tillägg enligt följande:

• För att beräkna: $R=P+Q;$$P=(x_{1}:y_{1}:1 ),Q=(x_{2}:y_{2}:1)$ ,
• $\lambda =(y_{1}-y_{2})(x_{1}-x_{2})^{-1 }$ ,
• $x_{3}=\lambda ^{2}-x_{1}-x_{2}$ ,
• $y_{3}=\lambda (x_{1}-x_{3})-y_{1}$ ,
• $R=P+Q=(x_{3}:y_{3}:1)$ .

Om addition misslyckas kommer detta att bero på ett misslyckande som beräknar $\lambda .$ I synnerhet eftersom $(x_{1}-x_{2})^{-1}$ inte alltid kan beräknas om n inte är primtal (och därför är $\mathbb {Z} /n\mathbb {Z}$ inte ett fält). Utan att använda $\mathbb {Z} /n\mathbb {Z}$ eftersom ett fält kan man räkna ut:

• $\lambda '=y_{1}-y_{2}$ ,
• $x_{3}'={\lambda '}^{2}-x_{ 1}(x_{1}-x_{2})^{2}-x_{2}(x_{1}-x_{2})^{2}$ ,
• $y_{3}'=\lambda '(x_{1} (x_{1}-x_{2})^{2}-x_{3}')-y_{1}(x_{1}-x_{2})^{3}$ ,
• $R=P+Q=(x_{3}'(x_{1 }-x_{2}):y_{3}':(x_{1}-x_{2})^{3})$ och förenkla om möjligt.

Denna beräkning är alltid laglig och om gcd för Z -koordinaten med n ≠ (1 eller n ), så när förenklingen misslyckas , hittas en icke-trivial divisor av n .

Vridna Edwards-kurvor

Huvudartikel: Twisted Edwards curve

Användningen av Edwards-kurvor kräver färre modulära multiplikationer och mindre tid än användningen av Montgomery-kurvor eller Weierstrass-kurvor (andra använda metoder). Med Edwards-kurvor kan du också hitta fler primtal.

Definition. Låt $k$ vara ett fält där $2\neq 0$ , och låt $a,d\in k\setminus \{0\}$ med $a\neq d$ . Sedan ges den tvinnade Edwards-kurvan $E_{E,a,d}$ av $ax^{2}+y^{2}=1+dx^{2}y^{2}.$ En Edwards-kurva är en vriden Edwards-kurva där $a=1$ .

Det finns fem kända sätt att bygga en uppsättning punkter på en Edwards-kurva: uppsättningen affinpunkter, uppsättningen projektiva punkter, uppsättningen inverterade punkter, uppsättningen förlängda punkter och uppsättningen av fullbordade punkter.

Uppsättningen affina punkter ges av:

$\{(x,y)\in \mathbb {A} ^{2}:ax^{ 2}+y^{2}=1+dx^{2}y^{2}\}$ .

Tilläggslagen ges av

$(e,f),(g,h)\mapsto \left({\frac {eh+fg}{1+degfh}},{\frac {fh-aeg}{1-degfh}}\right ).$

Punkten (0,1) är dess neutrala element och inversen av $(e,f)$ är $(-e,f)$ .

De andra representationerna definieras liknande hur den projektiva Weierstrass-kurvan följer från affinen.

Varje elliptisk kurva i Edwards-form har en ordningspunkt 4. Så torsionsgruppen för en Edwards-kurva över $\mathbb {Q}$ är isomorf till antingen $\mathbb {Z} /4\mathbb {Z} ,\mathbb {Z} /8\mathbb {Z} ,\mathbb {Z} /12\mathbb {Z} ,\mathbb {Z} /2\ mathbb {Z} \times \mathbb {Z} /4\mathbb {Z}$ eller $\mathbb {Z} /2\mathbb {Z} \times \mathbb {Z } /8\mathbb {Z}$ .

De mest intressanta fallen för ECM är $\mathbb {Z} /12\mathbb {Z}$ och ${\displaystyle \mathbb {Z} /2\mathbb { Z} \times \mathbb {Z} /8\mathbb {Z} } ,$ eftersom de tvingar gruppordningarna för kurvans moduloprimtal att vara delbara med 12 respektive 16. Följande kurvor har en torsionsgrupp som är isomorf till $\mathbb {Z} /12\mathbb {Z}$ :

• $x^{2}+y^{2}=1+dx^{2}y^{2}$ med punkt ${\ displaystil (a,b)}$ där ${\displaystyle b\notin \{-2,-1/2,0,\pm 1\},a^{2}=-(b^{2}+2b)} och$ d $d=-(2b+1)/(a^{2}b^{2})$
• $x^{2}+y^{2}=1+dx^{2}y^{2}$ med punkt ${\ displaystil (a,b)}$ där $a={\frac {u^{2}-1}{u^{2}+1}},b=-{\frac {(u-1)^{2}}{u^{2 }+1}}$ och $d={\frac {(u^{2}+1)^{3}(u^{2}-4u+1)}{(u-1)^{6}(u+1)^ {2}}},u\notin \{0,\pm 1\}.$

Varje Edwards-kurva med en ordningspunkt 3 kan skrivas på de sätt som visas ovan. Kurvor med torsionsgrupp isomorf till $\mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /8\mathbb {Z}$ och $\mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /4\mathbb {Z}$ kan vara effektivare för att hitta primtal.

Steg 2

Ovanstående text handlar om det första steget av elliptisk kurvfaktorisering. Där hoppas man hitta en primtal divisor p så att $sP$ är det neutrala elementet av $E(\mathbb {Z} /p\mathbb {Z} )$ . I det andra steget hoppas man ha hittat en primtalare q så att $sP$ har liten primtalsordning i $E(\mathbb {Z} /q\mathbb {Z} )$ .

Vi hoppas att ordningen ligger mellan $B_{1}$ och $B_{2}$ , där $B_{1}$ bestäms i steg 1 och ${\ displaystyle B_{2}}$ är ny steg 2-parameter. Kontrollera efter en liten ordning av $sP$ , kan göras genom att beräkna $(ls)P$ modulo n för varje primtal l .

GMP-ECM och EECM-MPFQ

Användningen av Twisted Edwards elliptiska kurvor, såväl som andra tekniker, användes av Bernstein et al för att ge en optimerad implementering av ECM. Dess enda nackdel är att den fungerar på mindre sammansatta tal än den mer generella implementeringen, GMP-ECM från Zimmerman.

Hyperelliptic curve method (HECM)

Det finns nya utvecklingar när det gäller att använda hyperelliptiska kurvor för att faktorisera heltal. Cosset visar i sin artikel (2010) att man kan bygga en hyperelliptisk kurva med släkte två (så en kurva $y^{2}=f(x)$ med f av grad 5) , vilket ger samma resultat som att använda två "normala" elliptiska kurvor samtidigt. Genom att använda Kummer-ytan blir beräkningen mer effektiv. Nackdelarna med den hyperelliptiska kurvan (mot en elliptisk kurva) kompenseras av detta alternativa beräkningssätt. Därför hävdar Cosset grovt att det inte är värre att använda hyperelliptiska kurvor för faktorisering än att använda elliptiska kurvor.

Quantum version (GEECM)

Bernstein , Heninger , Lou och Valenta föreslår GEECM, en kvantversion av ECM med Edwards-kurvor. Den använder Grovers algoritm för att ungefär fördubbla längden på de primtal som hittas jämfört med standard EECM, förutsatt att en kvantdator med tillräckligt många qubits och med jämförbar hastighet som den klassiska datorn som kör EECM.

Se även

• UBASIC för praktiskt program (ECMX).

•   Bernstein, Daniel J.; Birkner, Peter; Lange, Tanja; Peters, Christiane (2013). "ECM använder Edwards-kurvor" . Beräkningsmatematik . 82 (282): 1139–1179. doi : 10.1090/S0025-5718-2012-02633-0 . MR 3008853 .
•   Bosma, W.; Hulst, MPM van der (1990). Primalitet som bevisas med cyklotomi . Ph.D. Avhandling, Universiteit van Amsterdam. OCLC 256778332 .
•   Brent, Richard P. (1999). "Faktorisering av det tionde Fermat-numret" . Beräkningsmatematik . 68 (225): 429–451. Bibcode : 1999MaCom..68..429B . doi : 10.1090/S0025-5718-99-00992-8 . MR 1489968 .
•     Cohen, Henri (1993). En kurs i beräkningsalgebraisk talteori . Examentexter i matematik. Vol. 138. Berlin: Springer-Verlag. doi : 10.1007/978-3-662-02945-9 . ISBN 978-0-387-55640-6 . MR 1228206 . S2CID 118037646 .
•    Cosset, R. (2010). "Faktorisering med släkt 2-kurvor". Beräkningsmatematik . 79 (270): 1191–1208. arXiv : 0905.2325 . Bibcode : 2010MaCom..79.1191C . doi : 10.1090/S0025-5718-09-02295-9 . MR 2600562 . S2CID 914296 .
•    Lenstra, AK ; Lenstra Jr., HW, red. (1993). Utvecklingen av nummerfältssilen . Föreläsningsanteckningar i matematik. Vol. 1554. Berlin: Springer-Verlag. doi : 10.1007/BFb0091534 . ISBN 978-3-540-57013-4 . MR 1321216 .
•    Lenstra Jr., HW (1987). "Faktorering av heltal med elliptiska kurvor" (PDF) . Annals of Mathematics . 126 (3): 649–673. doi : 10.2307/1971363 . hdl : 1887/2140 . JSTOR 1971363 . MR 0916721 .
•    Pomerance, Carl ; Crandall, Richard (2005). Prime Numbers: A Computational Perspective (andra upplagan). New York: Springer. ISBN 978-0-387-25282-7 . MR 2156291 .
•    Pomerance, Carl (1985). "Den kvadratiska sållfaktoreringsalgoritmen". Framsteg inom kryptologi, Proc. Eurocrypt '84 . Föreläsningsanteckningar i datavetenskap. Vol. 209. Berlin: Springer-Verlag. s. 169–182. doi : 10.1007/3-540-39757-4_17 . ISBN 978-3-540-16076-2 . MR 0825590 .
•   Pomerance, Carl (1996). "En berättelse om två siktar" (PDF) . Meddelanden från American Mathematical Society . 43 (12): 1473–1485. MR 1416721 .
•   Silverman, Robert D. (1987). "The Multiple Polynomial Quadratic Sieve" . Beräkningsmatematik . 48 (177): 329–339. doi : 10.1090/S0025-5718-1987-0866119-8 . MR 0866119 .
•    Trappe, W.; Washington, LC (2006). Introduktion till kryptografi med kodningsteori (andra upplagan). Saddle River, NJ: Pearson Prentice Hall. ISBN 978-0-13-186239-5 . MR 2372272 .
•   Samuel S. Wagstaff, Jr. (2013). Glädjen med att faktorisera . Providence, RI: American Mathematical Society. s. 173–190. ISBN 978-1-4704-1048-3 .
• Watras, Marcin (2008). Kryptografi, talanalys och mycket stora tal . Bydgoszcz: Wojciechowski-Steinhagen. PL:5324564.

externa länkar

• Faktorisering med Elliptic Curve Method , en WebAssembly-applikation som använder ECM och växlar till den självinitialiserande kvadratiska sikten när den är snabbare.
• GMP-ECM , en effektiv implementering av ECM.
• ECMNet , en enkel klient-server-implementering som fungerar med flera faktoriseringsprojekt.
• pyecm , en pythonimplementering av ECM. Mycket snabbare med psyco och/eller gmpy.
• Distributed computing project yoyo@Home Delprojekt ECM är ett program för elliptisk kurvfaktorisering som används av ett par projekt för att hitta faktorer för olika slags tal.
• Lenstra Elliptic Curve Factorization Algoritm källkod Enkel C och GMP Elliptic Curve Factorization Algoritm källkod.
• EECM-MPFQ En implementering av ECM med hjälp av Edwards-kurvor skrivna med MPFQ finita fältbibliotek.