algoritmo de Schoof

El algoritmo de Schoof es un algoritmo eficiente para contar puntos en curvas elípticas sobre campos finitos . El algoritmo tiene aplicaciones en criptografía de curva elíptica donde es importante conocer el número de puntos para juzgar la dificultad de resolver el problema de logaritmos discretos en el grupo de puntos de una curva elíptica.

El algoritmo fue publicado por René Schoof en 1985 y supuso un avance teórico, ya que fue el primer algoritmo de tiempo polinómico determinista para contar puntos en curvas elípticas . Antes del algoritmo de Schoof, los enfoques para contar puntos en curvas elípticas, como los algoritmos ingenuos y de pasos gigantes, eran, en su mayor parte, tediosos y tenían un tiempo de ejecución exponencial.

Este artículo explica el enfoque de Schoof, poniendo énfasis en las ideas matemáticas subyacentes a la estructura del algoritmo.

Introducción

Sea una curva elíptica definida sobre el campo finito , donde para un número primo y un número entero . Sobre un campo de características, se puede dar una curva elíptica mediante una ecuación (corta) de Weierstrass. ${\displaystyle E}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle q=p^{n}}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle \geq 1}$ ${\displaystyle \neq 2,3}$

${\displaystyle y^{2}=x^{3}+Ax+B}$

con . El conjunto de puntos definido consta de las soluciones que satisfacen la ecuación de la curva y un punto en el infinito . Usando la ley de grupo sobre curvas elípticas restringida a este conjunto, se puede ver que este conjunto forma un grupo abeliano , actuando como elemento cero. Para contar puntos en una curva elíptica, calculamos la cardinalidad de . El enfoque de Schoof para calcular la cardinalidad hace uso del teorema de Hasse en curvas elípticas junto con el teorema del resto chino y los polinomios de división . ${\displaystyle A,B\in \mathbb {F} _{q}}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle (a,b)\in \mathbb {F} _{q}^{2}}$ ${\displaystyle O}$ ${\displaystyle E(\mathbb {F} _{q})}$ ${\displaystyle O}$ ${\displaystyle E(\mathbb {F} _{q})}$ ${\displaystyle \#E(\mathbb {F} _{q})}$

teorema de hasse

El teorema de Hasse establece que si es una curva elíptica sobre el campo finito , entonces satisface ${\displaystyle E/\mathbb {F} _{q}}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle \#E(\mathbb {F} _{q})}$

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

Este poderoso resultado, proporcionado por Hasse en 1934, simplifica nuestro problema al reducirlo a un conjunto finito (aunque grande) de posibilidades. Definiendo ser y haciendo uso de este resultado, ahora tenemos que calcular el valor del módulo donde es suficiente para determinar y por lo tanto . Si bien no existe una forma eficiente de calcular directamente para general , es posible calcular para un primo pequeño, de manera bastante eficiente. Elegimos ser un conjunto de primos distintos tales que . Dado para todos , el teorema chino del resto nos permite calcular . ${\displaystyle \#E(\mathbb {F} _{q})}$ ${\displaystyle t}$ ${\displaystyle q+1-\#E(\mathbb {F} _{q})}$ ${\displaystyle t}$ ${\displaystyle N}$ ${\displaystyle N>4{\sqrt {q}}}$ ${\displaystyle t}$ ${\displaystyle \#E(\mathbb {F} _{q})}$ ${\displaystyle t{\pmod {N}}}$ ${\displaystyle N}$ ${\displaystyle t{\pmod {l}}}$ ${\displaystyle l}$ ${\displaystyle S=\{l_{1},l_{2},...,l_{r}\}}$ ${\displaystyle \prod l_{i}=N>4{\sqrt {q}}}$ ${\displaystyle t{\pmod {l_{i}}}}$ ${\displaystyle l_{i}\in S}$ ${\displaystyle t{\pmod {N}}}$

Para calcular un número primo , utilizamos la teoría del endomorfismo de Frobenius y la división de polinomios . Tenga en cuenta que considerar números primos no supone ninguna pérdida, ya que siempre podemos elegir un número primo más grande para que ocupe su lugar y garantizar que el producto sea lo suficientemente grande. En cualquier caso, el algoritmo de Schoof se utiliza con mayor frecuencia para abordar el caso, ya que existen algoritmos más eficientes, los llamados algoritmos ádicos, para campos de características pequeñas. ${\displaystyle t{\pmod {l}}}$ ${\displaystyle l\neq p}$ ${\displaystyle \phi }$ ${\displaystyle l\neq p}$ ${\displaystyle q=p}$ ${\displaystyle p}$

El endomorfismo de Frobenius

Dada la curva elíptica definida sobre consideramos puntos sobre , el cierre algebraico de ; es decir, permitimos puntos con coordenadas en . El endomorfismo de Frobenius de over se extiende a la curva elíptica por . ${\displaystyle E}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle E}$ ${\displaystyle {\bar {\mathbb {F} }}_{q}}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle {\bar {\mathbb {F} }}_{q}}$ ${\displaystyle {\bar {\mathbb {F} }}_{q}}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle \phi :(x,y)\mapsto (x^{q},y^{q})}$

