Factoring elliptisten käyrien kanssa

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 14. lokakuuta 2016 tarkistetusta versiosta . tarkastukset vaativat 57 muokkausta .

Faktorisointi elliptisiä käyriä käyttäen ( englanniksi elliptic curve factorization method , lyhenne ECM ) tai Lenstran menetelmä elliptisiä käyriä käyttäen ( englanniksi Lenstra elliptic curve factorization ) on algoritmi luonnollisen luvun faktorointiin elliptisten käyrien avulla . Tällä algoritmilla on subeksponentiaalinen monimutkaisuus [1] . ECM on kolmanneksi nopeimmin juokseva [2] yleisen lukukentän seulamenetelmän ja neliöllisen seulamenetelmän jälkeen .

Käytännössä se soveltuu parhaiten luvun pienten alkujakajien löytämiseen, ja siksi sitä pidetään erittäin erikoistuneena [3] algoritmina.

Se on paras algoritmi [4] 20-25 merkin pituisten alkujakajien etsimiseen (koko 64…83 bittiä), koska sen monimutkaisuus riippuu pääasiassa pienimmästä alkujakajasta p, ei tekijöihin sidotusta luvusta.

Käytetään usein tunnistamaan (hylkäämään) luvun pieniä alkulukujakajia. Jos algoritmin toiminnan jälkeen saatu luku on edelleen komposiitti, niin loput tekijät ovat suuria lukuja, ja lisälaajennuksessa on järkevää käyttää yleisempiä faktorointialgoritmeja.

Suurin tällä algoritmilla löydetty jakaja on 83 merkkiä pitkä ja Ryan Propper löysi sen 7. syyskuuta 2013 [5] .

Algoritmi

Luonnollisen luvun faktorointialgoritmi (ei-triviaalin jakajan löytäminen) [6] : $n$

Valitaan satunnainen elliptinen käyrä , jonka yhtälö on muotoa : ja ei- triviaali piste valitaan tälle käyrälle . Tämä voidaan tehdä näin: $E$ $\mathbb {Z} _{n}$ $E$ $y^{2}=x^{3}+ax+b{\pmod {n))$ $P(x_{0},y_{0})$
1. Numerot valitaan satunnaisesti . $x_{0},y_{0},a$ $\sisään$ $\mathbb {Z} _{n}$
2. Laskettu . $b=y_{0}^{2}-x_{0}^{3}-ax_{0}{\pmod {n))$
Valitaan kokonaisluku , joka on suuren määrän pienten lukujen tulo. Esimerkiksi, kuten voit valita: $e$ $e$
- Factorial joitakin pieniä lukuja . ${\näyttötyyli B!}$ $B$
- Useiden pienten alkulukujen tulo pieniin potenssiin. Toisin sanoen valitaan alkuluvut (jotka eivät ylitä tiettyä lukua ) ja asteet siten, että sopivaan potenssiin nostamisen tulos ei ylitä tiettyä lukua : $l_{i}$ $B$ ${\alpha _{i))$ $l_{i}$ $l_{i}^{\alpha _{i))$ $C$
$e=\prod _{\ell \leq B}\ell ^{\alpha _{i)),$ missä on suurin mahdollisista indikaattoreista, jossa . $\alpha _{i}=\left\lfloor \log _{\ell }C\right\rfloor$ $\ell ^{\alpha _{i}}\leq C$
Elliptisen käyrän tulo lasketaan : $eP$ $E$ ${\displaystyle eP=\underbrace {P\boxplus \dots \boxplus P} _{e))$ , missä on konsernilain määrittelemä summausoperaatio . $\box plus$ Summausoperaatio vaatii summatut pisteet yhdistävän segmentin kaltevuuden löytämisen ja vaatii siksi jakomoduulin toiminnan . Modulo-operaatio suoritetaan käyttämällä laajennettua Euclid-algoritmia . Erityisesti jakaminen jollakin luvulla v (mod n ) sisältää gcd :n ( v , n ) löytämisen . Tapauksessa gcd( v , n ) 1, gcd( v , n ) n , -lisäys ei anna mitään merkityksellistä pistettä elliptisellä käyrällä, mikä tarkoittaa, että gcd( v , n ) on n: n ei-triviaali jakaja . . Tämän perusteella seuraavat tapaukset ovat mahdollisia laskentaprosessissa: $\neq$ $\neq$ $\box plus$ $eP$
- Jos laskennan aikana ei havaittu irreversiibeliä elementtiä ( mod n ) , on valittava toinen elliptinen käyrä ja piste ja toistettava algoritmi alusta. $E$ $P(x_{0},y_{0})$
- Jos jossain vaiheessa , jossa ( ), niin sinun on valittava toinen elliptinen käyrä ja piste ja toistettava algoritmi alusta, koska piste pysyy ennallaan lisätoimintojen jälkeen. $e'P=\underbrace {P\boxplus \dots \boxplus P} _{e'}=\infty$ $e'\leq e$ $E$ $P(x_{0},y_{0})$ $\infty$
- Jos jossain laskentavaiheessa gcd( v , n ) 1 ja gcd( v , n ) n , niin gcd( v , n ) on n:n vaadittu ei-triviaali jakaja . $\neq$ $\neq$

