Algoritmo de Schoof-Elkies-Atkin

El algoritmo Schoof-Elkies-Atkin (SEA) es un algoritmo utilizado para encontrar el orden o calcular el número de puntos en una curva elíptica sobre un campo finito . Su aplicación principal es en criptografía de curva elíptica . El algoritmo es una extensión del algoritmo de Schoof de Noam Elkies y AOL Atkin para mejorar significativamente su eficiencia (bajo supuestos heurísticos).

Detalles

La extensión de Elkies-Atkin al algoritmo de Schoof funciona restringiendo el conjunto de números primos considerados a primos de cierto 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 hacerlo, utilizamos polinomios modulares que parametrizan pares de curvas elípticas isógenas en términos de sus invariantes j (en la práctica , también se pueden usar polinomios modulares alternativos, pero con el mismo propósito). ${\displaystyle S=\{l_{1},\ldots ,l_{s}\}}$ ${\displaystyle l}$ ${\displaystyle \phi ^{2}-t\phi +q=0}$ ${\displaystyle \mathbb {F} _{l}}$ ${\displaystyle \Phi _{l}(X,Y)}$ ${\displaystyle l}$

Si el polinomio instanciado tiene una raíz en entonces es un primo de Elkies, y podemos calcular un polinomio cuyas raíces corresponden a puntos en el núcleo de la -isogenia desde hasta . El polinomio es un divisor del polinomio de división correspondiente utilizado en el algoritmo de Schoof y tiene un grado significativamente menor que . Para los primos de Elkies, esto permite calcular el número de puntos en módulo de manera más eficiente que en el algoritmo de Schoof. En el caso de un primo de Atkin, podemos obtener cierta información del patrón de factorización de in , que restringe las posibilidades para el número de puntos módulo , pero la complejidad asintótica del algoritmo depende completamente de los primos de Elkies. Siempre que haya suficientes números primos de Elkies pequeños (en promedio, esperamos que la mitad de los primos sean primos de Elkies), esto da como resultado una reducción en el tiempo de ejecución. El algoritmo resultante es probabilístico (del tipo Las Vegas ) y su tiempo de ejecución esperado es, heurísticamente, , lo que lo hace más eficiente en la práctica que el algoritmo de Schoof. Aquí la notación es una variante de la notación O grande que suprime los términos que son logarítmicos en el término principal de una expresión. ${\displaystyle \Phi _{l}(X,j(E))}$ ${\displaystyle j(E')}$ ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle l}$ ${\displaystyle f_{l}(X)}$ ${\displaystyle l}$ ${\displaystyle E}$ ${\displaystyle E'}$ ${\displaystyle f_{l}}$ ${\displaystyle O(l)}$ ${\displaystyle O(l^{2})}$ ${\displaystyle E}$ ${\displaystyle l}$ ${\displaystyle \Phi _{l}(X,j(E))}$ ${\displaystyle \mathbb {F} _{l}[X]}$ ${\displaystyle l}$ ${\displaystyle l}$ ${\displaystyle {\tilde {O}}(\log ^{4}q)}$ ${\displaystyle {\tilde {O}}}$

Implementaciones

El algoritmo Schoof-Elkies-Atkin se implementa en el sistema de álgebra informática PARI/GP en la función GP ellap.

enlaces externos

• "Schoof: Contando puntos en curvas elípticas sobre campos finitos"
• artículo sobre Mathworld
• "Observaciones sobre el algoritmo Schoof-Elkies-Atkin"
• "El algoritmo SEA en la característica 2"