Factorizarea cu curbe eliptice

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 14 octombrie 2016; verificările necesită 57 de modificări .

Factorizarea folosind curbe eliptice ( metoda de factorizare a curbei elliptice în engleză , prescurtare ECM ) sau metoda lui Lenstra de factorizare folosind curbe eliptice ( în engleză Lenstra elliptic curve factorization ) este un algoritm pentru factorizarea unui număr natural folosind curbe eliptice . Acest algoritm are complexitate subexponențială [1] . ECM este a treia cea mai rapidă rulare [2] după metoda sită de câmp cu număr general și metoda sită pătratică .

În practică, este cel mai potrivit pentru a găsi divizori primi mici ai unui număr și, prin urmare, este considerat un algoritm [3] foarte specializat.

Este cel mai bun algoritm [4] pentru găsirea divizorilor primi cu lungimea de 20-25 de caractere (dimensiune 64…83 de biți), deoarece complexitatea sa depinde în principal de cel mai mic divizor prim p, și nu de numărul factorizat.

Adesea folosit pentru a identifica (renunța) divizorii primi mici ai unui număr. Dacă numărul obținut după operarea algoritmului este încă compus, atunci factorii rămași sunt numere mari, iar pentru extinderea ulterioară este logic să folosiți algoritmi de factorizare mai generali.

Cel mai mare divizor găsit folosind acest algoritm are 83 de caractere și a fost găsit de Ryan Propper pe 7 septembrie 2013 [5] .

Algoritm

Algoritm de factorizare (găsirea unui divizor non-trivial) al unui număr natural [6] : $n$

Se alege o curbă eliptică aleatorie peste , cu o ecuație de forma : , iar pe această curbă se alege un punct netrivial . Acest lucru se poate face astfel: $E$ $\mathbb {Z} _{n}$ $E$ $y^{2}=x^{3}+ax+b{\pmod {n))$ $P(x_{0},y_{0})$
1. Numerele sunt selectate aleatoriu . $x_{0},y_{0},a$ $\în$ $\mathbb {Z} _{n}$
2. Calculat . $b=y_{0}^{2}-x_{0}^{3}-ax_{0}{\pmod {n))$
Se alege un număr întreg care este produsul unui număr mare de numere mici. De exemplu, după cum puteți alege: $e$ $e$
- Factorial al unui număr mic . $B!$ $B$
- Produsul mai multor numere prime mici la puteri mici. Adică, sunt alese numere prime (care nu depășesc un anumit număr ) și grade astfel încât rezultatul ridicării la puterea corespunzătoare să nu depășească un anumit număr : $l_{i}$ $B$ ${\alpha _{i)}$ $l_{i}$ $l_{i}^{\alpha _{i)}$ $C$
$e=\prod _{\ell \leq B}\ell ^{\alpha _{i)),$ unde este cel mai mare dintre indicatorii posibili, la care . $\alpha _{i}=\left\lfloor \log _{\ell }C\right\rfloor$ $\ell ^{\alpha _{i}}\leq C$
Produsul pe curba eliptică se calculează : $eP$ $E$ $eP=\underbrace {P\boxplus \dots \boxplus P} _{e)$ , unde este operația de adăugare definită de legea grupului . $\box plus$ Operația de adunare necesită găsirea pantei segmentului care leagă punctele însumate și, prin urmare, necesită operația de împărțire modulo n . Operația modulo se face folosind algoritmul Euclid extins . În special, împărțirea la un număr v (mod n ) implică găsirea mcd -ului ( v , n ) . În cazul mcd( v , n ) 1, mcd( v , n ) n , -adunarea nu va da niciun punct semnificativ pe curba eliptică, ceea ce implică faptul că mcd( v , n ) este un divizor non-trivial al lui n . Pe baza acestui fapt, în procesul de calcul sunt posibile următoarele cazuri: $\neq$ $\neq$ $\box plus$ $eP$
- Dacă nu au fost întâlnite elemente ireversibile (mod n ) în timpul calculului , atunci este necesar să alegeți o altă curbă eliptică și un punct și să repetați algoritmul de la început. $E$ $P(x_{0},y_{0})$
- Dacă la un moment dat , unde ( ), atunci trebuie să alegeți o altă curbă eliptică și un punct și să repetați algoritmul de la început, deoarece punctul va rămâne neschimbat după operațiuni suplimentare de adăugare. $e'P=\underbrace {P\boxplus \dots \boxplus P} _{e'}=\infty$ $e'\leq e$ $E$ $P(x_{0},y_{0})$ $\infty$
- Dacă la o anumită etapă de calcul mcd( v , n ) 1 și mcd( v , n ) n , atunci mcd( v , n ) este divizorul netrivial necesar al lui n . $\neq$ $\neq$

Motivație

Ecuația luată modulo numărul n definește o curbă eliptică . Dacă numerele p și q sunt doi divizori primi ai numărului n , atunci ecuația de mai sus va fi adevărată și atunci când este luată modulo p sau modulo q . Adică : și : definesc, respectiv, două curbe eliptice (mai mici decât ). Cu toate acestea, chiar și cu o operație de adunare dată , nu numai curbe eliptice sunt, ci și grupuri . Fie ca acestea să conțină N p și , respectiv, N q elemente, atunci dacă: $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$ - orice punct al curbei inițiale
$k_i$ sunt numere pozitive astfel încât: $k_{i}P=\infty$ $E_1$
$k$ este minimul de $k_i$

Apoi, după teorema lui Lagrange este adevărat că

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

O afirmație similară este valabilă și pentru o curbă modulo q .

Ordinea unui grup de puncte situate pe o curbă eliptică peste Z p este mărginită de teorema lui Hasse : p + 1 − 2 √ p p + 1 + 2 √ p $|E|$ $\leq |E|\leq$

Pentru o curbă eliptică aleasă aleatoriu, ordinele N p și N q sunt numere aleatoare mărginite de teorema lui Hasse (vezi mai jos). Este puțin probabil ca majoritatea divizorilor primi ai lui N p și N q să fie aceiași și este probabil ca atunci când se calculează eP , să se întâlnească unele modulo p , dar nu mod q , sau invers. Dacă acesta este cazul, atunci kP nu există pe curba inițială, iar în calcule s-a găsit un v astfel încât fie gcd( v , p ) = p fie gcd( v , q ) = q , dar nu ambele. Atunci mcd( v , n ) este un divizor netrivial al lui n . $kP=\infty$

ECM este o rafinare a metodei mai vechi P-1 de către Pollard [7] . Algoritmul p − 1 găsește divizori primi ai lui p astfel încât ( p − 1) este B-neted pentru un B mic . Pentru orice e care este un multiplu al lui ( p − 1) și pentru orice a care este relativ prim pentru p , teorema lui Fermat susține că a e ≡ 1 (mod p ) . Atunci mcd ( a e − 1, n ) va fi un divizor al lui n cu probabilitate mare . Totuși, algoritmul p − 1 va eșua [7] când p are divizori primi mari. ECM funcționează corect în acest caz, deoarece în loc să luăm în considerare grupul multiplicativ peste Z p , a cărui ordine este întotdeauna p − 1 , considerăm grupul unei curbe eliptice aleatoare peste un câmp finit Z p .

Ordinea unui grup de puncte situate pe o curbă eliptică peste Z p este mărginită de teorema lui Hasse : p + 1 − 2 √ p p + 1 + 2 √ p . Pare important să investigăm [8] probabilitatea ca un număr neted să se afle în acest interval (în acest caz, există curbe a căror ordine este un număr neted). Nu există dovezi că există întotdeauna un număr neted în intervalul Hasse, dar folosind metode probabilistice euristice , teorema Canfield –Erdős–Pomerance [ 9] și notația L , obținem o estimare că este suficient să luăm L [ √ 2 /2, √ 2 ] până când se obține o ordine de grup netedă. Această estimare euristică este bine aplicabilă în practică. $|E|$ $\leq |E|\leq$

Exemplu

Factorizarea [10] a numărului n = 455839.

Sunt selectate o curbă eliptică și un punct situat pe această curbă

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

10 sunt calculate succesiv! P :

1. Coordonatele punctului sunt calculate . $P_{2}=2!P=2P$

Tangenta pantei tangentei în punctul P este:

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

Coordonatele punctului : $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)).

Se poate demonstra că punctul 2P se află într-adevăr pe curbă:

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

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

Tangenta pantei tangentei în punctul 2 P este

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

. Pentru a calcula 593 / 106 modulo n , puteți folosi algoritmul Euclid extins : 455839 = 4300 106 + 39, apoi 106 = 2 39 + 28, apoi 39 = 28 + 11, apoi 28 = 2 11 + 6, apoi 6 + 5, apoi 6 = 5 + 1. Prin urmare, GCD(455839, 106) = 1 și invers: 1 = 6 - 5 = 2 6 - 11 = 2 28 - 5 11 = 7 28 - 5 39 = 7 106 - 19 39 = 81707 106 - 19 455839. De unde 1/106 = 81707 (mod 455839), deci −593 / 106 = 322522 (mod 455839).

Ținând cont de s calculat , se calculează coordonatele punctului 2(2 P ), la fel cum s-a făcut mai sus: 4 P = (259851, 116255). Se poate demonstra că punctul se află într-adevăr pe curba noastră eliptică.
Însumând 4 P și 2 P se găsește . $P_{3}=(179685,-28708)$

3. În mod similar, puteți calcula , , și așa mai departe. În momentul calculării 640 P , puteți observa că este necesar calculul elementului invers la 599 (mod 455839). Deoarece 455839 este divizibil cu 599, se găsește descompunerea necesară: 455839 = 599 761. $P_{4}=4!P$ $P_{5}=5!P$

Complexitate computațională

Fie cel mai mic divizor al lui n p . Atunci numărul de operații aritmetice efectuate poate fi estimat cu valoarea [11] : (sau în notația L ). Dacă înlocuim p cu , atunci obținem o estimare a complexității subexponențiale: . $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]$

Dacă comparăm metoda curbelor eliptice cu alte metode de factorizare, atunci această metodă aparține clasei metodelor de factorizare subexponențială [1] și, prin urmare, funcționează mai rapid decât orice metodă exponențială. În comparație cu metoda sită pătratică (QS) și metoda sită câmp numeric (NFS) , totul depinde de mărimea celui mai mic divizor al lui n [12] . Dacă numărul n este ales, ca în RSA , ca produs a două numere prime de aproximativ aceeași lungime, atunci metoda curbei eliptice are aceeași estimare ca metoda sită pătratică, dar este inferioară metodei sită câmp numeric [13]. ] .

Algoritm cu coordonate proiective

Înainte de a considera planul proiectiv peste , merită să luăm în considerare planul proiectiv obișnuit peste ℝ: în loc de puncte, luăm în considerare drepte care trec prin 0. O dreaptă poate fi definită folosind un punct diferit de zero astfel: pentru orice punct al acestei drepte ⇔ ∃ c ≠ 0, astfel încât x' = c x , y' = c y și z' = c z . Conform acestei relaţii de echivalenţă spaţiul se numeşte plan proiectiv . Punctele planului , corespund dreptelor spațiului tridimensional care trec prin 0. Rețineți că punctul nu există în acest spațiu, deoarece nu definește o dreaptă care trece prin 0. Algoritmul lui Lenstra nu necesită utilizarea câmpului ℝ , câmpul finit oferă și structura grupului peste curba eliptică . Totuși, aceeași curbă, dar cu operații pe , nu formează un grup dacă nu este un număr prim. Metoda factorizării folosind curbe eliptice folosește trăsăturile legii adunării în cazurile în care nu este simplă. $\mathbb {Z} _{n}$ $(x,y,z)$ $(x',y',z')$ $(P^{2})$ $(x:y:z)$ $(0:0:0)$ $\mathbb {Z} _{n}$ $n$ $n$

Algoritm de factorizare în coordonate proiective [14] :. Elementul neutru în acest caz este dat de punctul de la infinit . Fie n un număr întreg și pozitiv, o curbă eliptică . $(0:1:0)$ $E(Z_{n})=\{(x:y:z)\in P^{2}\ |\ y^{2}z=x^{3}+axz^{2}+bz ^{3}\}$

Selectat ( a ≠ 0). $x_{P},y_{P},a$ $\în$ $\mathbb {Z} _{n}$
Calculat . Curba eliptică E este dată ca (forma Weierstrass). Folosind coordonatele proiective, o curbă eliptică poate fi scrisă ca o ecuație omogenă . se află pe această curbă. ${\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)$
Limita superioară este selectată . Notă: pot exista factori numai dacă ordinea grupului E peste este un număr B-neted . Aceasta înseamnă că toți factorii primi E peste trebuie să fie mai mici sau egali cu B . $B\in \mathbb {Z}$ $\mathbb {Z} _{p}$ $\mathbb {Z} _{p}$
Se calculează NOC . $k=$ $(1,\dots, B)$
Calculat în inel . Este important de reținut că dacă | | - B-smooth , iar n este simplu (în acest caz , un câmp), atunci . Cu toate acestea, dacă | | - B-neted pentru un număr p care este un divizor al lui n , rezultatul poate să nu fie (0:1:0) deoarece adunarea și înmulțirea pot să nu funcționeze la fel de bine dacă n nu este un număr prim. Astfel este posibil să găsim un divizor non-trivial al lui n . $\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})$
Dacă divizorul nu a fost găsit, atunci algoritmul se repetă de la pasul 2.

La punctul 5, calculul poate să nu fie posibil, deoarece adăugarea a două puncte peste o curbă eliptică necesită calculul lui , ceea ce nu este întotdeauna posibil dacă n nu este un număr prim. Este posibil să se calculeze suma a două puncte în felul următor, care nu necesită primătatea lui n (nu necesită ca acesta să fie un câmp): $kP$ $(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})$ , coordonatele sunt simplificate în continuare cât mai mult posibil (un divizor netrivial n este găsit dacă apare o eroare în timpul simplificării).

Folosind curbele Edwards

Utilizarea curbelor Edwards permite [15] reducerea numărului de operații modulare și reducerea timpului de execuție a algoritmului în comparație cu curbele eliptice în forma Weierstrass ( ) și în forma Montgomery ( ). $y^{2}=x^{3}+ax+b{\pmod {p}}$ $By^{2}=x^{3}+Ax^{2}+x$

Definiție: Fie un câmp a cărui caracteristică nu este un număr și fie . Apoi curba Edwards este definită ca. Există cinci moduri de a construi un set de puncte pe o curbă Edwards: un set de puncte afine , un set de puncte proiective , un set de puncte inversate , un set de puncte extinse și un set de puncte. puncte completate . puncte ). De exemplu, setul de puncte afine este dat ca: . $k$ $2$ $d\in k\setminus \{0,1\}$ $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}\}$

Operația de adunare: Legea adunării este dată de formula . $(e,f),(g,h)\mapsto \left({\frac {eh+fg}{1+degfh}),{\frac {fh-eg}{1-degfh}}\right )$

Punctul (0,1) este elementul neutru, iar inversul punctului este . $(e,f)$ $(-e,f)$

Alte forme sunt obținute într-un mod similar cu modul în care se obține o curbă Weierstrass proiectivă dintr-o curbă afină.

Exemplu de adunare: Puteți demonstra legea adunării folosind un exemplu de curbă eliptică în forma Edwards cu d =2: , și puncte pe ea. Se propune să se verifice dacă suma lui P 1 cu elementul neutru (0,1) este egală cu P 1 . Într-adevăr: ${\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

Fiecare curbă eliptică în forma Edwards are un punct de ordin 4. Prin urmare, grupul periodic al unei curbe Edwards peste este izomorf la sau . $\mathbb {Q}$ $\mathbb {Z} _{4},\mathbb {Z} _{8},\mathbb {Z} _{12},\mathbb {Z} _{2}\times \mathbb {Z} _ {patru}$ $\mathbb {Z} _{2}\times \mathbb {Z} _{8)$

Pentru factorizarea folosind algoritmul Lenstra, cele mai interesante cazuri [16] sunt și . $\mathbb {Z} _{12}$ $\mathbb {Z} _{2}\times \mathbb {Z} _{8)$

Un exemplu de curbă care conține un grup periodic izomorf la : $\mathbb {Z} _{12}$

$x^{2}+y^{2}=1+dx^{2}y^{2}$ cu un punct situat pe cercul unitar centrat în punctul (0,-1). $(a,b)$

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

Vezi și

Note

↑ 1 2 Bressoud, 2000 , p. 331.
↑ Parker, 2014 .
↑ Bressoud, 2000 .
↑ Brent, 1998 .
↑ 50 cei mai mari divizori găsiți de ECM . Data accesului: 27 noiembrie 2016. Arhivat din original pe 20 februarie 2009. (nedefinit)
↑ Lenstra, 1987 , p. 16-20.
↑ 12 Lenstra , 1987 .
↑ Lenstra, Number-Theoretic Algorithms, 1986 , p. 16.
↑ Canfield, 1983 .
↑ Introducere în Criptografie cu Teoria Codării, 2006 .
↑ Vasilenko, 2006 , p. 109.
↑ Lenstra, Number-Theoretic Algorithms, 1986 , p. 331.
↑ Brent, 1998 , p. 12.
↑ Vasilenko, 2006 , p. 112.
↑ ECM folosind curbele Edwards, 2013 , p. 2-3.
↑ ECM folosind curbele Edwards, 2013 , p. 19.

Literatură

Koblitz NA Curs de teoria numerelor și criptografie (neopr.) . — Springer-Verlag , 1987.
Lenstra AK, Lenstra HW, Lovász L. Factorizarea polinoamelor cu coeficienți raționali (neopr.) // Math. Ann. . - 1982. - T. 261 .
Lenstra Jr., HW Factorizarea numerelor întregi cu curbe eliptice (engleză) // Annals of Mathematics : journal. - 1987. - Vol. 126 , nr. 2 . - P. 649-673 .
Trappe, W., Washington, LC Introducere în Criptografie cu Teoria Codării . - Al doilea. - Pearson Prentice Hall , 2006. - ISBN 0-13-186239-1 .
Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters. ECM folosind curbele Edwards // Matematica calculului : jurnal. - 2013. - Vol. 82 . - P. 1139-1179 . - doi : 10.1090/S0025-5718-2012-02633-0 .
Ishmukhametov Sh. T. Metode de factorizare pentru numere naturale . - Kazan: Kazan. un.. - 2011. - 190 p.
David Bressoud și Stan Wagon. Un curs de teoria numerelor computaționale. - Editura Key College / Springer, 2000. - S. 168-169. — 366 p. - ISBN 978-1-930190-10-8 .
Steven Galbraith. Matematica Criptografiei cu cheie publică. - Cambridge University Press, 2012. - P. 330-332. — 630 p. — ISBN 9781139012843 .
O. N. Vasilenko. Algoritmi teoretici numerici în criptografie. — M.: MTsNMO, 2006. — 335 p. — ISBN 5-94057-103-4 .
W. Trappe și L. C. Washington. Introducere în Criptografie cu Teoria Codării. - Al doilea. - Pearson Prentice Hall, 2006. - ISBN 0-13-186239-1 .
Parker D. Elliptic curves and Lenstra's factorization algorithm (engleză) // University of Chicago: REU 2014. - 2014.
ER Canfield , Paul Erdős , Carl Pomerance. Despre o problemă a lui Oppenheim cu privire la „Factorisatio Numerorum” (engleză) // Jurnal de teoria numerelor. - 1983. - Emisiune. 17 .
Richard P. Brent. Unii algoritmi de factorizare întregi folosind curbe eliptice // Australian Computer Science Communications 8, 149-163. — 1998.
HW Lenstra, JR. Curbe eliptice și algoritmi de teorie a numărului (engleză) // Proceedings of the International Congress of Mathematicians. - 1986. Arhivat la 29 martie 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 Timofeev, Paul Zimmermann. Factorizarea unui modul RSA de 768 de biți // Cryptology ePrint Archive, Raport 2010/006. — 2010.

Link -uri

- Factorizarea curbei eliptice , o implementare a appletului Java care combină ECM și o metodă de sită pătratică cu autoinițializare (aceasta din urmă este aleasă atunci când este mai rapidă pentru un anumit caz).
GMP-ECM , o implementare eficientă a ECM.
ECMNet , o implementare simplă server-client.
pyecm , o implementare Python 2 a ECM.

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin