Factorización con curvas elípticas

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 14 de octubre de 2016; las comprobaciones requieren 57 ediciones .

La factorización mediante curvas elípticas ( método de factorización de curvas elípticas en inglés , abreviado ECM ) o el método de factorización de Lenstra mediante curvas elípticas ( factorización de curvas elípticas en inglés Lenstra ) es un algoritmo para factorizar un número natural mediante curvas elípticas . Este algoritmo tiene una complejidad subexponencial [1] . ECM es el tercero de ejecución más rápida [2] después del método de tamiz de campo numérico general y el método de tamiz cuadrático .

En la práctica, es más adecuado para encontrar pequeños divisores primos de un número y, por lo tanto, se considera un algoritmo altamente especializado [3] .

Es el mejor algoritmo [4] para encontrar divisores primos de 20-25 caracteres de longitud (tamaño 64…83 bits), porque su complejidad depende principalmente del divisor primo más pequeño p, y no del número factorizado.

A menudo se usa para identificar (descartar) pequeños divisores primos de un número. Si el número obtenido después de la operación del algoritmo sigue siendo compuesto, entonces los factores restantes son números grandes, y para una mayor expansión tiene sentido usar algoritmos de factorización más generales.

El divisor más grande encontrado usando este algoritmo tiene 83 caracteres y fue encontrado por Ryan Propper el 7 de septiembre de 2013 [5] .

Algoritmo

Algoritmo de factorización (encontrar un divisor no trivial) de un número natural [6] : $norte$

Se elige una curva elíptica aleatoria sobre , con una ecuación de la forma : , y se elige un punto no trivial en esta curva . Esto se puede hacer así: $mi$ $\mathbb {Z} _{n}$ $mi$ $y^{2}=x^{3}+ax+b{\pmod {n))$ ${\ estilo de visualización P (x_ {0}, y_ {0})}$
1. Los números se seleccionan al azar . ${\ estilo de visualización x_ {0}, y_ {0}, a}$ $\en$ $\mathbb {Z} _{n}$
2. Calculado . $b=y_{0}^{2}-x_{0}^{3}-ax_{0}{\pmod {n))$
Se elige un número entero que sea el producto de una gran cantidad de números pequeños. Por ejemplo, como puedes elegir: $mi$ $mi$
- Factorial de algún número pequeño . ${\ estilo de visualización B!}$ $B$
- El producto de varios números primos pequeños a potencias pequeñas. Es decir, se eligen números primos (que no superen un número determinado ), y grados tales que el resultado de elevar a la potencia adecuada no supere un número determinado : $l_{yo}$ $B$ ${\ estilo de visualización {\ alfa _ {i}}}$ $l_{yo}$ $l_{i}^{\alpha _{i))$ $C$
$e=\prod_{\ell \leq B}\ell ^{\alpha_{i)),$ donde es el mayor de los posibles indicadores, en el que . $\alpha _{i}=\left\lfloor \log _{\ell }C\right\rfloor$ $\ell ^{\alpha _{i}}\leq C$
El producto de la curva elíptica se calcula : $EP$ $mi$ ${\displaystyle eP=\underbrace {P\boxplus \dots \boxplus P} _{e))$ , donde es la operación de suma definida por la ley de grupos . $\caja más$ La operación de suma requiere encontrar la pendiente del segmento que conecta los puntos sumados y, por lo tanto, requiere la operación de división módulo n . La operación de módulo se realiza utilizando el algoritmo de Euclides extendido . En particular, dividir por algún número v (mod n ) implica encontrar el mcd ( v , n ) . En el caso de mcd( v , n ) 1, mcd( v , n ) n , -la suma no dará ningún punto significativo en la curva elíptica, lo que implica que mcd( v , n ) es un divisor no trivial de n . En base a esto, los siguientes casos son posibles en el proceso de cálculo: $\neq$ $\neq$ $\caja más$ $EP$
- Si no se encontraron elementos irreversibles (mod n ) durante el cálculo , entonces es necesario elegir otra curva elíptica y punto y repetir el algoritmo desde el principio. $mi$ ${\ estilo de visualización P (x_ {0}, y_ {0})}$
- Si en algún momento , donde ( ), entonces debe elegir otra curva elíptica y punto y repetir el algoritmo desde el principio, porque el punto permanecerá sin cambios después de más operaciones de suma. $e'P=\underbrace {P\boxplus \dots \boxplus P} _{e'}=\infty$ $e'\leq e$ $mi$ ${\ estilo de visualización P (x_ {0}, y_ {0})}$ $\infty$
- Si en alguna etapa del cálculo mcd( v , n ) 1 y mcd( v , n ) n , entonces mcd( v , n ) es el divisor no trivial requerido de n . $\neq$ $\neq$

Justificación

La ecuación tomada módulo el número n define una curva elíptica . Si los números p y q son dos divisores primos del número n , entonces la ecuación anterior también será cierta cuando se tome módulo p o módulo q . Es decir, : y : definen, respectivamente, dos curvas elípticas (menor que ). Sin embargo, incluso con una operación de suma dada , no solo son curvas elípticas: también son grupos . Que contengan N p y N q elementos, respectivamente, entonces si: $y^{2}=x^{3}+ax+b$ $mi$ $E_1$ $y^{2}=x^{3}+ax+b{\pmod {p}}$ $E_2$ $y^{2}=x^{3}+ax+b{\pmod {q))$ $mi$ $E_1$ $E_2$ $\caja más$

$PAGS$ - cualquier punto de la curva original
$k_i$ son números positivos tales que: $k_{i}P=\infty$ $E_1$
$k$ es el minimo de $k_i$

Entonces por el teorema de Lagrange es cierto que

$k$ - divisor $Notario público$
$N_{p}P=\infty$

Una afirmación similar también es válida para una curva módulo q .

El orden de un grupo de puntos que se encuentran en una curva elíptica sobre Z p está acotado por el teorema de Hasse : p + 1 − 2 √ p p + 1 + 2 √ p $|E|$ ${\ estilo de visualización \ leq |E|\ leq}$

Para una curva elíptica elegida al azar, los órdenes N p y N q son números aleatorios acotados por el teorema de Hasse (ver más abajo). Es poco probable que la mayoría de los divisores primos de N p y N q sean iguales, y es probable que cuando se calcule eP , se encontrará algún módulo p pero no mod q , o viceversa. Si este es el caso, entonces kP no existe en la curva original, y en los cálculos se encontró una v tal que gcd( v , p ) = p o gcd( v , q ) = q , pero no ambas. Entonces mcd( v , n ) es un divisor no trivial de n . $kP=\infty$

ECM es un refinamiento del antiguo método P-1 de Pollard [7] . El algoritmo p − 1 encuentra divisores primos de p tales que ( p − 1) es B-suave para alguna B pequeña . Para cualquier e que sea un múltiplo de ( p − 1 ) , y para cualquier a que sea relativamente primo de p , el teorema de Fermat sostiene que a e ≡ 1 (mod p ) . Entonces mcd ( a e − 1, n ) será un divisor de n con alta probabilidad . Sin embargo, el algoritmo p − 1 fallará [7] cuando p tenga grandes divisores primos. ECM funciona correctamente en este caso, porque en lugar de considerar el grupo multiplicativo sobre Z p , cuyo orden es siempre p − 1 , consideramos el grupo de una curva elíptica aleatoria sobre un campo finito Z p .

El orden de un grupo de puntos que se encuentran en una curva elíptica sobre Z p está acotado por el teorema de Hasse : p + 1 − 2 √ p p + 1 + 2 √ p . Parece importante investigar [8] la probabilidad de que algún número suave se encuentre en este intervalo (en este caso, hay curvas cuyo orden es un número suave). No hay evidencia de que siempre haya algún número suave en el intervalo de Hasse, pero usando métodos probabilísticos heurísticos , el teorema de Canfield -Erdős-Pomerance [ 9] y la notación L , obtenemos una estimación de que es suficiente tomar L [ √ 2 /2, √ 2 ] se curva hasta obtener un orden de grupo suave. Esta estimación heurística es bien aplicable en la práctica. $|E|$ ${\ estilo de visualización \ leq |E|\ leq}$

Ejemplo

Factorización [10] del número n = 455839.

Se selecciona una curva elíptica y un punto que se encuentra en esta curva

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

¡10 se calculan secuencialmente! pag :

1. Se calculan las coordenadas del punto . $P_{2}=2!P=2P$

La tangente de la pendiente de la tangente en el punto P es:

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

Coordenadas del punto : $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 puede demostrar que el punto 2P realmente se encuentra en la curva:

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

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

La tangente de la pendiente de la tangente en el punto 2 P es

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

. Para calcular 593/106 módulo n , puede usar el algoritmo de Euclides extendido : 455839 = 4300 106 + 39, luego 106 = 2 39 + 28, luego 39 = 28 + 11, luego 28 = 2 11 + 6, luego 11 = 6 + 5, luego 6 = 5 + 1. Por lo tanto, MCD(455839, 106) = 1, y viceversa: 1 = 6 - 5 = 2 6 - 11 = 2 28 - 5 11 = 7 28 - 5 39 = 7 106 - 19 39 = 81707 106 - 19 455839. De donde 1/106 = 81707 (mod 455839), por lo tanto −593 / 106 = 322522 (mod 455839).

Teniendo en cuenta el s calculado , se calculan las coordenadas del punto 2(2 P ), tal como se hizo anteriormente: 4 P = (259851, 116255). Se puede demostrar que el punto realmente se encuentra en nuestra curva elíptica.
Sumando 4 P y 2 P se encuentra . $P_{3}=(179685,-28708)$

3. Del mismo modo, puede calcular , , etc. Al momento de calcular 640 P , se puede notar que se requiere el cálculo del elemento inverso a 599 (mod 455839). Como 455839 es divisible por 599, se encuentra la descomposición requerida: 455839 = 599 761. $P_{4}=4!P$ $P_{5}=5!P$

Complejidad computacional

Sea p el divisor más pequeño de n . Luego, el número de operaciones aritméticas realizadas se puede estimar por el valor [11] : (o en notación L ). Si reemplazamos p por , entonces obtenemos una estimación de complejidad subexponencial: . $e^{\sqrt {(2+o(1))\ln p\ln(\ln p)))\ln ^{2}n$ $L_{p}[1/2;{\sqrt {2}}]$ ${\ estilo de visualización n^{1/2}}$ ${\ estilo de visualización L_ {n} [1/2; 1]}$

Si comparamos el método de las curvas elípticas con otros métodos de factorización, entonces este método pertenece a la clase de métodos de factorización subexponenciales [1] y, por lo tanto, funciona más rápido que cualquier método exponencial. Cuando se compara con el método de tamiz cuadrático (QS) y el método de tamiz de campo numérico (NFS) , todo depende del tamaño del divisor más pequeño de n [12] . Si se elige el número n , como en RSA , como un producto de dos números primos de aproximadamente la misma longitud, entonces el método de la curva elíptica tiene la misma estimación que el método de tamiz cuadrático, pero es inferior al método de tamiz de campo numérico [13 ] .

Algoritmo con coordenadas proyectivas

Antes de considerar el plano proyectivo sobre , vale la pena considerar el plano proyectivo habitual sobre ℝ: en lugar de puntos, consideramos líneas que pasan por 0. Una línea se puede definir usando un punto distinto de cero de la siguiente manera: para cualquier punto de esta línea ⇔ ∃ c ≠ 0, tal que x' = c x , y' = c y y z' = c z . De acuerdo con esta relación de equivalencia , el espacio se denomina plano proyectivo . Los puntos del plano corresponden a líneas del espacio tridimensional que pasan por 0. Nótese que el punto no existe en este espacio, ya que no define una línea que pasa por 0. El algoritmo de Lenstra no requiere el uso del campo ℝ , el campo finito también proporciona la estructura del grupo sobre la curva elíptica . Sin embargo, la misma curva, pero con operaciones sobre , no forma grupo si no es un número primo. El método de factorización mediante curvas elípticas utiliza las características de la ley de la suma en los casos en que no es simple. $\mathbb {Z} _{n}$ $(x, y, z)$ ${\ estilo de visualización (x', y', z')}$ ${\ estilo de visualización (P^{2})}$ ${\ estilo de visualización (x: y: z)}$ ${\ estilo de visualización (0:0:0)}$ $\mathbb {Z} _{n}$ $norte$ $norte$

Algoritmo de factorización en coordenadas proyectivas [14] :. El elemento neutro en este caso viene dado por el punto en el infinito . Sea n un número entero y positivo, una curva elíptica . ${\ estilo de visualización (0: 1: 0)}$ $E(Z_{n})=\{(x:y:z)\in P^{2}\ |\ y^{2}z=x^{3}+axz^{2}+bz ^{3}\}$

Seleccionado ( a ≠ 0). $x_{P},y_{P},a$ $\en$ $\mathbb {Z} _{n}$
Calculado . La curva elíptica E se da como (forma de Weierstrass). Usando coordenadas proyectivas, una curva elíptica se puede escribir como una ecuación homogénea . se encuentra en esta curva. ${\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)$
Se selecciona el límite superior . Nota: puede haber factores solo si el orden del grupo E sobre es un número B-liso . Esto significa que todos los factores primos sobre E deben ser menores o iguales que B. $B\en \mathbb {Z}$ $\mathbb {Z} _{p}$ $\mathbb {Z} _{p}$
Se calcula el NOC . $k=$ ${\ estilo de visualización (1, \ puntos, B)}$
Calculado en el ring . Es importante tener en cuenta que si | | - B-suave , y n es simple (en este caso , un campo), entonces . Sin embargo, si | | - B-suave para algún número p que es un divisor de n , el resultado puede no ser (0:1:0) porque la suma y la multiplicación pueden no funcionar tan bien si n no es un número primo. Por lo tanto, es posible encontrar un divisor no trivial de n . $\underbrace {P+P+\dots +P} _{k}$ ${\ estilo de visualización E (\ mathbb {Z} _ {n})}$ ${\ estilo de visualización E (\ mathbb {Z} _ {n})}$ $\mathbb {Z} _{n}$ $kP=(0:1:0)$ ${\ estilo de visualización E (\ mathbb {Z} _ {p})}$
Si no se encuentra el divisor, se repite el algoritmo desde el paso 2.

En el punto 5, el cálculo puede no ser posible, ya que sumar dos puntos sobre una curva elíptica requiere el cálculo de , que no siempre es posible si n no es un número primo. Es posible calcular la suma de dos puntos de la siguiente manera, que no requiere la primacía de n (no requiere que sea un campo): ${\ Displaystyle kP}$ ${\ estilo de visualización (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})$ , las coordenadas se simplifican aún más tanto como sea posible (se encuentra un divisor no trivial n si se produce un error durante la simplificación).

Usando las curvas de Edwards

El uso de curvas de Edwards permite [15] reducir el número de operaciones modulares y reducir el tiempo de ejecución del algoritmo en comparación con las curvas elípticas en forma de Weierstrass ( ) y en forma de Montgomery ( ). $y^{2}=x^{3}+ax+b{\pmod {p}}$ $Por^{2}=x^{3}+Ax^{2}+x$

Definición: Sea un campo cuya característica no sea un número , y sea . Entonces, la curva de Edwards se define como Hay cinco formas de construir un conjunto de puntos en una curva de Edwards: un conjunto de puntos afines , un conjunto de puntos proyectivos , un conjunto de puntos invertidos , un conjunto de puntos extendidos y un conjunto de puntos completados . puntos ). Por ejemplo, el conjunto de puntos afines se da como: . $k$ $2$ ${\displaystyle d\in k\setminus \{0,1\))$ ${\ Displaystyle E_ {E, d))$ $x^{2}+y^{2}=1+dx^{2}y^{2}.$ $\{(x,y)\en A^{2}:x^{2}+y^{2}=1+dx^{2}y^{2}\}$

Operación de suma: La ley de la suma viene dada por la fórmula . $(e,f),(g,h)\mapsto \left({\frac {eh+fg}{1+degfh)),{\frac {fh-eg}{1-degfh))\right )$

El punto (0,1) es el elemento neutro, y el inverso del punto es . ${\ estilo de visualización (e, f)}$ ${\ estilo de visualización (-e, f)}$

Otras formas se obtienen de forma similar a como se obtiene una curva proyectiva de Weierstrass a partir de una curva afín.

Ejemplo de suma: puede demostrar la ley de la suma usando un ejemplo de una curva elíptica en forma de Edwards con d = 2: y puntos en ella. Se propone comprobar que la suma de P 1 con el elemento neutro (0,1) es igual a P 1 . En realidad: ${\displaystyle }x^{2}+y^{2}=1+2x^{2}y^{2}$ ${\ estilo de visualización 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

Cada curva elíptica en la forma de Edwards tiene un punto de orden 4. Por lo tanto, el grupo periódico de una curva de Edwards es isomorfo a o . ${\ estilo de visualización \ mathbb {Q}}$ $\mathbb {Z}_{4},\mathbb {Z}_{8},\mathbb {Z}_{12},\mathbb {Z}_{2}\times \mathbb {Z} _ {cuatro}$ ${\ estilo de visualización \ mathbb {Z} _ {2} \ veces \ mathbb {Z} _ {8}}$

Para la factorización usando el algoritmo de Lenstra, los casos más interesantes [16] son y . ${\ estilo de visualización \ mathbb {Z} _ {12}}$ ${\ estilo de visualización \ mathbb {Z} _ {2} \ veces \ mathbb {Z} _ {8}}$

Un ejemplo de una curva que contiene un grupo periódico isomorfo a : ${\ estilo de visualización \ mathbb {Z} _ {12}}$

${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2))$ con un punto situado en el círculo unitario con centro en el punto (0,-1). ${\ estilo de visualización (a, b)}$

$b\in (-2,0)\setminus \{-1,-1/2\},a^{2}=-(b^{2}+2b)$ y $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}}$ y $d={\frac {(u^{2}+1)^{3}(u^{2}-4u+1)}{(u-1)^{6}(u+1)^ {2}}},u\no en \{0,\pm 1\}.$

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

Véase también

Notas

↑ 1 2 Bressoud, 2000 , p. 331.
↑ Parker, 2014 .
↑ Bressoud, 2000 .
↑ Brent, 1998 .
↑ 50 divisores más grandes encontrados por ECM . Fecha de acceso: 27 de noviembre de 2016. Archivado desde el original el 20 de febrero de 2009. (indefinido)
↑ Lenstra, 1987 , pág. 16-20.
↑ 12 Lenstra , 1987 .
↑ Lenstra, Algoritmos teóricos de números, 1986 , p. dieciséis.
↑ Canfield, 1983 .
↑ Introducción a la criptografía con teoría de la codificación, 2006 .
↑ Vasilenko, 2006 , pág. 109.
↑ Lenstra, Algoritmos teóricos de números, 1986 , p. 331.
↑ Brent, 1998 , pág. 12
↑ Vasilenko, 2006 , pág. 112.
↑ ECM usando curvas de Edwards, 2013 , p. 2-3.
↑ ECM usando curvas de Edwards, 2013 , p. 19

Literatura

Koblitz NA Curso de teoría de números y criptografía (neopr.) . — Springer-Verlag , 1987.
Lenstra AK, Lenstra HW, Lovász L. Factorización de polinomios con coeficientes racionales (neopr.) // Math. Ana. . - 1982. - T. 261 .
Lenstra Jr., HW Factorización de enteros con curvas elípticas (inglés) // Annals of Mathematics : revista. - 1987. - vol. 126 , núm. 2 . - Pág. 649-673 .
Trappe, W., Washington, LC Introducción a la criptografía con la teoría de la codificación . - Segundo. - Pearson Prentice Hall , 2006. - ISBN 0-13-186239-1 .
Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters. ECM utilizando curvas de Edwards // Matemáticas de Computación : diario. - 2013. - Vol. 82 . - P. 1139-1179 . -doi : 10.1090/ S0025-5718-2012-02633-0 .
Ishmukhametov Sh. T. Métodos de factorización para números naturales . - Kazán: Kazán. un.. - 2011. - 190 p.
David Bressoud y Stan Wagon. Un curso de teoría computacional de números. - Key College Publishing / Springer, 2000. - S. 168-169. — 366 págs. - ISBN 978-1-930190-10-8 .
Steven Galbraith. Matemáticas de la criptografía de clave pública. - Cambridge University Press, 2012. - P. 330-332. — 630 págs. — ISBN 9781139012843 .
O. N. Vasilenko. Algoritmos de teoría de números en criptografía. — M.: MTsNMO, 2006. — 335 p. — ISBN 5-94057-103-4 .
W. Trappe y L. C. Washington. Introducción a la Criptografía con Teoría de Codificación. - Segundo. - Pearson Prentice Hall, 2006. - ISBN 0-13-186239-1 .
Parker D. Curvas elípticas y algoritmo de factorización de Lenstra (inglés) // Universidad de Chicago: REU 2014. - 2014.
ER Canfield , Paul Erdös , Carl Pomerance. Sobre un problema de Oppenheim relativo a "Factorisatio Numerorum" (inglés) // Revista de teoría de números. - 1983. - Edición. 17 _
Richard P.Brent. Algunos algoritmos de factorización de enteros que utilizan curvas elípticas // Australian Computer Science Communications 8, 149-163. — 1998.
HW Lenstra, JR. Curvas elípticas y algoritmos teóricos de números (inglés) // Actas del Congreso Internacional de Matemáticos. - 1986. Archivado el 29 de marzo de 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. Factorización de un módulo RSA de 768 bits // Cryptology ePrint Archive, Informe 2010/006. — 2010.

Enlaces

- Factorización de curva elíptica , una implementación de subprograma de Java que combina ECM y un método de tamiz cuadrático de inicialización automática (este último se elige cuando es más rápido para un caso particular).
GMP-ECM , una implementación eficiente de ECM.
ECMNet , una implementación servidor-cliente simple.
pyecm , una implementación Python 2 de ECM.

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin