Un aspecto importante en el estudio de las curvas elípticas es idear formas efectivas de contar puntos en la curva . Ha habido varios enfoques para hacerlo, y los algoritmos ideados han demostrado ser herramientas útiles en el estudio de diversos campos como la teoría de números y, más recientemente, en criptografía y autenticación de firma digital (Ver criptografía de curva elíptica y DSA de curva elíptica ). Si bien en la teoría de números tienen importantes consecuencias en la resolución de ecuaciones diofánticas , con respecto a la criptografía, nos permiten hacer un uso efectivo de la dificultad del problema del logaritmo discreto. (DLP) para el grupo , de curvas elípticas sobre un campo finito , donde q = p k y p es un primo. El DLP, como se le conoce, es un enfoque ampliamente utilizado para la criptografía de clave pública , y la dificultad para resolver este problema determina el nivel de seguridad del criptosistema. Este artículo cubre algoritmos para contar puntos en curvas elípticas sobre campos de características grandes, en particular p > 3. Para curvas sobre campos de características pequeñas , existen algoritmos más eficientes basados en métodos p -ádicos.
Enfoques para contar puntos en curvas elípticas
Hay varios enfoques del problema. Comenzando con el enfoque ingenuo, rastreamos los desarrollos hasta el trabajo definitivo de Schoof sobre el tema, mientras que también enumeramos las mejoras al algoritmo de Schoof realizadas por Elkies (1990) y Atkin (1992).
Varios algoritmos hacen uso del hecho de que los grupos de la forma están sujetos a un teorema importante debido a Hasse, que limita el número de puntos a considerar. El teorema de Hasse establece que si E es una curva elíptica sobre el campo finito, entonces la cardinalidad de satisface
Enfoque ingenuo
El enfoque ingenuo para contar puntos, que es el menos sofisticado, implica recorrer todos los elementos del campo. y probar cuáles satisfacen la forma de Weierstrass de la curva elíptica
Ejemplo
Sea E la curva y 2 = x 3 + x + 1 sobre. Para contar puntos en E , hacemos una lista de los posibles valores de x , luego de los residuos cuadráticos de x mod 5 (solo para fines de búsqueda), luego de x 3 + x + 1 mod 5, luego de y de x 3 + x + 1 mod 5. Este rendimientos los puntos de E .
Puntos | ||||
---|---|---|---|---|
Por ejemplo, la última fila se calcula de la siguiente manera: Si inserta en la ecuación usted obtiene como resultado (tercera columna). Este resultado se puede lograr si( Los residuos cuadráticos se pueden buscar en la segunda columna). Entonces los puntos para la última fila son.
Por lo tanto, tiene cardinalidad de 9: los 8 puntos enumerados antes y el punto en el infinito.
Este algoritmo requiere un tiempo de ejecución O ( q ), porque todos los valores de debe ser considerado.
Paso de bebé paso gigante
Se obtiene una mejora en el tiempo de ejecución utilizando un enfoque diferente: elegimos un elemento seleccionando valores aleatorios de Hasta que es un cuadrado en y luego calcular la raíz cuadrada de este valor para obtener . El teorema de Hasse nos dice que yace en el intervalo . Así, según el teorema de Lagrange , encontrar un único mintiendo en este intervalo y satisfaciendo , resulta en encontrar la cardinalidad de . El algoritmo falla si existen dos enteros distintos y en el intervalo tal que . En tal caso, suele ser suficiente repetir el algoritmo con otro punto elegido al azar en.
Probar todos los valores de para encontrar el que satisfaga toma alrededor pasos.
Sin embargo, al aplicar el algoritmo de pasos gigantes para, podemos acelerar esto pasos. El algoritmo es como sigue.
El algoritmo
1. elige entero, 2. PARA { a } HACER 3. 4. ENDFOR 5. 6. 7. REPETIR calcula los puntos 8. HASTA : \\la -se comparan las coordenadas9. \\Nota 10. Factor . Dejar ser los distintos factores primos de .11. MIENTRAS HACER 12. SI 13. ENTONCES 14. ELSE 15. ENDIF 16. ENDMientras tanto 17. \\Nota es el orden del punto 18. MIENTRAS divide más de un entero en 19. DEBE elegir un nuevo punto y vaya a 1.20. FINALIZAR 21. REGRESO \\ es la cardinalidad de
Notas al algoritmo
- En la línea 8. asumimos la existencia de una coincidencia. De hecho, el siguiente lema asegura que existe tal coincidencia:
- Dejar ser un entero con . Existen enteros y con
- Informática una vez se ha calculado se puede hacer agregando a en lugar de calcular de nuevo la multiplicación escalar completa. Por tanto, el cálculo completo requiere adiciones. se puede obtener con una duplicación de . El cálculo de requiere duplicaciones y adiciones, donde es el número de dígitos distintos de cero en la representación binaria de ; tenga en cuenta que el conocimiento de la y nos permite reducir el número de duplicaciones. Finalmente, para llegar de a , simplemente agrega en lugar de volver a calcular todo.
- Asumimos que podemos factorizar . Si no, al menos podemos encontrar todos los pequeños factores primos y comprueba eso para éstos. Luegoserá un buen candidato para la orden de.
- La conclusión del paso 17 se puede demostrar utilizando la teoría de grupos elemental: ya que , el orden de divide . Si no hay divisor adecuado de se da cuenta , luego es el orden de .
Un inconveniente de este método es que se necesita demasiada memoria cuando el grupo crece. Para solucionar este problema, podría ser más eficaz almacenar solo los coordenadas de los puntos (junto con el número entero correspondiente ). Sin embargo, esto conduce a una multiplicación escalar extra para elegir entre y .
Existen otros algoritmos genéricos para calcular el orden de un elemento de grupo que son más eficientes en el espacio, como el algoritmo rho de Pollard y el método canguro de Pollard . El método canguro de Pollard permite buscar una solución en un intervalo prescrito, lo que da como resultado un tiempo de ejecución de, utilizando espacio.
Algoritmo de Schoof
Un avance teórico para el problema de calcular la cardinalidad de grupos del tipo Fue logrado por René Schoof, quien, en 1985, publicó el primer algoritmo determinista de tiempo polinomial. En el algoritmo de Schoof es fundamental el uso de polinomios de división y el teorema de Hasse , junto con el teorema del resto chino .
La intuición de Schoof explota el hecho de que, según el teorema de Hasse, existe un rango finito de valores posibles para . Basta con calcular módulo un entero . Esto se logra computando modulo primos cuyo producto excede y luego aplicando el teorema del resto chino. La clave del algoritmo es usar el polinomio de división. para calcular de manera eficiente modulo .
El tiempo de ejecución del algoritmo de Schoof es polinomio en , con una complejidad asintótica de , dónde denota la complejidad de la multiplicación de enteros . Su complejidad espacial es.
Algoritmo de Schoof-Elkies-Atkin
En la década de 1990, Noam Elkies , seguido de AOL Atkin, ideó mejoras en el algoritmo básico de Schoof al hacer una distinción entre los números primosque se utilizan. Un primo se llama primo de Elkies si la ecuación característica del endomorfismo de Frobenius, , se divide . De lo contrariose llama prima de Atkin. Los números primos de Elkies son la clave para mejorar la complejidad asintótica del algoritmo de Schoof. La información obtenida de los primos de Atkin permite una mejora adicional que es asintóticamente insignificante pero que puede ser bastante importante en la práctica. La modificación del algoritmo de Schoof para utilizar números primos de Elkies y Atkin se conoce como algoritmo de Schoof-Elkies-Atkin (SEA).
El estado de una prima en particular depende de la curva elíptica , y se puede determinar utilizando el polinomio modular . Si el polinomio univariado tiene una raíz en , dónde denota el invariante j de, luego es una prima de Elkies, y por lo demás es una prima de Atkin. En el caso de Elkies, se utilizan cálculos adicionales que involucran polinomios modulares para obtener un factor adecuado del polinomio de división.. El grado de este factor es, mientras que tiene grado .
A diferencia del algoritmo de Schoof, el algoritmo SEA generalmente se implementa como un algoritmo probabilístico (del tipo de Las Vegas ), de modo que la búsqueda de raíces y otras operaciones se puedan realizar de manera más eficiente. Su complejidad computacional está dominada por el costo de calcular los polinomios modulares, pero como estos no dependen de , pueden calcularse una vez y reutilizarse. Bajo el supuesto heurístico de que hay suficientes números primos de Elkies pequeños, y excluyendo el costo de calcular polinomios modulares, el tiempo de ejecución asintótico del algoritmo SEA es, dónde . Su complejidad espacial es, pero cuando se utilizan polinomios modulares precalculados, esto aumenta a .
Ver también
Bibliografía
- I. Blake, G. Seroussi y N. Smart: curvas elípticas en criptografía , Cambridge University Press, 1999.
- A. Enge: Curvas elípticas y sus aplicaciones a la criptografía: Introducción . Editores académicos Kluwer, Dordrecht, 1999.
- G. Musiker: algoritmo de Schoof para contar puntos en . Disponible en http://www.math.umn.edu/~musiker/schoof.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
- LC Washington: Curvas elípticas: teoría de números y criptografía. Chapman \ & Hall / CRC, Nueva York, 2003.