cryptography - historia - Número de puntos en la curva elíptica
elliptic curve cryptography (4)
Si tienes una curva elíptica en la forma de:
y ^ 2 = x ^ 3 + a * x + b (mod p)
¿Hay un buen programa para calcular el número de puntos en esta curva?
He leído sobre el algoritmo Schoof''s y Schoof-Elkies-Atkin (SEA), pero estoy buscando implementaciones de código abierto. ¿Alguien sabe un buen programa que puede hacer esto?
Además, si a es 1 yb es 0, el algoritmo SEA no se puede usar porque el j-invariante es 0. ¿Es correcto?
Editar: esto es en el contexto de la criptografía de curva elíptica
¿Has oído hablar de Sage ?
Sage incluye Pari, que es un paquete de código abierto para teoría de números. Pari tiene una implementación de SEA.
sage: k = GF(next_prime(10^20))
sage: E = EllipticCurve(k.random_element())
sage: E.cardinality() # less than a second
100000000005466254167
Aquí hay algunos enlaces: Implementaciones de porciones del borrador P1363 .
Lo intenté con Sage. Me tomó alrededor de 3-4 horas para compilar x64 ubuntu. Parece ser un buen programa. Pero cuando el j-invariante es 0, el algoritmo SEA no se puede utilizar, y luego parece tener algunos problemas si usa valores grandes para p / k.
Después de buscar un poco más, también encontré miracl: http://www.shamus.ie/index.php?page=elliptic-curves Tienen implementaciones para el algoritmo Schoof y SEA normal. Pero este programa también tiene algunos problemas cuando se usan valores de entrada grandes. Después de 3-4 horas de funcionamiento se bloqueó: /. Traté de solucionarlo, y actualmente está funcionando nuevamente, así que espero que funcione.
Editar: Funciona ahora. El programa en el enlace de arriba es idéntico al que Rasmus Faber dio.
He estado usando el programa de Mike Scotts (miracl) para este propósito también. Siendo simplemente curioso, me pregunto: ¿Cuán grandes fueron los dominios con orden de primer grupo que podría producir con el software? Llegué a 1024 bits y ahora lo dejo porque necesito mi PC de oficina para algo más que ejecutar el software de recuento de puntos durante semanas. ¿Has producido dominios más grandes? De ser así, me gustaría obtener los parámetros del dominio y, si no tiene objeciones, los incluiría en la firma académica de ECC-Software.
Mis dominios se pueden encontrar aquí ECC Domain Page . El software para usarlos es accesible desde aquí Manual con Enlace a la página de descarga
Saludos Michael Anders