Número de puntos en la curva elíptica.

StackOverflow https://stackoverflow.com/questions/407977

  •  03-07-2019
  •  | 
  •  

Pregunta

Si tiene una curva elíptica en forma de:

y ^ 2 = x ^ 3 + a * x + b (mod p)

¿Existe un buen programa para calcular el número de puntos en esta curva?

He leído sobre el algoritmo de Schoof y Schoof-Elkies-Atkin (SEA), pero estoy buscando implementaciones de código abierto. ¿Alguien conoce un buen programa que pueda 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 esto correcto?

Editar: esto está en el contexto de la criptografía de curva elíptica

¿Fue útil?

Solución

Hay algunos enlaces aquí: Implementaciones de partes del borrador P1363 .

Otros consejos

¿Has oído hablar de Sage ?

Sage incluye Pari, que es un paquete de código abierto para la teoría de números. Pari tiene una implementación de SEA.

De http: // wstein.org/papers/2008-bordeaux/sphinx/elliptic_curves.html#schoof-elkies-atkin-point-counting : 

sage: k = GF(next_prime(10^20))
sage: E = EllipticCurve(k.random_element())
sage: E.cardinality()                   # less than a second
100000000005466254167

He intentado Sage. Me tomó alrededor de 3-4 horas compilar en x64 ubuntu. Parece ser un buen programa. Pero cuando el j-invariante es 0, el algoritmo SEA no se puede usar, y luego parece tener algunos problemas si usa valores grandes para p / k.

Después de buscar un poco más, también encontré milagro: http: // www. shamus.ie/index.php?page=elliptic-curves Tienen implementaciones para el algoritmo normal de Schoof y SEA. Pero este programa también tiene algunos problemas al usar valores de entrada grandes. Después de 3-4 horas de ejecución, se bloqueó: /. Traté de arreglarlo, y actualmente se está ejecutando nuevamente, así que espero que funcione.

Editar: funciona ahora. El programa en el enlace de arriba es idéntico al que dio Rasmus Faber.

He estado usando el programa Mike Scotts (milagro) para este propósito también. Siendo curioso, puedo preguntar: ¿Qué tamaño tenían los dominios con orden de grupo principal que podía producir con el software? Obtuve hasta 1024 bits y ahora lo dejé porque necesito mi PC de oficina para algo distinto al software de conteo de puntos de ejecución durante semanas. ¿Produjiste dominios más grandes? De ser así, me complacería obtener los parámetros de dominio y, si no tiene objeciones, los incluiría en mi firma académica de ECC-Software.

Mis dominios se pueden encontrar aquí Página de dominio ECC . El software para usarlos está disponible desde aquí Manual con enlace a la página de descarga

Saludos   Michael Anders

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top