Perustelut

Yhtälö , joka on otettu modulo luvun n mukaan, määrittää elliptisen käyrän . Jos luvut p ja q ovat kaksi luvun n alkujakajaa , niin yllä oleva yhtälö on myös totta, kun ne otetaan modulo p tai modulo q . Eli : ja : määrittelevät vastaavasti kaksi elliptistä käyrää (pienempi kuin ). Jopa tietyllä summausoperaatiolla , eivät kuitenkaan ole vain elliptisiä käyriä: ne ovat myös ryhmiä . Olkoon ne sisältävät N p ja N q elementtiä, vastaavasti, jos: $y^{2}=x^{3}+ax+b$ $E$ $E_1$ $y^{2}=x^{3}+ax+b{\pmod {p}}$ $E_2$ $y^{2}=x^{3}+ax+b{\pmod {q))$ $E$ $E_1$ $E_2$ $\box plus$

$P$ - mikä tahansa alkuperäisen käyrän piste
$k_i$ ovat positiivisia lukuja, kuten: $k_{i}P=\infty$ $E_1$
$k$ on minimi $k_i$

Sitten Lagrangen lauseen mukaan se on totta

$k$ -jakaja $N_p$
$N_{p}P=\infty$

Samanlainen väite pätee myös käyrälle modulo q .

Elliptisellä käyrällä Z p :n yläpuolella olevan pisteryhmän järjestystä rajoittaa Hassen lause : p + 1 − 2 √ p p + 1 + 2 √ p $|E|$ $\leq |E|\leq$

Satunnaisesti valitulle elliptiselle käyrälle luvut N p ja N q ovat satunnaislukuja, joita rajoittaa Hassen lause (katso alla). On epätodennäköistä, että suurin osa N p :n ja N q :n alkujakajista ovat samat, ja on todennäköistä, että kun eP lasketaan, kohdataan jokin modulo p mutta ei mod q tai päinvastoin. Jos näin on, niin kP :tä ei ole alkuperäisellä käyrällä, ja laskelmissa löydettiin v niin, että joko gcd( v , p ) = p tai gcd( v , q ) = q , mutta ei molempia. Tällöin gcd( v , n ) on n:n ei-triviaali jakaja . $kP=\infty$

ECM on jalostus Pollardin vanhemmasta P-1-menetelmästä [7] . Algoritmi p − 1 löytää p :n alkujakajia siten, että ( p − 1) on B-tasainen jollekin pienelle B :lle . Jokaiselle e :lle, joka on ( p − 1) : n kerrannainen , ja mille tahansa a :lle , joka on suhteellisesti alkuluku p : hen , Fermatin lause pätee, että a e ≡ 1 (mod p ) . Silloin gcd ( a e − 1, n ) on n: n jakaja suurella todennäköisyydellä . Algoritmi p − 1 kuitenkin epäonnistuu [7] , kun p :llä on suuret alkujakajat. ECM toimii tässä tapauksessa oikein, koska sen sijaan, että otettaisiin huomioon Z p ylittävä kertova ryhmä , jonka järjestys on aina p − 1 , tarkastellaan satunnaisen elliptisen käyrän ryhmää äärellisen kentän Z p yli .

