Faktorozás elliptikus görbékkel

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2016. október 14-én felülvizsgált verziótól ; az ellenőrzések 57 szerkesztést igényelnek .

Az elliptikus görbékkel történő faktorizálás ( angol elliptikus görbe faktorizációs módszer , rövidítés ECM ) vagy a Lenstra -féle elliptikus görbék faktorizálási módszere ( angol Lenstra elliptic curve factorization ) egy természetes szám elliptikus görbék segítségével történő faktorálási algoritmusa . Ez az algoritmus szubexponenciális bonyolultságú [1] . Az ECM a harmadik leggyorsabban futó [2] az általános számmezőszita módszer és a kvadratikus szita módszer után .

A gyakorlatban ez a legalkalmasabb egy szám kis prímosztóinak megtalálására, ezért rendkívül speciális [3] algoritmusnak tekintik.

Ez a legjobb algoritmus [4] 20-25 karakter hosszúságú (64…83 bites) prímosztók keresésére, mivel bonyolultsága elsősorban a legkisebb p prímosztótól függ , és nem a faktorizált számtól.

Gyakran használják egy szám kis prímosztóinak azonosítására (eldobására). Ha az algoritmus működése után kapott szám továbbra is összetett, akkor a fennmaradó tényezők nagy számok, és a további bővítéshez célszerű általánosabb faktorizációs algoritmusokat alkalmazni.

Az ezzel az algoritmussal talált legnagyobb osztó 83 karakter hosszú, és Ryan Propper találta meg 2013. szeptember 7-én [5] .

Algoritmus

Természetes szám faktorizációs algoritmusa (nem triviális osztó keresése) [6] : $n$

Egy véletlenszerű elliptikus görbét választunk : alakú egyenlettel , és ezen a görbén választunk egy nem triviális pontot . Ezt így lehet megtenni: $E$ $\mathbb {Z} _{n}$ $E$ $y^{2}=x^{3}+ax+b{\pmod {n))$ $P(x_{0},y_{0})$
1. A számok véletlenszerűen kerülnek kiválasztásra . $x_{0},y_{0},a$ $\ban ben$ $\mathbb {Z} _{n}$
2. Kiszámolva . $b=y_{0}^{2}-x_{0}^{3}-ax_{0}{\pmod {n))$
Olyan egész számot választunk , amely nagyszámú kis szám szorzata. Például, ahogy választhat: $e$ $e$
- Néhány kis szám faktorál . $B!$ $B$
- Több kis prímszám szorzata kis hatványokkal. Ez azt jelenti, hogy a prímszámokat (amelyek nem haladják meg a bizonyos számot ), és a fokokat úgy választják meg, hogy a megfelelő hatványra emelés eredménye ne haladjon meg egy bizonyos számot : $l_{i}$ $B$ ${\alpha _{i))$ $l_{i}$ $l_{i}^{\alpha _{i))$ $C$
$e=\prod _{\ell \leq B}\ell ^{\alpha _{i)),$ hol a legnagyobb a lehetséges mutatók közül, amelynél . $\alpha _{i}=\left\lfloor \log _{\ell }C\right\rfloor$ $\ell ^{\alpha _{i}}\leq C$
Az elliptikus görbén lévő szorzat kiszámítása : $eP$ $E$ ${\displaystyle eP=\underbrace {P\boxplus \dots \boxplus P} _{e))$ , ahol a csoporttörvény által meghatározott összeadási művelet . $\box plusz$ Az összeadás művelethez meg kell találni az összegzett pontokat összekötő szakasz meredekségét , ezért szükséges a modulo n osztás művelete . A modulo művelet a kiterjesztett Euclid algoritmussal történik . Konkrétan, ha valamilyen v számmal osztunk (mod n ), akkor a gcd ( v , n ) megtalálását jelenti . A gcd( v , n ) 1 esetén gcd( v , n ) n , -összeadás nem ad értelmes pontot az elliptikus görbén, ami azt jelenti, hogy gcd( v , n ) n nem triviális osztója . . Ennek alapján a számítási folyamatban a következő esetek lehetségesek: $\neq$ $\neq$ $\box plusz$ $eP$
- Ha a számítás során nem fordult elő irreverzibilis elem (mod n ) , akkor másik elliptikus görbét és pontot kell választani, és az algoritmust elölről meg kell ismételni. $E$ $P(x_{0},y_{0})$
- Ha valamelyik szakaszban , ahol ( ), akkor másik elliptikus görbét és pontot kell választani, és az algoritmust elölről meg kell ismételni, mert a pont a további összeadási műveletek után változatlan marad. $e'P=\underbrace {P\boxplus \dots \boxplus P} _{e'}=\infty$ $e'\leq e$ $E$ $P(x_{0},y_{0})$ $\infty$
- Ha a számítás valamely szakaszában gcd( v , n ) 1 és gcd( v , n ) n , akkor gcd( v , n ) n szükséges nem triviális osztója . $\neq$ $\neq$

Indoklás

Az n számra felvett egyenlet egy elliptikus görbét határoz meg . Ha a p és q számok az n szám két prímosztói , akkor a fenti egyenlet akkor is igaz, ha modulo p vagy modulo q felvesszük . Azaz : és : két elliptikus görbét határoz meg (kisebb, mint ). Azonban még egy adott összeadási művelet mellett is nemcsak elliptikus görbék, hanem csoportok is . Legyen bennük N p és N q elem, akkor ha: $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 plusz$

$P$ - az eredeti görbe bármely pontja
$k_i$ pozitív számok , például: $k_{i}P=\infty$ $E_1$
$k$ a minimuma $k_i$

Akkor Lagrange tétele szerint igaz, hogy

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

Hasonló állítás igaz a modulo q görbére is .

A Z p feletti elliptikus görbén fekvő pontok csoportjának sorrendjét a Hasse-tétel határolja : p + 1 − 2 √ p p + 1 + 2 √ p $|E|$ $\leq |E|\leq$

Véletlenszerűen választott elliptikus görbe esetén az N p és N q rendek a Hasse-tétel által határolt véletlen számok (lásd alább). Nem valószínű, hogy N p és N q prímosztóinak többsége megegyezik, és valószínű, hogy az eP kiszámításakor néhány modulo p , de nem mod q fog találkozni , vagy fordítva. Ha ez a helyzet, akkor kP nem létezik az eredeti görbén, és a számításokban olyan v -t találtunk, hogy vagy gcd( v , p ) = p vagy gcd( v , q ) = q , de mindkettő nem. Ekkor gcd( v , n ) n nem triviális osztója . $kP=\infty$

Az ECM a régebbi Pollard-féle P-1 módszer finomítása [7] . A p - 1 algoritmus megtalálja p prímosztóit úgy, hogy ( p - 1) B -sima valamilyen kis B esetén . Bármely e -re, amelyik többszöröse ( p − 1) , és bármely a -ra , amely p - hez viszonylag prím , a Fermat-tétel szerint a e ≡ 1 (mod p ) . Ekkor gcd ( a e − 1, n ) nagy valószínűséggel osztója lesz n -nek . A p − 1 algoritmus azonban meghiúsul [7] , ha p -nek nagy prímosztói vannak. Az ECM ebben az esetben helyesen működik, mert ahelyett, hogy a Z p feletti multiplikatív csoportot vesszük figyelembe , amelynek sorrendje mindig p − 1 , egy Z p véges mező feletti véletlenszerű elliptikus görbe csoportját tekintjük .

A Z p feletti elliptikus görbén fekvő pontcsoportok sorrendjét a Hasse-tétel határolja : p + 1 − 2 √ p p + 1 + 2 √ p . Fontosnak tűnik megvizsgálni [8] , hogy mekkora a valószínűsége annak, hogy ebben az intervallumban sima szám található (ebben az esetben vannak görbék, amelyek sorrendje sima szám). Nincs bizonyíték arra, hogy a Hasse-intervallumban mindig van valamilyen sima szám, de heurisztikus valószínűségi módszerekkel, a Canfield –Erdős–Pomerance-tétellel [ 9] és az L-jelöléssel azt a becslést kapjuk, hogy elegendő L -t venni [ √ 2 /2, √ 2 ] görbék, amíg sima csoportsorrendet nem kapunk. Ez a heurisztikus becslés jól alkalmazható a gyakorlatban. $|E|$ $\leq |E|\leq$

Példa

Az n = 455839 szám faktorizálása [10] .

Egy elliptikus görbe és egy ezen a görbén fekvő pont kerül kiválasztásra

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

10-et szekvenciálisan számítanak ki! P :

1. A pontkoordináták kiszámítása . $P_{2}=2!P=2P$

Az érintő meredekségének érintője a P pontban :

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

Pont koordinátái : $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)).

Megmutatható, hogy a 2P pont valóban a görbén fekszik:

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

