Nombre de points sur la courbe elliptique

Question

Si vous avez une courbe elliptique sous la forme de:

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

Existe-t-il un bon programme pour calculer le nombre de points sur cette courbe?

J'ai lu des articles sur l'algorithme de Schoof et Schoof-Elkies-Atkin (SEA), mais je recherche des implémentations open source. Quelqu'un connaît-il un bon programme capable de le faire?

De plus, si a vaut 1 et b vaut 0, l'algorithme SEA ne peut pas être utilisé car le j-invariant est 0. Est-ce correct?

Modifier: il s’agit de la cryptographie à courbe elliptique

Answer 1

Il y a quelques liens ici: Implémentations de parties du brouillon P1363 .

Answer 2

Avez-vous entendu parler de Sage ?

Sage inclut Pari, un package open source pour la théorie des nombres. Pari a implémenté 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

Answer 3

J'ai essayé Sage. Il m'a fallu environ 3-4 heures pour compiler ubuntu x64. Cela semble être un bon programme. Mais quand le j-invariant est 0, l'algorithme SEA ne peut pas être utilisé, et il semble y avoir quelques problèmes si vous utilisez de grandes valeurs pour p / k.

Après avoir cherché un peu plus, j'ai également trouvé miracl: http: // www. shamus.ie/index.php?page=elliptic-curves Ils ont des implémentations pour les algorithmes normaux de Schoof et SEA. Mais ce programme rencontre également des problèmes lors de l’utilisation de valeurs d’entrée importantes. Après 3-4 heures de fonctionnement, il s'est écrasé: /. J'ai essayé de le réparer et, actuellement, il fonctionne à nouveau, donc j'espère que cela fonctionnera.

Edit: Cela fonctionne maintenant. Le programme dans le lien ci-dessus est identique à celui donné par Rasmus Faber.

Answer 4

J'utilise aussi le programme Mike Scotts (miracl) à cette fin. Étant simplement curieux, puis-je demander: Quelle est la taille des domaines avec ordre de groupe principal que vous pouvez produire avec le logiciel? Je me suis levé à 1024 bits et j'ai arrêté car j'ai besoin de mon ordinateur de bureau pour autre chose que de faire fonctionner un logiciel de comptage de points pendant des semaines. Avez-vous produit de plus grands domaines? Si tel est le cas, je serais heureux d’obtenir les paramètres de domaine et, si vous n’avez pas d’objections, incluez-les dans ma signature académique ECC-Software.

Mes domaines peuvent être trouvés ici Page de domaine ECC . Le logiciel permettant de les utiliser est accessible à partir d'ici Manuel avec lien vers la page de téléchargement

Cordialement   Michael Anders