Elliptisellä käyrällä Z p :n päällä olevan pisteryhmän järjestystä rajoittaa Hassen lause : p + 1 − 2 √ p p + 1 + 2 √ p . Vaikuttaa tärkeältä tutkia [8] todennäköisyyttä, että jokin sileä luku voi olla tässä välissä (tässä tapauksessa on käyriä, joiden järjestys on sileä luku). Ei ole todisteita siitä, että Hasse-välissä olisi aina jokin sileä luku, mutta käyttämällä heuristisia todennäköisyysmenetelmiä, Canfield –Erdős-Pomerance -lausetta [ 9] ja L-merkintää , saadaan arvio, että riittää ottamaan L [ √ 2 /2, √ 2 ] käyriä, kunnes saadaan tasainen ryhmäjärjestys. Tämä heuristinen arvio soveltuu hyvin käytännössä. $|E|$ $\leq |E|\leq$

Esimerkki

Luvun n = 455839 faktorointi [ 10] .

Elliptinen käyrä ja tällä käyrällä oleva piste valitaan

y^{2}=x^{3}+5x-5,~P=(1,~1).

10 lasketaan peräkkäin! P :

1. Pistekoordinaatit lasketaan . $P_{2}=2!P=2P$

Tangentin kulman tangentti pisteessä P on:

s={\frac {dy}{dx}}={\frac {3x^{2}+5}{2y}}=4.

Pistekoordinaatit : $P_2$

x_{2}=s^{2}-2x_{1}=14{\pmod {n)),

y_{2}=s(x_{1}-x_{2})-y=4(1-14)-1=-53{\pmod {n)).

Voidaan osoittaa, että piste 2P todella sijaitsee käyrällä:

(-53)^{2}=2809=14^{3}+5\cdot 14-5.

2. Laskettu . $P_{3}=3!P=6P$

Tangentin kulmakertoimen tangentti pisteessä 2 P on

s=(3\cdot 196+5)/(2(-53))=-593/106=322522{\pmod {n))

. Moduulin 593/106 laskemiseen voit käyttää laajennettua Euklidin algoritmia : 455839 = 4300 106 + 39, sitten 106 = 2 39 + 28, sitten 39 = 28 + 11, sitten 28 = 2 11 + 1 = 6, + 5, sitten 6 = 5 + 1. Siksi GCD(455839, 106) = 1 ja päinvastoin: 1 = 6 - 5 = 2 6 - 11 = 2 28 - 5 11 = 7 28 - 5 39 = 7 106 - 19 39 = 81707 106 - 19 455 839. Mistä 1/106 = 81707 (modi 455839), siis −593 / 106 = 322522 (modi 455839).

Ottaen huomioon lasketut s , lasketaan pisteen 2(2 P ) koordinaatit, kuten edellä on tehty: 4 P = (259851, 116255). Voidaan osoittaa, että piste todella sijaitsee elliptisellä käyrällämme.
Yhteenveto 4 P ja 2 P löytyy . $P_{3}=(179685,-28708)$

3. Samoin voit laskea , , ja niin edelleen. Laskettaessa 640 P , voit huomata, että käänteiselementin laskenta arvoon 599 (mod 455839) vaaditaan. Koska 455839 on jaollinen luvulla 599, löydetään tarvittava hajonta: 455839 = 599 761. $P_{4}=4!P$ $P_{5}=5!P$

Laskennallinen monimutkaisuus

Olkoon n: n pienin jakaja p . Tällöin suoritettujen aritmeettisten operaatioiden lukumäärä voidaan arvioida arvolla [11] : (tai L - merkinnällä ). Jos korvaamme p : llä , saamme subeksponentiaalisen kompleksisuusestimaatin: . $e^{\sqrt {(2+o(1))\ln p\ln(\ln p)))\ln ^{2}n$ $L_{p}[1/2;{\sqrt {2}}]$ $n^{1/2}$ $L_{n}[1/2;1]$

Jos vertaamme elliptisten käyrien menetelmää muihin tekijöihin jakamismenetelmiin, niin tämä menetelmä kuuluu osaeksponentiaalisten [1] tekijöiden laskentamenetelmien luokkaan , ja siksi se toimii nopeammin kuin mikään eksponentiaalinen menetelmä. Verrattuna kvadraattiseen seulamenetelmään (QS) ja numerokenttäseulamenetelmään (NFS) kaikki riippuu n:n pienimmän jakajan koosta [ 12] . Jos luku n valitaan, kuten RSA :ssa, kahden suunnilleen samanpituisen alkuluvun tuloksi, niin elliptisen käyrän menetelmällä on sama estimaatti kuin neliöseulamenetelmällä, mutta se on huonompi kuin lukukenttäseulamenetelmä [13 ] .

Algoritmi projektiivisillä koordinaatteilla

Ennen kuin tarkastellaan projektiivista tasoa yli , kannattaa harkita tavallista projektiivista tasoa ℝ:n yli: pisteiden sijasta huomioidaan 0:n kautta kulkevat suorat. Suora voidaan määrittää käyttämällä nollasta poikkeavaa pistettä seuraavasti: tämän suoran mille tahansa pisteelle ⇔ ∃ c ≠ 0, jolloin x' = c x , y' = c y ja z' = c z . Tämän ekvivalenssisuhteen mukaan avaruutta kutsutaan projektiivitasoksi . Tason pisteet vastaavat kolmiulotteisen avaruuden viivoja, jotka kulkevat arvon 0 kautta. Huomaa, että pistettä ei ole tässä avaruudessa, koska se ei määrittele arvon 0 kautta kulkevaa suoraa. Lenstran algoritmi ei vaadi kentän ℝ käyttöä , äärellinen kenttä tarjoaa myös ryhmän rakenteen elliptisen käyrän yli. Sama käyrä, mutta operaatioilla , ei kuitenkaan muodosta ryhmää, jos se ei ole alkuluku. Elliptisiä käyriä käyttävä tekijälaskentamenetelmä käyttää summauslain ominaisuuksia tapauksissa, joissa se ei ole yksinkertainen. $\mathbb {Z} _{n}$ $(x, y, z)$ ${\näyttötyyli (x',y',z')}$ ${\näyttötyyli (P^{2})}$ ${\näyttötyyli (x:y:z)}$ $(0:0:0)$ $\mathbb {Z} _{n}$ $n$ $n$

Faktorisointialgoritmi projektitiivisissa koordinaateissa [14] :. Neutraali elementti annetaan tässä tapauksessa äärettömyyden pisteellä . Olkoon n kokonaisluku ja positiivinen luku, elliptinen käyrä . $(0:1:0)$ $E(Z_{n})=\{(x:y:z)\in P^{2}\ |\ y^{2}z=x^{3}+axz^{2}+bz ^{3}\}$

