Número de pontos em curva elíptica

Question

Se você tem uma curva elíptica na forma de:

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

Existe um bom programa para calcular o número de pontos nesta curva?

Eu li sobre Schoof de e Schoof-Elkies-Atkin algoritmo (SEA), mas eu estou olhando para implementações de código aberto. Alguém sabe um bom programa que pode fazer isso?

Além disso, se a é 1 e b é 0, o algoritmo SEA não pode ser usado porque o j-invariante é 0. É este correto?

Editar: isto é, no contexto de criptografia de curva elíptica-

Answer 1

Existem alguns links: Implementações de porções do P1363 projecto .

Answer 2

Você já ouviu falar Sábio ?

Sábio inclui Pari, que é um pacote de código aberto para a teoria dos números. Pari tem uma implementação da AAE.

A partir 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

Answer 3

Eu tentei Sage. Levei cerca de 3-4 horas para compilar a ubuntu x64. Parece ser um bom programa. Mas quando o j-invariante é 0 o algoritmo SEA não pode ser usado, e depois parece ter alguns problemas se você usar grandes valores de p / k.

Depois de pesquisar alguns MIRACL mais eu também descobriu: http: // www. shamus.ie/index.php?page=elliptic-curves Eles têm implementações tanto para o Schoof normal e algoritmo SEA. Mas este programa também tem alguns problemas ao usar grandes valores de entrada. Depois de 3-4 horas de executá-lo caiu: /. Tentei corrigi-lo, e atualmente ele está correndo novamente por isso espero que ele irá trabalhar.

Edit: Ele funciona agora. O programa no link acima é idêntico ao Rasmus Faber deu.

Answer 4

Eu tenho usado o programa de Mike Scotts (MIRACL) para esta finalidade também. Sendo apenas curioso posso perguntar: Qual o tamanho eram os domínios com vista privilegiada grupo que poderia produzir com o software? Eu tenho até 1024 bit e agora parar porque eu preciso do meu escritório PC para algo diferente do que correr software contagem de pontos por semanas a fio. Será que quis produzir domínios maiores? Se assim for eu ficaria feliz em obter os parâmetros de domínio e se você não tem objeções seria incluí-los na minha assinatura ECC-Academic Software.

Os meus domínios pode ser encontrada aqui ECC Domínio Página . O software para usá-los com é acessível a partir daqui manual com Link para a página de download

Saudações Michael Anders