2. Számított . $P_{3}=3!P=6P$

Az érintő meredekségének érintője a 2 P pontban az

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

. Az 593/106 modulo n kiszámításához használhatja a kiterjesztett Euklidész algoritmust : 455839 = 4300 106 + 39, majd 106 = 2 39 + 28, majd 39 = 28 + 11, majd 28 = 2 11 + 1 = 6 + 5, majd 6 = 5 + 1. Ezért GCD(455839, 106) = 1, és fordítva: 1 = 6 - 5 = 2 6 - 11 = 2 28 - 5 11 = 7 28 - 5 39 = 7 106 - 19 39 = 81707 106 - 19 455 839. Ahonnan 1/106 = 81707 (mod 455839), így −593 / 106 = 322522 (mod 455839).

A számított s figyelembe vételével a 2(2 P ) pont koordinátáit ugyanúgy számítjuk ki, mint ahogyan fentebb: 4 P = (259851, 116255). Megmutatható, hogy a pont valóban az elliptikus görbénkön fekszik.
4 P és 2 P összegzése található . $P_{3}=(179685,-28708)$

3. Hasonlóképpen kiszámíthatja a , , és így tovább. A 640 P kiszámításakor észreveheti, hogy az inverz elemet 599-re (mod 455839) kell kiszámítani. Mivel a 455839 osztható 599-cel, a szükséges bontás megtalálható: 455839 = 599 761. $P_{4}=4!P$ $P_{5}=5!P$

Számítási összetettség

Legyen n legkisebb osztója p . Ekkor a végrehajtott aritmetikai műveletek száma a [11] : értékkel becsülhető (vagy L-jelölésben ) . Ha p - t helyettesítjük -re, akkor szubexponenciális komplexitásbecslést kapunk: . $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]$

Ha összehasonlítjuk az elliptikus görbék módszerét más faktorizációs módszerekkel, akkor ez a módszer a szubexponenciális [1] faktorizációs módszerek osztályába tartozik , ezért gyorsabban működik, mint bármely exponenciális módszer. Ha összehasonlítjuk a kvadratikus szita módszerrel (QS) és a számmező szita módszerrel (NFS) , akkor mindez az n legkisebb osztójának méretétől függ [12] . Ha az n számot, mint az RSA -ban, két, megközelítőleg azonos hosszúságú prímszám szorzataként választjuk, akkor az elliptikus görbe módszere ugyanolyan becsléssel rendelkezik, mint a másodfokú szita módszer, de rosszabb, mint a számmező szita módszer [13 ] .

Algoritmus projektív koordinátákkal

Mielőtt a projektív síkot a felettinek tekintenénk, érdemes figyelembe venni a szokásos projektív síkot ℝ felett: pontok helyett a 0-n átmenő egyeneseket vesszük figyelembe. Egy egyenest nullától eltérő pont használatával a következőképpen definiálhatunk: ennek az egyenesnek bármely pontjára ⇔ ∃ c ≠ 0, úgy, hogy x' = c x , y' = c y és z' = c z . Ennek az ekvivalenciarelációnak megfelelően a teret projektív síknak nevezzük . A sík pontjai a 0-n átmenő háromdimenziós tér egyeneseinek felelnek meg . Vegye figyelembe, hogy a pont nem létezik ebben a térben, mivel nem definiál 0-n átmenő egyenest. A Lenstra-algoritmus nem igényli a ℝ mező használatát. , a véges mező a csoport szerkezetét is megadja az elliptikus görbe felett. Ugyanez a görbe azonban a következő műveletekkel nem alkot csoportot, ha nem prímszám. Az elliptikus görbéket alkalmazó faktorizációs módszer az összeadás törvényének jellemzőit használja olyan esetekben, amikor nem egyszerű. $\mathbb {Z} _{n}$ $(x,y,z)$ $(x',y',z')$ $(P^{2})$ ${\megjelenítési stílus (x:y:z)}$ $(0:0:0)$ $\mathbb {Z} _{n}$ $n$ $n$

Faktorizációs algoritmus projektív koordinátákban [14] :. A semleges elemet ebben az esetben a végtelenben lévő pont adja . Legyen n egész és pozitív szám, elliptikus görbe . $(0:1:0)$ $E(Z_{n})=\{(x:y:z)\in P^{2}\ |\ y^{2}z=x^{3}+axz^{2}+bz ^{3}\}$