Valittu ( a ≠ 0). $x_{P},y_{P},a$ $\sisään$ $\mathbb {Z} _{n}$
Laskettu . Elliptinen käyrä E on annettu muodossa (Weierstrassin muoto). Projektiivisten koordinaattien avulla elliptinen käyrä voidaan kirjoittaa homogeeniseksi yhtälöksi . sijaitsee tällä käyrällä. ${\displaystyle b=y_{P}^{2}-x_{P}^{3}-ax_{P))$ $y^{2}=x^{3}+ax+b$ ${\displaystyle ZY^{2}=X^{3}+aZ^{2}X+bZ^{3))$ $P=(x_{P}:y_{P}:1)$
Yläraja on valittu . Huomaa: tekijöitä voi olla vain, jos ryhmän E järjestys on B - tasainen luku. Tämä tarkoittaa, että kaikkien alkutekijöiden E over on oltava pienempiä tai yhtä suuria kuin B . $B\in \mathbb {Z}$ $\mathbb {Z} _{p}$ $\mathbb {Z} _{p}$
NOC lasketaan . $k=$ ${\näyttötyyli (1,\pisteet ,B)}$
Laskettu kehässä . On tärkeää huomata, että jos | | - B-smooth , ja n on yksinkertainen (tässä tapauksessa kenttä), sitten . Kuitenkin, jos | | - B-tasainen jollekin luvulle p , joka on n: n jakaja , tulos ei välttämättä ole (0:1:0), koska yhteen- ja kertolasku ei välttämättä toimi yhtä hyvin, jos n ei ole alkuluku. Siten on mahdollista löytää n:n ei-triviaali jakaja . $\underbrace {P+P+\dots +P} _{k}$ $E(\mathbb {Z} _{n})$ $E(\mathbb {Z} _{n})$ $\mathbb {Z} _{n}$ $kP=(0:1:0)$ $E(\mathbb {Z} _{p})$
Jos jakajaa ei löydy, algoritmi toistetaan vaiheesta 2 alkaen.

Kohdassa 5 laskeminen ei ehkä ole mahdollista, koska kahden pisteen lisääminen elliptiselle käyrälle vaatii laskennan , mikä ei aina ole mahdollista, jos n ei ole alkuluku. On mahdollista laskea kahden pisteen summa seuraavalla tavalla, joka ei vaadi n : n primenessia (ei vaadi sen olevan kenttä): $kP$ ${\näyttötyyli (x_{1}-x_{2})^{-1))$ $\mathbb {Z} _{n}$

$\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})$ , koordinaatteja yksinkertaistetaan edelleen niin paljon kuin mahdollista (ei-triviaali jakaja n löytyy, jos yksinkertaistamisen aikana tapahtuu virhe).

Edwardsin käyrien käyttäminen

Edwards-käyrien käyttö mahdollistaa [15] vähentää modulaaristen operaatioiden määrää ja lyhentää algoritmin suoritusaikaa verrattuna elliptisiin käyriin Weierstrass-muodossa ( ) ja Montgomeryn muodossa ( ). $y^{2}=x^{3}+ax+b{\pmod {p}}$ $Tekijä^{2}=x^{3}+Ax^{2}+x$

Määritelmä: Antaa olla kenttä, jonka ominaisuus ei ole luku , Ja anna . Sitten Edwardsin käyrä määritellään seuraavasti: On viisi tapaa muodostaa joukko pisteitä Edwardsin käyrään: joukko affiineja , joukko projektiopisteitä , joukko käänteisiä pisteitä , joukko laajennettuja pisteitä ja joukko suoritetut pisteet . ). Esimerkiksi affiinipisteiden joukko annetaan seuraavasti: . $k$ $2$ $d\in k\setminus \{0,1\}$ ${\displaystyle E_{E,d))$ $x^{2}+y^{2}=1+dx^{2}y^{2}.$ $\{(x,y)\in A^{2}:x^{2}+y^{2}=1+dx^{2}y^{2}\}$

Yhteenlaskuoperaatio: Yhteenlaskulaki annetaan kaavalla . $(e,f),(g,h)\mapsto \left({\frac {eh+fg}{1+degfh)),{\frac {fh-eg}{1-degfh))\oikea )$

Piste (0,1) on neutraali elementti ja pisteen käänteisarvo on . ${\näyttötyyli (e,f)}$ ${\näyttötyyli (-e,f)}$

Muita muotoja saadaan samalla tavalla kuin projektiivinen Weierstrass-käyrä saadaan affiinikäyrästä.

