El algoritmo de Schoof-Elkies-Atkin (SEA) es un algoritmo que se utiliza 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 la criptografía de curva elíptica . El algoritmo es una extensión del algoritmo de Schoof por 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 primosconsiderado como primos de cierto tipo. Estos llegaron a llamarse números 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 una prima de Atkin es una prima que no es una prima 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 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 utilizar polinomios modulares alternativos pero con el mismo propósito).
Si el polinomio instanciado tiene una raíz en luego es un primo de Elkie, y podemos calcular un polinomio cuyas raíces corresponden a puntos en el núcleo de la -isogenia de a . El polinomioes un divisor del polinomio de división correspondiente utilizado en el algoritmo de Schoof, y tiene un grado significativamente menor, versus . Para los números primos de Elkies, esto permite calcular el número de puntos en modulo más eficientemente que en el algoritmo de Schoof. En el caso de un primo de Atkin, podemos obtener alguna información del patrón de factorización de en , que restringe las posibilidades para el número de puntos módulo , pero la complejidad asintótica del algoritmo depende completamente de los números primos de Elkies. Siempre que haya suficientes números primos de Elkies pequeños (en promedio, esperamos que la mitad de los primospara ser primos de Elkies), esto da como resultado una reducción en el tiempo de ejecución. El algoritmo resultante es probabilístico (del tipo de Las Vegas ) y su tiempo de ejecución esperado es, heurísticamente,, haciéndolo más eficiente en la práctica que el algoritmo de Schoof. Aquí elLa notación es una variante de la notación O grande que suprime los términos logarítmicos en el término principal de una expresión.
Implementaciones
El algoritmo de Schoof-Elkies-Atkin se implementa en el sistema de álgebra computacional PARI / GP en la función GP ellap.