Este mapa es la identidad y se puede extender hasta el punto del infinito , convirtiéndolo en un morfismo de grupo desde hacia sí mismo. ${\displaystyle E(\mathbb {F} _{q})}$ ${\displaystyle O}$ ${\displaystyle E({\bar {\mathbb {F} _{q}}})}$

El endomorfismo de Frobenius satisface un polinomio cuadrático que está vinculado a la cardinalidad de mediante el siguiente teorema: ${\displaystyle E(\mathbb {F} _{q})}$

Teorema: El endomorfismo de Frobenius dado por satisface la ecuación característica ${\displaystyle \phi }$

${\displaystyle \phi ^{2}-t\phi +q=0,}$dónde ${\displaystyle t=q+1-\#E(\mathbb {F} _{q})}$

Así tenemos para todo eso , donde + denota suma en la curva elíptica y y denota multiplicación escalar de por y de por . ${\displaystyle P=(x,y)\in E}$ ${\displaystyle (x^{q^{2}},y^{q^{2}})+q(x,y)=t(x^{q},y^{q})}$ ${\displaystyle q(x,y)}$ ${\displaystyle t(x^{q},y^{q})}$ ${\displaystyle (x,y)}$ ${\displaystyle q}$ ${\displaystyle (x^{q},y^{q})}$ ${\displaystyle t}$

Se podría intentar calcular simbólicamente estos puntos y como funciones en el anillo de coordenadas de y luego buscar un valor que satisfaga la ecuación. Sin embargo, los grados se hacen muy grandes y este enfoque no es práctico. ${\displaystyle (x^{q^{2}},y^{q^{2}})}$ ${\displaystyle (x^{q},y^{q})}$ ${\displaystyle q(x,y)}$ ${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B)}$ ${\displaystyle E}$ ${\displaystyle t}$

La idea de Schoof era realizar este cálculo restringido a cuestiones de orden para varios números primos pequeños . Fijando un número primo impar , pasamos ahora a resolver el problema de determinar , definido como , para un número primo dado . Si un punto está en el subgrupo de torsión , entonces ¿dónde está el número entero único tal que y ? Tenga en cuenta eso y eso para cualquier número entero que tengamos . Por lo tanto tendrá el mismo orden que . Así, para pertenecer a , también tenemos if . Por lo tanto hemos reducido nuestro problema a resolver la ecuación ${\displaystyle l}$ ${\displaystyle l}$ ${\displaystyle l}$ ${\displaystyle t_{l}}$ ${\displaystyle t{\pmod {l}}}$ ${\displaystyle l\neq 2,p}$ ${\displaystyle (x,y)}$ ${\displaystyle l}$ ${\displaystyle E[l]=\{P\in E({\bar {\mathbb {F} _{q}}})\mid lP=O\}}$ ${\displaystyle qP={\bar {q}}P}$ ${\displaystyle {\bar {q}}}$ ${\displaystyle q\equiv {\bar {q}}{\pmod {l}}}$ ${\displaystyle \mid {\bar {q}}\mid <l/2}$ ${\displaystyle \phi (O)=O}$ ${\displaystyle r}$ ${\displaystyle r\phi (P)=\phi (rP)}$ ${\displaystyle \phi (P)}$ ${\displaystyle P}$ ${\displaystyle (x,y)}$ ${\displaystyle E[l]}$ ${\displaystyle t(x^{q},y^{q})={\bar {t}}(x^{q},y^{q})}$ ${\displaystyle t\equiv {\bar {t}}{\pmod {l}}}$

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

donde y tienen valores enteros en . ${\displaystyle {\bar {t}}}$ ${\displaystyle {\bar {q}}}$ ${\displaystyle [-(l-1)/2,(l-1)/2]}$

Primos de módulo de cálculo

El polinomio de división l es tal que sus raíces son precisamente las coordenadas x de puntos de orden l . Por lo tanto, restringir el cálculo de a los l -puntos de torsión significa calcular estas expresiones como funciones en el anillo de coordenadas de E y módulo del polinomio de división l . Es decir, estamos trabajando en . Esto significa en particular que el grado de X e Y definido mediante es como máximo 1 en y y como máximo en x . ${\displaystyle (x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)}$ ${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})}$ ${\displaystyle (X(x,y),Y(x,y)):=(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)}$ ${\displaystyle (l^{2}-3)/2}$

La multiplicación escalar se puede realizar mediante métodos de duplicación y suma o utilizando el polinomio de división enésima. El último enfoque da: ${\displaystyle {\bar {q}}(x,y)}$ ${\displaystyle {\bar {q}}}$

${\displaystyle {\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)}$

¿ Dónde está el polinomio de n- ésima división? Tenga en cuenta que es una función solo en x y denotela por . ${\displaystyle \psi _{n}}$ ${\displaystyle y_{\bar {q}}/y}$ ${\displaystyle \theta (x)}$

Debemos dividir el problema en dos casos: el caso en el que y el caso en el que . Tenga en cuenta que estas igualdades se verifican módulo . ${\displaystyle (x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)}$ ${\displaystyle (x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)}$ ${\displaystyle \psi _{l}}$

Caso 1: ( x q 2 , y q 2 ) ≠ ± q ¯ ( x , y ) {\displaystyle (x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)}

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

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

Tenga en cuenta que este cálculo falla en caso de que el supuesto de desigualdad fuera incorrecto.

Ahora podemos usar la coordenada x para reducir la elección a dos posibilidades, es decir, el caso positivo y el negativo. Usando la coordenada y se determina posteriormente cuál de los dos casos se cumple. ${\displaystyle {\bar {t}}}$

Primero demostramos que X es una función sólo en x . Considerar . Como es par, reemplazando por , reescribimos la expresión como ${\displaystyle (y^{q^{2}}-y_{\bar {q}})^{2}=y^{2}(y^{q^{2}-1}-y_{\bar {q}}/y)^{2}}$ ${\displaystyle q^{2}-1}$ ${\displaystyle y^{2}}$ ${\displaystyle x^{3}+Ax+B}$

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

y tener eso

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

Aquí, parece que no está bien, ¿lo tiramos ? ${\displaystyle x^{q^{2}}-x_{\bar {q}}}$

Ahora si para uno entonces satisface. ${\displaystyle X\equiv x_{\bar {t}}^{q}{\bmod {\psi }}_{l}(x)}$ ${\displaystyle {\bar {t}}\in [0,(l-1)/2]}$ ${\displaystyle {\bar {t}}}$

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

para todos l -puntos de torsión P .

Como se mencionó anteriormente, usando Y y ahora podemos determinar cuál de los dos valores de ( o ) funciona. Esto da el valor de . El algoritmo de Schoof almacena los valores de en una variable para cada l primo considerado. ${\displaystyle y_{\bar {t}}^{q}}$ ${\displaystyle {\bar {t}}}$ ${\displaystyle {\bar {t}}}$ ${\displaystyle -{\bar {t}}}$ ${\displaystyle t\equiv {\bar {t}}{\pmod {l}}}$ ${\displaystyle {\bar {t}}{\pmod {l}}}$ ${\displaystyle t_{l}}$

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

Comenzamos con el supuesto de que . Dado que l es un número primo impar, no puede serlo y por lo tanto . La ecuación característica produce eso . Y en consecuencia eso . Esto implica que q es un módulo cuadrado l . Dejar . Calcule y verifique si . Si es así, depende de la coordenada y. ${\displaystyle (x^{q^{2}},y^{q^{2}})={\bar {q}}(x,y)}$ ${\displaystyle {\bar {q}}(x,y)=-{\bar {q}}(x,y)}$ ${\displaystyle {\bar {t}}\neq 0}$ ${\displaystyle {\bar {t}}\phi (P)=2{\bar {q}}P}$ ${\displaystyle {\bar {t}}^{2}{\bar {q}}\equiv (2q)^{2}{\pmod {l}}}$ ${\displaystyle q\equiv w^{2}{\pmod {l}}}$ ${\displaystyle w\phi (x,y)}$ ${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})}$ ${\displaystyle {\bar {q}}(x,y)=w\phi (x,y)}$ ${\displaystyle t_{l}}$ ${\displaystyle \pm 2w{\pmod {l}}}$

Si q resulta no ser un módulo cuadrado l o si la ecuación no se cumple para ninguno de w y , nuestra suposición es falsa, por lo tanto . La ecuación característica da . ${\displaystyle -w}$ ${\displaystyle (x^{q^{2}},y^{q^{2}})=+{\bar {q}}(x,y)}$ ${\displaystyle (x^{q^{2}},y^{q^{2}})=-{\bar {q}}(x,y)}$ ${\displaystyle t_{l}=0}$

Caso adicional l = 2 {\displaystyle l=2}

Si recuerda, nuestras consideraciones iniciales omiten el caso de . Dado que asumimos que q es impar y, en particular, si y solo si tiene un elemento de orden 2. Por definición de suma en el grupo, cualquier elemento de orden 2 debe ser de la forma . Por tanto , si y sólo si el polinomio tiene raíz en , si y sólo si . ${\displaystyle l=2}$ ${\displaystyle q+1-t\equiv t{\pmod {2}}}$ ${\displaystyle t_{2}\equiv 0{\pmod {2}}}$ ${\displaystyle E(\mathbb {F} _{q})}$ ${\displaystyle (x_{0},0)}$ ${\displaystyle t_{2}\equiv 0{\pmod {2}}}$ ${\displaystyle x^{3}+Ax+B}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle \gcd(x^{q}-x,x^{3}+Ax+B)\neq 1}$

el algoritmo

 Aporte: 1. Una curva elíptica . ${\displaystyle E=y^{2}-x^{3}-Ax-B}$ 2. Un número entero q para un campo finito con . ${\displaystyle F_{q}}$ ${\displaystyle q=p^{b},b\geq 1}$ Producción: El número de puntos de E sobre . ${\displaystyle F_{q}}$ Elija un conjunto de números primos impares S que no contengan p  tal que  ${\displaystyle N=\prod _{l\in S}l>4{\sqrt {q}}.}$ Put  if , else .  ${\displaystyle t_{2}=0}$   ${\displaystyle \gcd(x^{q}-x,x^{3}+Ax+B)\neq 1}$  ${\displaystyle t_{2}=1}$ Calcula el polinomio de división ${\displaystyle \psi _{l}}$ . Todos los cálculos en el bucle siguiente se realizan en el anillo  ${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l}).}$ For  do :  ${\displaystyle l\in S}$  Sea el número entero único  ${\displaystyle {\bar {q}}}$ tal que y .  ${\displaystyle q\equiv {\bar {q}}{\pmod {l}}}$ ${\displaystyle \mid {\bar {q}}\mid <l/2}$ Calcular y .​  ${\displaystyle (x^{q},y^{q})}$ ${\displaystyle (x^{q^{2}},y^{q^{2}})}$ ${\displaystyle (x_{\bar {q}},y_{\bar {q}})}$ si  entonces ${\displaystyle x^{q^{2}}\neq x_{\bar {q}}}$   Calcular .  ${\displaystyle (X,Y)}$ para  hacer :  ${\displaystyle 1\leq {\bar {t}}\leq (l-1)/2}$  si  entonces  ${\displaystyle X=x_{\bar {t}}^{q}}$  si  entonces ${\displaystyle Y=y_{\bar {t}}^{q}}$   ; demás . de lo contrario, si q es un módulo cuadrado l, entonces calcule w con calcule si, entonces , de lo contrario, si, de lo contrario, utilice el teorema del resto chino para calcular t módulo N a partir de las ecuaciones , donde . ${\displaystyle t_{l}={\bar {t}}}$   ${\displaystyle t_{l}=-{\bar {t}}}$     ${\displaystyle q\equiv w^{2}{\pmod {l}}}$  ${\displaystyle w(x^{q},y^{q})}$   ${\displaystyle w(x^{q},y^{q})=(x^{q^{2}},y^{q^{2}})}$   ${\displaystyle t_{l}=2w}$   ${\displaystyle w(x^{q},y^{q})=(x^{q^{2}},-y^{q^{2}})}$   ${\displaystyle t_{l}=-2w}$   ${\displaystyle t_{l}=0}$   ${\displaystyle t_{l}=0}$ ${\displaystyle t\equiv t_{l}{\pmod {l}}}$ ${\displaystyle l\in S}$ Producción . ${\displaystyle q+1-t}$

Complejidad

La mayor parte del cálculo se realiza mediante la evaluación de y , para cada primo , es decir, calculando ,,, para cada primo . Esto implica exponenciación en el anillo y requiere multiplicaciones. Como el grado de es , cada elemento del anillo es un polinomio de grado . Según el teorema de los números primos , hay alrededor de primos de tamaño , dando eso es y obtenemos eso . Por lo tanto, cada multiplicación en el anillo requiere multiplicaciones que a su vez requieren operaciones de bits. En total, el número de operaciones de bits para cada primo es . Dado que este cálculo debe realizarse para cada uno de los números primos, la complejidad total del algoritmo de Schoof resulta ser . El uso de aritmética rápida de polinomios y enteros reduce esto a . ${\displaystyle \phi (P)}$ ${\displaystyle \phi ^{2}(P)}$ ${\displaystyle l}$ ${\displaystyle x^{q}}$ ${\displaystyle y^{q}}$ ${\displaystyle x^{q^{2}}}$ ${\displaystyle y^{q^{2}}}$ ${\displaystyle l}$ ${\displaystyle R=\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})}$ ${\displaystyle O(\log q)}$ ${\displaystyle \psi _{l}}$ ${\displaystyle {\frac {l^{2}-1}{2}}}$ ${\displaystyle O(l^{2})}$ ${\displaystyle O(\log q)}$ ${\displaystyle O(\log q)}$ ${\displaystyle l}$ ${\displaystyle O(\log q)}$ ${\displaystyle O(l^{2})=O(\log ^{2}q)}$ ${\displaystyle R}$ ${\displaystyle O(\log ^{4}q)}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle O(\log ^{2}q)}$ ${\displaystyle l}$ ${\displaystyle O(\log ^{7}q)}$ ${\displaystyle O(\log q)}$ ${\displaystyle O(\log ^{8}q)}$ ${\displaystyle {\tilde {O}}(\log ^{5}q)}$

Mejoras al algoritmo de Schoof

En la década de 1990, Noam Elkies , seguido de AOL Atkin , idearon mejoras al algoritmo básico de Schoof restringiendo el conjunto de números primos considerados antes a números primos de un determinado tipo. Estos pasaron a denominarse primos de Elkies y primos de Atkin, respectivamente. Un primo se llama primo de Elkies si la ecuación característica: se divide , mientras que un primo de Atkin es un primo que no es un primo de Elkies. Atkin mostró cómo combinar la información obtenida de los primos de Atkin con la información obtenida de los primos de Elkies para producir un algoritmo eficiente, que llegó a conocerse como algoritmo de Schoof-Elkies-Atkin . El primer problema a abordar es determinar si un número primo dado es Elkies o Atkin. Para ello utilizamos polinomios modulares, que provienen del estudio de formas modulares y de la interpretación de curvas elípticas sobre números complejos como retículos. Una vez que hemos determinado en qué caso estamos, en lugar de usar polinomios de división , podemos trabajar con un polinomio que tenga menor grado que el polinomio de división correspondiente: en lugar de . Para una implementación eficiente, se utilizan algoritmos probabilísticos de búsqueda de raíces, lo que lo convierte en un algoritmo de Las Vegas en lugar de un algoritmo determinista. Bajo el supuesto heurístico de que aproximadamente la mitad de los números primos hasta un límite son primos de Elkies, esto produce un algoritmo que es más eficiente que el de Schoof, con un tiempo de ejecución esperado de uso de aritmética ingenua y aritmética rápida. Aunque se sabe que esta suposición heurística se cumple para la mayoría de las curvas elípticas, no se sabe que se cumpla en todos los casos, incluso bajo el GRH . ${\displaystyle S=\{l_{1},\ldots ,l_{s}\}}$ ${\displaystyle l}$ ${\displaystyle \phi ^{2}-t\phi +q=0}$ ${\displaystyle \mathbb {F} _{l}}$ ${\displaystyle O(l)}$ ${\displaystyle O(l^{2})}$ ${\displaystyle O(\log q)}$ ${\displaystyle O(\log ^{6}q)}$ ${\displaystyle {\tilde {O}}(\log ^{4}q)}$

Implementaciones

Mike Scott implementó varios algoritmos en C++ y están disponibles con el código fuente. Las implementaciones son gratuitas (sin términos ni condiciones) y utilizan la biblioteca MIRACL que se distribuye bajo AGPLv3 .

• Implementación del algoritmo de Schoof para con prime . ${\displaystyle E(\mathbb {F} _{p})}$ ${\displaystyle p}$
• Implementación del algoritmo de Schoof para . ${\displaystyle E(\mathbb {F} _{2^{m}})}$

Ver también

• Criptografía de curva elíptica
• Contando puntos en curvas elípticas
• Polinomios de división
• Endomorfismo de Frobenius

Referencias

• R. Schoof: Curvas elípticas sobre campos finitos y cálculo de raíces cuadradas mod p. Matemáticas. Comp., 44(170):483–494, 1985. Disponible en http://www.mat.uniroma2.it/~schoof/ctpts.pdf
• R. Schoof: Contando puntos en curvas elípticas sobre campos finitos. J. Theor. Nombres Bordeaux 7:219–254, 1995. Disponible en http://www.mat.uniroma2.it/~schoof/ctg.pdf
• G. Musiker: Algoritmo de Schoof para contar puntos en . Disponible en http://www.math.umn.edu/~musiker/schoof.pdf ${\displaystyle E(\mathbb {F} _{q})}$
• V. Müller : Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern. Master's Thesis. Universität des Saarlandes, Saarbrücken, 1991. Available at http://lecturer.ukdw.ac.id/vmueller/publications.php
• A. Enge: Elliptic Curves and their Applications to Cryptography: An Introduction. Kluwer Academic Publishers, Dordrecht, 1999.
• L. C. Washington: Elliptic Curves: Number Theory and Cryptography. Chapman & Hall/CRC, New York, 2003.
• N. Koblitz: A Course in Number Theory and Cryptography, Graduate Texts in Math. No. 114, Springer-Verlag, 1987. Second edition, 1994