Yhteenlaskuesimerkki: Voit havainnollistaa summauslakia käyttämällä esimerkkiä elliptisestä käyrästä Edwards-muodossa, jossa d =2: , ja siinä on pisteitä. Ehdotetaan tarkistettavaksi, että P 1 :n summa neutraalielementillä (0,1) on yhtä suuri kuin P 1 . Todella: ${\displaystyle }x^{2}+y^{2}=1+2x^{2}y^{2}$ $P_{1}=(1,0)$

x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}} }=1

y_{3}={\frac {y_{1}y_{2}-x_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}} }=0

Jokaisella Edwards-muodon elliptisellä käyrällä on järjestyspiste 4. Siksi Edwards-käyrän jaksollinen ryhmä on isomorfinen tai . $\mathbb {Q}$ $\mathbb {Z} _{4},\mathbb {Z} _{8},\mathbb {Z} _{12},\mathbb {Z} _{2}\times \mathbb {Z} _ {neljä}$ $\mathbb {Z} _{2}\times \mathbb {Z} _{8}$

Lenstra-algoritmia käyttävien tekijöiden jakamisen kannalta mielenkiintoisimmat [16] tapaukset ovat ja . $\mathbb {Z} _{12}$ $\mathbb {Z} _{2}\times \mathbb {Z} _{8}$

Esimerkki käyrästä, joka sisältää jaksollisen ryhmän , joka on isomorfinen : $\mathbb {Z} _{12}$

$x^{2}+y^{2}=1+dx^{2}y^{2}$ pisteen ollessa yksikköympyrässä , jonka keskipiste on piste (0,-1). ${\näyttötyyli (a,b)}$

$b\in (-2,0)\setminus \{-1,-1/2\},a^{2}=-(b^{2}+2b)$ ja $d=-{\frac {2b+1}{a^{2}b^{2}}}={\frac {2b+1}{b^{3}(b+2)))$
$a={\frac {u^{2}-1}{u^{2}+1)),b=-{\frac {(u-1)^{2)){u^{2 }+1}}$ ja $d={\frac {(u^{2}+1)^{3}(u^{2}-4u+1)}{(u-1)^{6}(u+1)^ {2}}},u\notin \{0,\pm 1\}.$

$a(1/u)=-a(u),b(1/u)=b(u),d(1/u)=d(u)$

Katso myös

Muistiinpanot

↑ 1 2 Bressoud, 2000 , s. 331.
↑ Parker, 2014 .
↑ Bressoud, 2000 .
↑ Brent, 1998 .
↑ ECM:n löytämät 50 suurinta jakajaa . Käyttöpäivä: 27. marraskuuta 2016. Arkistoitu alkuperäisestä 20. helmikuuta 2009. (määrätön)
↑ Lenstra, 1987 , s. 16-20.
↑ 12 Lenstra , 1987 .
↑ Lenstra, Number-Theoretic Algorithms, 1986 , s. 16.
↑ Canfield, 1983 .
↑ Johdatus kryptografiaan koodausteorialla, 2006 .
↑ Vasilenko, 2006 , s. 109.
↑ Lenstra, Number-Theoretic Algorithms, 1986 , s. 331.
↑ Brent, 1998 , s. 12.
↑ Vasilenko, 2006 , s. 112.
↑ ECM käyttäen Edwardsin käyriä, 2013 , s. 2-3.
↑ ECM käyttäen Edwardsin käyriä, 2013 , s. 19.

Kirjallisuus

Koblitz NA Lukuteorian ja kryptografian kurssi (uuspr.) . - Springer-Verlag , 1987.
Lenstra AK, Lenstra HW, Lovász L. Polynomien faktorointi rationaalisilla kertoimilla (neopr.) // Math. Ann. . - 1982. - T. 261 .
Lenstra Jr., HW Kokonaislukujen faktorointi elliptisten käyrien avulla (englanniksi) // Annals of Mathematics : Journal. - 1987. - Voi. 126 , nro. 2 . - s. 649-673 .
Trappe, W., Washington, LC Johdatus kryptografiaan koodausteorialla . — Toiseksi. - Pearson Prentice Hall , 2006. - ISBN 0-13-186239-1 .
Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters. ECM käyttäen Edwardsin käyriä // Laskennan matematiikka : päiväkirja. - 2013. - Vol. 82 . - s. 1139-1179 . - doi : 10.1090/S0025-5718-2012-02633-0 .
Ishmukhametov Sh. T. Faktorisointimenetelmät luonnollisille lukuille . - Kazan: Kazan. un.. - 2011. - 190 s.
David Bressoud ja Stan Wagon. Laskennallisen lukuteorian kurssi. - Key College Publishing / Springer, 2000. - S. 168-169. — 366 s. - ISBN 978-1-930190-10-8 .
Steven Galbraith. Julkisen avaimen kryptografian matematiikka. - Cambridge University Press, 2012. - P. 330-332. - 630 s. — ISBN 9781139012843 .
O.N. Vasilenko. Lukuteoreettiset algoritmit kryptografiassa. — M.: MTsNMO, 2006. — 335 s. — ISBN 5-94057-103-4 .
W. Trappe ja L. C. Washington. Johdatus kryptografiaan koodausteorialla. — Toiseksi. - Pearson Prentice Hall, 2006. - ISBN 0-13-186239-1 .
Parker D. Elliptiset käyrät ja Lenstran faktorointialgoritmi (englanniksi) // University of Chicago: REU 2014. - 2014.
ER Canfield , Paul Erdős , Carl Pomerance. Oppenheimin ongelmasta "Factorisatio Numerorum" (englanniksi) // Numeroteorian lehti. - 1983. - Numero. 17 .
Richard P. Brent. Joitakin elliptisiä käyriä käyttäviä kokonaislukujen kertoimia käyttäviä algoritmeja // Australian Computer Science Communications 8, 149-163. – 1998.
HW Lenstra, JR. Elliptiset käyrät ja lukuteoreettiset algoritmit (englanniksi) // Proceedings of the International Congress of Mathematicians. - 1986. Arkistoitu 29. maaliskuuta 2017.
Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen Lenstra, Emmanuel Thomé, Joppe Bos, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofejev, Paul Zimmermann. 768-bittisen RSA-moduulin faktorointi // Cryptology ePrint Archive, raportti 2010/006. – 2010.

Linkit

- Elliptisen käyrän faktorointi , Java-sovelman toteutus , joka yhdistää ECM:n ja itsealustava neliöllinen seulamenetelmä (jälkimmäinen valitaan, kun se on nopeampi tietyssä tapauksessa).
GMP-ECM , ECM:n tehokas toteutus.
ECMNet , yksinkertainen palvelin-asiakas-toteutus.
pyecm , ECM:n Python 2 -toteutus.

Lukuteoreettiset algoritmit
Yksinkertaisuustestit	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saksi Nightingale - Strassen
Alkulukujen löytäminen	Iterointi jakajien yli Eratosthenesin seula Atkinin seula Seula Sundarama
Faktorisointi	Iterointi jakajien yli Fermat menetelmä p −1 Pollardin menetelmä Pollardin ρ-algoritmi Lehmannin menetelmä Elliptisen käyrän menetelmä (Lenstran algoritmi) Dixonin algoritmi Neliömäinen seula
Diskreetti logaritmi	Gelfond-Shanks -algoritmi Polig-Hellman-algoritmi Pollardin ρ-menetelmä Pollardin kenguru-algoritmi Adlemanin algoritmi COS-algoritmi
GCD:n löytäminen	Eukleideen algoritmi Kehittynyt algoritmi Binäärinen algoritmi
Modulo-aritmetiikka	Montgomeryn algoritmi Kiinan jäännöslause
Lukujen kerto- ja jakolasku	Karatsuba-algoritmi Toom-Cook-algoritmi Schönhage-Strassen-algoritmi Fuhrer-algoritmi Harvey-van der Hoeven-algoritmi Burnickel-Ziegler-algoritmi
Neliöjuuren laskeminen	Tonelli-Shanks-algoritmi Berlekamp-Rabin-algoritmi