Kiválasztva ( a ≠ 0). $x_{P},y_{P},a$ $\ban ben$ $\mathbb {Z} _{n}$
Kiszámolva . Az E elliptikus görbét adjuk meg (Weierstrass-forma). A projektív koordináták segítségével egy elliptikus görbe homogén egyenletként írható fel . ezen a görbén fekszik. ${\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)$
A felső határ van kiválasztva . Megjegyzés: csak akkor lehetnek tényezők, ha az E csoport sorrendje B - sima szám . Ez azt jelenti, hogy az összes E over prímtényezőnek kisebbnek vagy egyenlőnek kell lennie B -nél . $B\in \mathbb {Z}$ $\mathbb {Z} _{p}$ $\mathbb {Z} _{p}$
A NOC kiszámítása megtörténik . $k=$ ${\megjelenítési stílus (1,\pontok ,B)}$
A ringben számolva . Fontos megjegyezni, hogy ha | | - B-sima , és n egyszerű (jelen esetben mező), akkor . Ha azonban | | - B-sima néhány p számra, amely n osztója , az eredmény nem biztos, hogy (0:1:0) lesz, mert az összeadás és a szorzás nem működik jól, ha n nem prímszám. Így meg lehet találni n nem triviális osztóját . $\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})$
Ha az osztó nem található, akkor az algoritmus megismétlődik a 2. lépéstől.

Az 5. pontban előfordulhat, hogy a számítás nem lehetséges, mivel egy elliptikus görbe két pontjának összeadásához ki kell számítani , ami nem mindig lehetséges, ha n nem prímszám. Két pont összegét a következő módon lehet kiszámítani, amihez nem szükséges n elsősége (nem kell, hogy mező legyen): $kP$ ${\displaystyle (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})$ , a koordinátákat a lehető legnagyobb mértékben tovább egyszerűsítjük (egy nem triviális n osztó található, ha az egyszerűsítés során hiba lép fel).

Edwards-görbék használata

Az Edwards-görbék használata lehetővé teszi [15] számára, hogy csökkentse a moduláris műveletek számát, és csökkentse az algoritmus végrehajtási idejét a Weierstrass ( ) és a Montgomery ( ) alakú elliptikus görbékhez képest . $y^{2}=x^{3}+ax+b{\pmod {p}}$ $By^{2}=x^{3}+Ax^{2}+x$

Definíció: Legyen olyan mező, amelynek jellemzője nem szám , és legyen . Ekkor az Edwards-görbe a következőképpen definiálható. Ötféle módon lehet pontkészletet létrehozni egy Edwards-görbén: affin pontok halmaza, projektív pontok halmaza, fordított pontok halmaza , kiterjesztett pontok halmaza és egy halmaz teljesített pontok . ). Például az affin pontok halmaza így van megadva: . $k$ $2$ ${\displaystyle 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}\}$

Összeadás művelet: Az összeadás törvényét a képlet adja meg . $(e,f),(g,h)\mapsto \left({\frac {eh+fg}{1+degfh)),{\frac {fh-eg}{1-degfh))\right )$

A (0,1) pont a semleges elem, a pont inverze pedig . ${\megjelenítési stílus (e,f)}$ $(-e,f)$

Más formákat hasonló módon kapunk, mint ahogyan egy projektív Weierstrass-görbét kapunk egy affin görbéből.

Összeadási példa: Az összeadási törvényt demonstrálhatja egy Edwards alakú elliptikus görbe példájával, ahol d =2: , és pontok vannak rajta. Javasoljuk annak ellenőrzését, hogy P 1 összege a semleges elemmel (0,1) egyenlő-e P 1 -gyel . Igazán: ${\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

Az Edwards-alakú minden elliptikus görbének van egy 4-es sorrendje. Ezért az Edwards-görbe feletti periodikus csoport izomorf -val vagy -vel . $\mathbb {Q}$ $\mathbb {Z} _{4},\mathbb {Z} _{8},\mathbb {Z} _{12},\mathbb {Z} _{2}\times \mathbb {Z} _ {négy}$ ${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{8))$

A Lenstra algoritmussal végzett faktorizálásnál a legérdekesebb [16] eset a és . $\mathbb {Z} _{12}$ ${\displaystyle \mathbb {Z} _{2}\times \mathbb {Z} _{8))$

Példa egy olyan görbére, amely a következővel izomorf periodikus csoportot tartalmaz : $\mathbb {Z} _{12}$

$x^{2}+y^{2}=1+dx^{2}y^{2}$ az egységkörön fekvő ponttal , amelynek középpontja a (0,-1) pontban van. ${\megjelenítési stílus (a,b)}$

$b\in (-2,0)\setminus \{-1,-1/2\},a^{2}=-(b^{2}+2b)$ és $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}}$ és $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)$

Lásd még

Jegyzetek

↑ 1 2 Bressoud, 2000 , p. 331.
↑ Parker, 2014 .
↑ Bressoud, 2000 .
↑ Brent, 1998 .
↑ Az ECM által talált 50 legnagyobb osztó . Hozzáférés dátuma: 2016. november 27. Az eredetiből archiválva : 2009. február 20. (határozatlan)
↑ Lenstra, 1987 , p. 16-20.
↑ Lenstra 12. , 1987 .
↑ Lenstra, Számelméleti algoritmusok, 1986 , p. 16.
↑ Canfield, 1983 .
↑ Bevezetés a kriptográfiába kódoláselmélettel, 2006 .
↑ Vasilenko, 2006 , p. 109.
↑ Lenstra, Számelméleti algoritmusok, 1986 , p. 331.
↑ Brent, 1998 , p. 12.
↑ Vasilenko, 2006 , p. 112.
↑ ECM Edwards-görbék használatával, 2013 , p. 2-3.
↑ ECM Edwards-görbék használatával, 2013 , p. 19.

Irodalom

Koblitz NA Számelmélet és kriptográfiai tanfolyam (neopr.) . – Springer-Verlag , 1987.
Lenstra AK, Lenstra HW, Lovász L. Polinomok faktorálása racionális együtthatókkal (neopr.) // Math. Ann. . - 1982. - T. 261 .
Lenstra Jr., HW Egész számok faktorálása elliptikus görbékkel (angol) // Annals of Mathematics : Journal. - 1987. - 1. évf. 126. sz . 2 . - P. 649-673 .
Trappe, W., Washington, LC Bevezetés a kriptográfiába kódoláselmélettel . — Másodszor. - Pearson Prentice Hall , 2006. - ISBN 0-13-186239-1 .
Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters. ECM Edwards-görbék használatával // Számítási matematika : folyóirat. - 2013. - Kt. 82 . - P. 1139-1179 . - doi : 10.1090/S0025-5718-2012-02633-0 .
Ishmukhametov Sh. T. Faktorizációs módszerek természetes számokra . - Kazan: Kazan. un.. - 2011. - 190 p.
David Bressoud és Stan Wagon. Számítási számelmélet tanfolyam. - Key College Publishing / Springer, 2000. - S. 168-169. — 366 p. - ISBN 978-1-930190-10-8 .
Steven Galbraith. A nyilvános kulcsú kriptográfia matematikája. - Cambridge University Press, 2012. - P. 330-332. — 630 p. — ISBN 9781139012843 .
O. N. Vaszilenko. Számelméleti algoritmusok a kriptográfiában. — M.: MTsNMO, 2006. — 335 p. — ISBN 5-94057-103-4 .
W. Trappe és L. C. Washington. Bevezetés a kriptográfiába kódoláselmélettel. — Másodszor. - Pearson Prentice Hall, 2006. - ISBN 0-13-186239-1 .
Parker D. Elliptikus görbék és Lenstra faktorizációs algoritmusa (angol) // University of Chicago: REU 2014. - 2014.
ER Canfield , Paul Erdős , Carl Pomerance. Oppenheim problémájáról a „Factorisatio Numerorum”-ra (angol) // Számelméleti folyóirat. - 1983. - Kiadás. 17 .
Richard P. Brent. Néhány egész szám faktorizációs algoritmus elliptikus görbéket használva // Australian Computer Science Communications 8, 149-163. – 1998.
HW Lenstra, JR. Elliptikus görbék és számelméleti algoritmusok (angol) // Proceedings of the International Congress of Mathematicians. - 1986. Archiválva : 2017. március 29.
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. Egy 768 bites RSA modulus faktorizálása // Cryptology ePrint Archívum, Jelentés 2010/006. – 2010.

Linkek

- Elliptikus görbe faktorizáció , egy Java kisalkalmazás -megvalósítás , amely egyesíti az ECM -et és egy öninicializáló kvadratikus szita módszert (ez utóbbit akkor választjuk, ha egy adott esetben gyorsabb).
GMP-ECM , az ECM hatékony megvalósítása.
ECMNet , egy egyszerű szerver-kliens megvalósítás.
pyecm , az ECM Python 2 megvalósítása.

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus