Algoritmo de Shuf

El algoritmo de Schuf es un algoritmo eficiente [1] para contar el número de puntos en una curva elíptica sobre un campo finito . El algoritmo tiene aplicaciones en criptografía elíptica , donde es importante conocer el número de puntos para juzgar la dificultad de resolver un problema de logaritmo discreto sobre un grupo de puntos en una curva elíptica.

El algoritmo fue publicado en 1985 por René Chouf y fue un gran avance teórico ya que fue el primer algoritmo de tiempo polinomial determinista para contar puntos en una curva elíptica . Antes del algoritmo de Schuf, los enfoques para contar puntos en curvas elípticas, como el algoritmo simple de pasos pequeños y grandes , eran en su mayor parte laboriosos y requerían un tiempo de ejecución exponencial.

Este artículo explica el enfoque de Schuf, centrándose en las ideas matemáticas detrás del algoritmo.

Introducción

Sea una curva elíptica definida sobre un campo finito , donde para primo y entero . Sobre un campo con característica , se puede dar (brevemente) una curva elíptica mediante la ecuación de Weierstrass $mi$ $\mathbb {F} _{q}$ $q=p^{n}$ $pags$ $n\geq 1$ ${\ estilo de visualización \ neq 2,3}$

y^{2}=x^{3}+Ax+B

con _ El conjunto de puntos definidos sobre consiste en soluciones que satisfacen la ecuación de la curva y el punto en el infinito . Si uno usa la ley de grupo sobre curvas elípticas en este conjunto, puede ver que este conjunto forma un grupo abeliano , en el que actúa como el elemento cero. Para contar puntos en una curva elíptica, calculamos la cardinalidad del conjunto . El enfoque de Schuf utiliza el teorema de la curva elíptica de Hasse , junto con el teorema del resto chino y los polinomios de división para calcular la cardinalidad . ${\ estilo de visualización A, B \ en \ mathbb {F} _ {q}}$ $\mathbb {F} _{q}$ ${\ estilo de visualización (a, b) \ en \ mathbb {F} _ {q}^{2}}$ $O$ ${\ estilo de visualización E (\ mathbb {F} _ {q})}$ $O$ ${\ estilo de visualización E (\ mathbb {F} _ {q})}$ ${\ estilo de visualización \ sostenido E (\ mathbb {F} _ {q})}$

Teorema de Hasse

El teorema de Hasse establece que si es una curva elíptica sobre un campo finito, entonces satisface la desigualdad ${\ Displaystyle E/\ mathbb {F} _ {q}}$ $\mathbb {F} _{q}$ ${\ estilo de visualización \ sostenido E (\ mathbb {F} _ {q})}$

\mid q+1-\sharp E(\mathbb {F} _{q})\mid \leq 2{\sqrt {q)).

Este fuerte resultado, obtenido por Hasse en 1934, simplifica nuestra tarea reduciéndola a un conjunto finito (aunque grande) de posibilidades. Si determinamos cómo y usamos este resultado, obtenemos que el cálculo del módulo de potencia , donde , es suficiente para calcular , y por lo tanto para obtener . Aunque no existe una forma eficiente de calcular directamente números generales, es posible calcular con bastante eficiencia un número primo pequeño . Elegimos como un conjunto de diferentes números primos, tal que . Si se da para todos , el teorema chino del resto le permite calcular . ${\ estilo de visualización \ sostenido E (\ mathbb {F} _ {q})}$ $t$ $q+1-\sharp E(\mathbb {F} _{q})$ $t$ $norte$ $N>4{\sqrt {q))$ $t$ ${\ estilo de visualización \ sostenido E (\ mathbb {F} _ {q})}$ $t{\pmod {N}}$ $norte$ $t{\pmod {l}}$ $yo$ $S=\{l_{1},l_{2},...,l_{r))\}$ $\prod l_{i}=N>4{\sqrt {q}}$ ${\ Displaystyle t {\ pmod {l_ {i}}}}$ ${\ estilo de visualización l_ {i} \ en S}$ $t{\pmod {N}}$

Para calcular primos , usamos la teoría del endomorfismo de Frobenius y los polinomios de división . Tenga en cuenta que considerar números primos no genera problemas, ya que siempre podemos elegir un número primo mayor para garantizar que el producto sea lo suficientemente grande. En cualquier caso, el algoritmo de Schuf se usa con mayor frecuencia para el caso , ya que existen algoritmos más eficientes, los llamados -ádicos, para campos con características pequeñas. $t{\pmod {l}}$ $l\neq p$ $\fi$ $l\neq p$ ${\ estilo de visualización q = p}$ $pags$

Endomorfismo de Frobenius

Dada una curva elíptica definida sobre , consideramos los puntos sobre sobre , la clausura algebraica del campo . Es decir, permitimos que los puntos tengan coordenadas en . El endomorfismo de Frobenius sobre extiende una curva elíptica con un mapeo . $mi$ $\mathbb {F} _{q}$ $mi$ ${\bar {\mathbb {F} }}_{q}$ $\mathbb {F} _{q}$ ${\bar {\mathbb {F} }}_{q}$ ${\bar {\mathbb {F} }}_{q}$ $\mathbb {F} _{q}$ ${\ estilo de visualización \ phi: (x, y) \ mapas a (x ^ {q}, y ^ {q})}$

Este mapa es idéntico y se puede extender por un punto hasta el infinito , lo que lo convierte en un morfismo de grupo sobre sí mismo. ${\ estilo de visualización E (\ mathbb {F} _ {q})}$ $O$ $E({\bar {\mathbb {F}_{q))})$

El endomorfismo de Frobenius satisface una ecuación cuadrática relacionada con la potencia por el siguiente teorema: ${\ estilo de visualización E (\ mathbb {F} _ {q})}$

Teorema: El endomorfismo de Frobenius dado por el mapeo satisface la ecuación característica $\fi$

\phi ^{2}-t\phi +q=0

, dónde

t=q+1-\sharp E(\mathbb {F} _{q})

Entonces, para todo lo que tenemos , donde + significa la suma de una curva elíptica, y y significa el producto escalar de un punto en y un punto en [2] . ${\ estilo de visualización P = (x, y) \ en E}$ ${\ estilo de visualización (x^{q^{2}},y^{q^{2}})+q(x,y)=t(x^{q},y^{q})}$ ${\ estilo de visualización q (x, y)}$ $t(x^{q},y^{q})$ $(x, y)$ $q$ ${\ estilo de visualización (x^{q},y^{q})}$ $t$

Puede intentar calcular estos puntos en forma simbólica y como funciones en el anillo de coordenadas en la curva y luego buscar un valor que satisfaga la ecuación. Sin embargo, los grados resultan ser muy grandes y este enfoque no tiene valor práctico. ${\ estilo de visualización (x^{q^{2}},y^{q^{2}})}$ ${\ estilo de visualización (x^{q},y^{q})}$ ${\ estilo de visualización q (x, y)}$ $\mathbb {F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B)$ $mi$ $t$

La idea de Schuf era realizar este tipo de cálculos, limitándose a los puntos de orden de varios números primos pequeños . Fijando un número primo impar, se procede a resolver el problema de determinar , definido como , para un primo dado . Si el punto está en el subgrupo -torsión de , entonces , donde es el único entero tal que y . Tenga en cuenta que y que para cualquier número entero tenemos . Por lo tanto, tiene el mismo orden que . Entonces para , que pertenece a , también tenemos si . En consecuencia, hemos reducido nuestro problema a resolver la ecuación $yo$ $yo$ $yo$ ${\ Displaystyle t_ {l}}$ $t{\pmod {l}}$ ${\ estilo de visualización l \ neq 2, p}$ $(x, y)$ $yo$ ${\displaystyle E[l]=\{P\in E({\bar {\mathbb {F} _{q))})\mid lP=O\))$ $qP={\bar {q}}P$ ${\ estilo de visualización {\ bar {q}}}$ $q\equiv {\bar {q}}{\pmod {l}}$ $\mid {\bar {q}}\mid <l/2$ ${\ estilo de visualización \ phi (O) = O}$ $r$ ${\ estilo de visualización r \ phi (P) = \ phi (rP)}$ ${\ estilo de visualización \ phi (P)}$ $PAGS$ $(x, y)$ ${\ estilo de visualización E [l]}$ $t(x^{q},y^{q})={\bar {t))(x^{q},y^{q})$ $t\equiv {\bar {t}}{\pmod {l}}$

(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)\equiv {\bar {t}}(x^{ q},y^{q}),

donde y se encuentran en el intervalo . ${\ estilo de visualización {\ bar {t}}}$ ${\ estilo de visualización {\ bar {q}}}$ ${\ estilo de visualización [- (l-1)/2, (l-1)/2]}$

Módulo de cálculos

El polinomio de división con índice l es un polinomio tal que sus raíces son exactamente lascoordenadas x de los puntos de orden l . Entonces la restricción del cálculoa los l -puntos de torsión significa el cálculo de estas expresiones como funciones del anillo de coordenadas E y del módulo del polinomio de l -ésima división. Es decir, trabajamos en. Esto significa, en particular, que el grado de X e Y definido porno excede de 1 con respecto a la variable y ycon respecto a la variable x . $(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)$ $\mathbb {F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi_{l})$ $(X(x,y),Y(x,y)):=(x^{q^{2}},y^{q^{2}})+{\bar {q}}( x,y)$ ${\ estilo de visualización (l^{2}-3)/2}$

El producto escalar se puede hacer con el método de duplicar y sumar , o con el polinomio de división th. El segundo enfoque da: ${\ estilo de visualización {\ barra {q}} (x, y)}$ ${\ estilo de visualización {\ bar {q}}}$

{\bar {q}}(x,y)=(x_{\bar {q}},y_{\bar {q}})=\left(x-{\frac {\psi _{{ \bar {q}}-1}\psi _({\bar {q}}+1}}{\psi _{\bar {q}}^{2}}},{\frac {\psi _{ 2{\bar {q}}}}{2\psi _{\bar {q}}^{4}}}\right)

donde es el polinomio de la n-ésima división. Tenga en cuenta que es una función solo de x , denotemos esta función por . $\psi_{{n}}$ $y_{\bar {q}}/y$ $\el impuesto)$

Debemos dividir el problema en dos casos: el caso en que , y el caso en que . $(x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)$ $(x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)$

Caso 1: $(x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)$

Usando la fórmula de suma para el grupo , obtenemos: ${\ estilo de visualización E (\ mathbb {F} _ {q})}$

X(x,y)=\left({\frac {y^{q^{2}}-y_{\bar {q}}}{x^{q^{2}}-x_{\ barra {q}}}}\derecha)^{2}-x^{q^{2}}-x_{\barra {q}}.

Tenga en cuenta que este cálculo es imposible si falla el supuesto de desigualdad.

Ahora podemos reducir la elección de la coordenada x para dos posibilidades, a saber, los casos positivo y negativo. Usando la coordenada y , determinamos cuál de los dos casos ocurre. ${\ estilo de visualización {\ bar {t}}}$

Primero mostramos que X es una función de x solamente . Considere . Como es par, reemplazando con , reescribimos la expresión como $(y^{q^{2}}-y_{\bar {q)))^{2}=y^{2}(y^{q^{2}-1}-y_{\bar {q}}/año)^{2}$ ${\ estilo de visualización q^{2}-1}$ ${\ estilo de visualización y^{2}}$ $x^{3}+Ax+B$

(x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x))

y tenemos

X(x)\equiv (x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}- \theta (x)){\bmod {\psi}}_{l}(x).

Ahora, si para , entonces la igualdad es cierta para $X\equiv x_{\bar {t}}^{q}{\bmod {\psi}}_{l}(x)$ ${\ estilo de visualización {\ bar {t}} \ en [0, (l-1)/2]}$ ${\ estilo de visualización {\ bar {t}}}$

\phi ^{2}(P)\mp {\bar {t))\phi (P)+{\bar {q))P=O

para todos los puntos de P l -torsión.

Como se mencionó anteriormente, usando Y y , ahora podemos determinar cuál de los dos valores ( o ) funciona. Da significado . El algoritmo de Schoof recuerda los valores en una variable para cada primo l considerado . $y_{\bar{t}}^{q}$ ${\ estilo de visualización {\ bar {t}}}$ ${\ estilo de visualización {\ bar {t}}}$ ${\ estilo de visualización - {\ bar {t}}}$ $t\equiv {\bar {t}}{\pmod {l}}$ ${\bar {t}}{\pmod{l}}$ $t_{l}$

Caso 2: $(x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)$

Supongamos que . Como l es un número primo impar, es imposible que , y por lo tanto . De la ecuación característica se sigue que , y por lo tanto que . Se sigue que q es un módulo cuadrado l . deja _ Calcular y comprobar si . Si es así, entonces es , dependiendo de la coordenada y. $(x^{q^{2}},y^{q^{2}})={\bar {q}}(x,y)$ ${\bar {q}}(x,y)=-{\bar {q}}(x,y)$ ${\ estilo de visualización {\ bar {t}} \ neq 0}$ ${\bar {t}}\fi(P)=2{\bar {q}}P$ ${\bar {t}}^{2}{\bar {q}}\equiv (2q)^{2}{\pmod {l}}$ $q\equiv w^{2}{\pmod {l))$ ${\ estilo de visualización w \ phi (x, y)}$ $\mathbb {F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi_{l})$ ${\bar {q}}(x,y)=w\phi (x,y)$ ${\ Displaystyle t_ {l}}$ ${\ estilo de visualización \ pm 2w {\ pmod {l}}}$

Si q no es cuadrado módulo l , o si la igualdad falla para alguna w y , nuestra suposición es incorrecta, entonces . La ecuación característica da . ${\ estilo de visualización -w}$ $(x^{q^{2}},y^{q^{2}})=+{\bar {q}}(x,y)$ $(x^{q^{2}},y^{q^{2}})=-{\bar {q}}(x,y)$ ${\ estilo de visualización t_ {l} = 0}$

Caso adicional ${\ estilo de visualización l = 2}$

Recuerde, nuestros acuerdos iniciales no consideran el caso . Ya que asumimos que q es impar, y, en particular, si y sólo si tiene un elemento de orden 2. Por la definición de suma en un grupo, cualquier elemento de orden 2 debe tener la forma . Por lo tanto, si y solo si el polinomio tiene una raíz en , si y solo si mcd . ${\ estilo de visualización l = 2}$ $q+1-t\equiv t{\pmod {2))$ $t_{2}\equiv 0{\pmod {2))$ ${\ estilo de visualización E (\ mathbb {F} _ {q})}$ ${\ estilo de visualización (x_ {0}, 0)}$ $t_{2}\equiv 0{\pmod {2))$ $x^{3}+Ax+B$ $\mathbb {F} _{q}$ $(x^{q}-x,x^{3}+Ax+B)\neq 1$

Algoritmo

Aporte: 1. Curva elíptica .

E=y^{2}-x^{3}-Ax-B

2. Un número entero q para un campo finito con .

F_q

q=p^{b},b\geq 1

Conclusión: Número de puntos E sobre .

F_q

Elegimos un conjunto de primos impares S , que no contenga p , tales que Aceptamos si mcd , de lo contrario aceptamos . Calculamos el polinomio de división .

N=\prod _{l\in S}l>4{\sqrt {q)).

{\ estilo de visualización t_ {2} = 0}

(x^{q}-x,x^{3}+Ax+B)\neq 1

{\ estilo de visualización t_ {2} = 1}

{\ estilo de visualización \ psi _ {l}}

Todos los cálculos en el bucle de abajo se llevan a cabo en el anillo . Para ejecutamos : Sea el único entero tal que y . Calculamos , y . Si entonces Calcula . para hacer : si entonces si entonces ; de lo contrario de lo contrario, si q es un cuadrado módulo l , entonces calcule w con calcule si entonces de lo contrario si entonces de otro modo de lo contrario Use el teorema del resto chino para calcular t módulo N a partir de la ecuación donde .

\mathbb {F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi_{l}).

{\ estilo de visualización l \ en S}

{\ estilo de visualización {\ bar {q}}}

q\equiv {\bar {q}}{\pmod {l}}

\mid {\bar {q}}\mid <l/2

{\ estilo de visualización (x^{q},y^{q})}

{\ estilo de visualización (x^{q^{2}},y^{q^{2}})}

{\ estilo de visualización (x_ {\ barra {q)), y_ {\ barra {q)))}

x^{q^{2}}\neq x_{\bar {q}}

(X, Y)

{\ estilo de visualización 1 \ leq {\ bar {t}} \ leq (l-1)/2}

X=x_{\bar {t}}^{q}

Y=y_{\bar{t}}^{q}

t_{l}={\bar{t))

t_{l}=-{\bar{t))

q\equiv w^{2}{\pmod {l))

{\ estilo de visualización w (x ^ {q}, y ^ {q})}

w(x^{q},y^{q})=(x^{q^{2}},y^{q^{2}})

{\ estilo de visualización t_ {l} = 2w}

w(x^{q},y^{q})=(x^{q^{2}},-y^{q^{2}})

{\ estilo de visualización t_ {l} = -2w}

{\ estilo de visualización t_ {l} = 0}

{\ estilo de visualización t_ {l} = 0}

x\equiv t_{l}{\pmod {l))

{\ estilo de visualización l \ en S}

Derivamos .

{\ estilo de visualización q+1-t}

Dificultad

La mayoría de los cálculos implican calcular y , para cada número primo , es decir , calcular , , para cada número primo . Los cálculos involucran exponenciación en el anillo y requieren multiplicaciones. Como el grado es , cada elemento del anillo es un polinomio de grado . Por el teorema de los números primos, hay aproximadamente números primos de tamaño , lo que da , y obtenemos . Por lo tanto, cada multiplicación en el anillo requiere multiplicaciones en , lo que a su vez requiere operaciones bit a bit. En total, el número de operaciones de bits para cada número primo es . Suponiendo que este cálculo debe realizarse para cada uno de los números primos, la complejidad total del algoritmo de Schuf se convierte en . El uso de operaciones polinómicas rápidas y aritmética de enteros reduce este tiempo a . ${\ estilo de visualización \ phi (P)}$ ${\ estilo de visualización \ phi ^ {2} (P)}$ $yo$ ${\ estilo de visualización x ^ {q}}$ ${\ Displaystyle y^{q}}$ ${\ estilo de visualización x^{q^{2))}$ $y^{q^{2}}$ $yo$ $R=\mathbb {F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi_{l})$ ${\ estilo de visualización O (\ log q)}$ ${\ estilo de visualización \ psi _ {l}}$ ${\frac {l^{2}-1}{2}}$ ${\ estilo de visualización O (l ^ {2})}$ ${\ estilo de visualización O (\ log q)}$ ${\ estilo de visualización O (\ log q)}$ $yo$ ${\ estilo de visualización O (\ log q)}$ $O(l^{2})=O(\log ^{2}q)$ $R$ $O(\log ^{4}q)$ $\mathbb {F} _{q}$ $O(\log ^{2}q)$ $yo$ $O(\log ^{7}q)$ ${\ estilo de visualización O (\ log q)}$ $O(\log ^{8}q)$ ${\tilde {O}}(\log^{5}q)$

Mejoras al algoritmo de Schuf

En la década de 1990, Noam Elkis y luego A. O. L. Atkin propusieron mejoras al algoritmo básico de Schuf al restringir el conjunto de números primos a números de cierto tipo. Estos números se conocieron como primos de Elkis y primos de Atkin, respectivamente. Un número primo se llama primo de Elkis si la igualdad característica es descomponible en , y los números primos de Atkin son números primos que no son números primos de Elkis. Atkin mostró cómo combinar la información obtenida de los números primos de Atkin con la información obtenida de los números primos de Elkis para obtener un algoritmo eficiente, que se denominó " Algoritmo Schoof-Elkis-Atkin . La primera tarea es determinar si un número primo dado es un número primo de Elkis o de Atkin. Para conseguir esto, utilizamos polinomios modulares, que surgen al estudiar formas modulares e interpretar curvas elípticas sobre el campo de números complejos como redes. Una vez que determinamos qué caso tenemos, en lugar de usar polinomios de división , podemos trabajar con polinomios que tienen grados más bajos que los polinomios de división: en lugar de . Para una implementación eficiente, se utilizan algoritmos probabilísticos de búsqueda de raíces, lo que hace que el algoritmo sea un algoritmo de Las Vegas , en lugar de un algoritmo determinista. Bajo la suposición heurística de que aproximadamente la mitad de los números primos menores o iguales son números primos de Elkis, esto produce un algoritmo que es más eficiente que el algoritmo de Schoof, y el tiempo de ejecución esperado de este algoritmo es , si se usa aritmética ordinaria, y , si se usa aritmética rápida. Cabe señalar que esta suposición heurística es cierta para la mayoría de las curvas elípticas, pero no se conoce para el caso general, incluso si la hipótesis de Riemann generalizada es cierta . $S=\{l_{1},\ldots,l_{s}\}$ $yo$ $\phi ^{2}-t\phi +q=0$ ${\ estilo de visualización \ mathbb {F} _ {l}}$ ${\ estilo de visualización O (l)}$ ${\ estilo de visualización O (l ^ {2})}$ ${\ estilo de visualización O (\ log q)}$ $O(\log ^{6}q)$ ${\tilde {O}}(\log^{4}q)$

Implementaciones

Algunos de los algoritmos han sido implementados en C++ por Mike Scott y están disponibles en código fuente . La implementación es absolutamente gratuita (sin condiciones, sin restricciones), pero utiliza la biblioteca MIRACL , que se distribuye bajo la licencia AGPLv3 .

Algoritmo de Schuf con implementación para con simple . ${\ estilo de visualización E (\ mathbb {F} _ {p})}$ $pags$
Algoritmo de Schuf con implementación para . $E(\mathbb {F} _{2^{m)))$

Véase también

Criptografía elíptica
Contar puntos en una curva elíptica
división de polinomios
Endomorfismo de Frobenius

Notas

↑ Aunque, el artículo de ECDSA dice lo siguiente: el algoritmo de Skoof es bastante ineficiente en la práctica para valores de p que son realmente de interés, es decir, p > 2 160 .
↑ El punto mP, igual a la suma m-veces del punto P en el grupo aditivo de puntos de una curva elíptica, se llama producto escalar del punto y el número m , y los puntos mP mismos se llaman múltiplos escalares de el punto ( Rybolovlev 2004 ). En el libro de Tiborg ( van Tilborg 2006 ) el mismo concepto se denomina múltiplo escalar.

Literatura

R. Schoof. Curvas elípticas sobre campos finitos y cálculo de raíces cuadradas mod p // Math. Comp.. - 1985. - T. 44 , núm. 170 . — S. 483–494 .
R. Schoof. Puntos de conteo en curvas elípticas sobre campos finitos // J. Theor. Nombres Burdeos. - 1995. - Edición. 7 . — S. 219–254 .
Gregg Musiker. Algoritmo de Schoof para contar puntos en ${\ estilo de visualización E (\ mathbb {F} _ {q})}$ . — 2005.
V. Müller. Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern . - Saarbrücken: Universität des Saarlandes, 1991. - (Tesis de Maestría).
Andreas Eng. Curvas elípticas y sus aplicaciones a la criptografía: una introducción. - Dordrecht: Kluwer Academic Publishers, 1999.
Lawrence C.Washington. Curvas elípticas: teoría de números y criptografía. - Nueva York: Chapman & Hall/CRC, 2003. - V. 50. - (Matemáticas Discretas y sus aplicaciones). — ISBN 978-1-4200-7146-7 .
Neal Koblitz. Un curso de teoría de números y criptografía. - Segunda edicion. - Springer-Verlag, 1994. - V. 114. - (Textos de Grado en Matemáticas). — ISBN 0-387-94293-9 .
H. C. A. van Tilborg. Fundamentos de criptología. - Moscú: Mir, 2006. - ISBN 5-03-003639-3 UDC 519.6.
Dmitri Rybolovlev. Uso de Criptografía de Curva Elíptica en Seguridad WEB . — 2004.

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