Algoritmo de Schoof

El algoritmo de Schoof es un algoritmo eficiente para contar puntos en curvas elípticas sobre cuerpos finitos . El algoritmo tiene aplicaciones en criptografía de curvas elípticas , donde es importante conocer la cantidad de puntos para juzgar la dificultad de resolver el problema del logaritmo discreto en el grupo de puntos de una curva elíptica.

El algoritmo fue publicado por René Schoof en 1985 y fue un gran avance teórico, ya que fue el primer algoritmo de tiempo polinomial 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 pequeños y pasos gigantes, eran, en su mayoría, tediosos y tenían un tiempo de ejecución exponencial.

Este artículo explica el enfoque de Schoof, haciendo hincapié en las ideas matemáticas que subyacen a la estructura del algoritmo.

Introducción

Sea una curva elíptica definida sobre el cuerpo finito , donde para un primo y un entero . Sobre un cuerpo de características una curva elíptica puede darse mediante una ecuación de Weierstrass (corta) ${\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 definidos sobre consiste en 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 , con actuando como el 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 sobre curvas elípticas junto con el teorema del resto chino y 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 cuerpo 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, dado por Hasse en 1934, simplifica nuestro problema al reducirlo a un conjunto finito (aunque grande) de posibilidades. Definiendo como , y haciendo uso de este resultado, ahora tenemos que calcular el valor de módulo donde , es suficiente para determinar , y por lo tanto . Si bien no hay una manera eficiente de calcular directamente para , es posible calcular para un primo pequeño, de manera bastante eficiente. Elegimos ser un conjunto de primos distintos tales que . Dado para todo , el teorema del resto chino 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 primo , utilizamos la teoría del endomorfismo de Frobenius y los polinomios de división . Nótese que considerar primos no es una pérdida ya que siempre podemos elegir un primo mayor para tomar su lugar y asegurarnos de que el producto sea lo suficientemente grande. En cualquier caso, el algoritmo de Schoof es el más utilizado para abordar el caso ya que existen algoritmos más eficientes, los llamados ádicos, para cuerpos 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 sobre , la clausura algebraica de ; es decir, permitimos puntos con coordenadas en . El endomorfismo de Frobenius de sobre 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 en y se puede extender hasta el punto en el infinito , convirtiéndolo en un morfismo de grupo de a 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 por 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 lo anterior , donde + denota adición en la curva elíptica y y denotan 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 de que satisfaga la ecuación. Sin embargo, los grados son 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 llevar a cabo este cálculo restringido a puntos de orden para varios primos pequeños . Fijando un primo impar , ahora pasamos a resolver el problema de determinar , definido como , para un primo dado . Si un punto está en el subgrupo de torsión - , entonces donde es el único entero tal que y . Nótese que y que para cualquier entero tenemos . Por lo tanto tendrá el mismo orden que . Por lo tanto, para pertenecer a , también tenemos si . 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]}$

Cálculo módulo primos

El polinomio de división l es tal que sus raíces son precisamente las coordenadas x de los puntos de orden l . Por lo tanto, restringir el cálculo de a los puntos de torsión l significa calcular estas expresiones como funciones en el anillo de coordenadas de E y módulo el 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 el método de doble y suma o utilizando el polinomio de división enésimo. Este último método da como resultado: ${\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)}$

donde es el polinomio de división n . Nótese que es una función solo en x y denotándola 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 . Nótese que estas igualdades se comprueban 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)}

Utilizando la fórmula de adición 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 utilizar la coordenada x para limitar la elección a dos posibilidades, es decir, el caso positivo y el negativo. Utilizando la coordenada y , más adelante se determina cuál de los dos casos se cumple. ${\displaystyle {\bar {t}}}$

Primero demostramos que X es una función en x solamente. Consideremos . Como es par, al reemplazar 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í no parece correcto, ¿tiramos ? ${\displaystyle x^{q^{2}}-x_{\bar {q}}}$

Ahora bien, 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 los puntos de l -torsión P .

Como se mencionó anteriormente, utilizando 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 primo l 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 . Como l es un primo impar, no puede ser eso y, por lo tanto , . La ecuación característica produce que . Y, en consecuencia, que . Esto implica que q es un cuadrado módulo l . Sea . Calcule en 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 cuadrado módulo l o si la ecuación no se cumple para ninguno de w y , nuestra suposición de que 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 recuerdas, nuestras consideraciones iniciales omiten el caso de . Dado que suponemos que q es impar, y en particular, si y solo si tiene un elemento de orden 2. Por definición de adición en el grupo, cualquier elemento de orden 2 debe ser de la forma . Por lo tanto, si y solo si el polinomio tiene una raíz en , si y solo 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 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 primos impares S que no contengan p  tales que:  ${\displaystyle N=\prod _{l\in S}l>4{\sqrt {q}}.}$ Ponga  if , else .  ${\displaystyle t_{2}=0}$   ${\displaystyle \gcd(x^{q}-x,x^{3}+Ax+B)\neq 1}$  ${\displaystyle t_{2}=1}$ Calcule el polinomio de división ${\displaystyle \psi _{l}}$ . Todos los cálculos en el bucle a continuación se realizan en el anillo  ${\displaystyle \mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l}).}$ Para  do :  ${\displaystyle l\in S}$  Sea el único entero  ${\displaystyle {\bar {q}}}$ tal que y .  ${\displaystyle q\equiv {\bar {q}}{\pmod {l}}}$ ${\displaystyle \mid {\bar {q}}\mid <l/2}$ Calcule , 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}}}$   Calcule .  ${\displaystyle (X,Y)}$ para  do :  ${\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}}$   ; de lo contrario . de lo contrario si q es un cuadrado módulo l entonces calcule w con calcular si entonces de lo contrario si entonces de lo contrario 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. Dado que el grado de es , cada elemento del anillo es un polinomio de grado . Por el teorema de los números primos , hay alrededor de primos de tamaño , dando que es y obtenemos que . 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 primos, la complejidad total del algoritmo de Schoof resulta ser . Usando polinomios rápidos y aritmética de números enteros esto se reduce 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 en el algoritmo de Schoof

En la década de 1990, Noam Elkies , seguido por AOL Atkin , idearon mejoras al algoritmo básico de Schoof al restringir el conjunto de primos considerados antes a primos de un cierto tipo. Estos llegaron a llamarse primos de Elkies y primos de Atkin respectivamente. Un primo se llama primo de Elkies si la ecuación característica: se divide en , 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 el algoritmo de Schoof-Elkies-Atkin . El primer problema a abordar es determinar si un primo dado es Elkies o Atkin. Para ello, hacemos uso de polinomios modulares, que provienen del estudio de formas modulares y una interpretación de curvas elípticas sobre los 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 un grado menor 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 hace que este sea un algoritmo de Las Vegas en lugar de un algoritmo determinista. Bajo el supuesto heurístico de que aproximadamente la mitad de los 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 usar aritmética ingenua y usar aritmética rápida. Aunque se sabe que este supuesto heurístico es válido para la mayoría de las curvas elípticas, no se sabe que sea válido 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 código fuente. Las implementaciones son gratuitas (sin términos ni condiciones) y utilizan la biblioteca MIRACL, que se distribuye bajo la licencia AGPLv3 .

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

Véase también

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

Referencias

• R. Schoof: Curvas elípticas sobre cuerpos finitos y el cálculo de raíces cuadradas mod p. Math. Comp., 44(170):483–494, 1985. Disponible en http://www.mat.uniroma2.it/~schoof/ctpts.pdf
• R. Schoof: Conteo de puntos en curvas elípticas sobre cuerpos 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. Tesis de Maestría. Universität des Saarlandes, Saarbrücken, 1991. Disponible en http://lecturer.ukdw.ac.id/vmueller/publications.php
• A. Enge: Curvas elípticas y sus aplicaciones a la criptografía: una introducción. Kluwer Academic Publishers, Dordrecht, 1999.
• LC Washington: Curvas elípticas: teoría de números y criptografía. Chapman & Hall/CRC, Nueva York, 2003.
• N. Koblitz: Un curso sobre teoría de números y criptografía, Textos de posgrado en matemáticas, n.º 114, Springer-Verlag, 1987. Segunda edición, 1994