Bonjour à tous !

J'essaye d'appliquer l'algorithme de Pohlig-Hellman pour résoudre un problème de logarithme discret. Le problème, c'est que je travaille sur une courbe elliptique modulaire dont je connais l'équation et le modulo. L'algorithme en question nécessite de connaître une décomposition en facteurs premiers de l'ordre du groupe cyclique dans lequel on travaille.

Existe-t-il un moyen à partir de l'équation de la courbe et du modulo de déterminer l'ordre d'un élément \(P\) donné ?

Merci d'avance !

-
Edité par BunshinKage 27 août 2019 à 18:11:39

Salut !

à ma connaissance, il n'existe pas de méthode très rapide pour ça, je dirais que la méthode, c'est qu'on estime l'ordre de la courbe elliptique avec la formule de Hasse, puis on essaie de voir si par hasard une de ces valeurs estimée n'est pas un multiple de l'ordre de notre point.

Je n'ai pas trop le temps de me pencher dessus, mais tu as un algo qui fait ça https://perso.univ-rennes1.fr/christophe.ritzenthaler/cours/point-counting-ec.pdf page 9, et il me semble aussi que c'est la méthode de sage. Pour en être sûr, il faudrait regarder comment PARI (https://pari.math.u-bordeaux.fr/cgi-bin/gitweb.cgi) fait ça.

En lisant la doc de Sage apparemment il y a des cas où c'est plus rapide : https://www.math.sciences.univ-nantes.fr/~sorger/chow/html/en/reference/plane_curves/sage/schemes/elliptic_curves/ell_point.html#sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field.order

Par curiosité, ton groupe modulaire fait quelle taille ?

En faisant des recherches, j'avais l'impression que ce qui était surtout utilisé était l'algorithme de Schoof (également détaillé dans ton premier lien). L'algorithme SEA est, de ce que j'ai compris, une optimisation de l'algorithme de Schoof en utilisant les nombres premiers d'Atkin, mais je ne me suis pas encore penché dessus (j'essaye déjà de comprendre l'algorithme de Schoof :')).

Je travaille sur une courbe sur \(\mathbb{F}_p\) avec \(p\) de l'ordre de grandeur de \(10^{53}\), je ne suis donc pas motivé à faire un comptage exhaustif :*

Mais ta réponse permet de confirmer que c'est encore l'algorithme qui est utilisé de nos jours, merci ! Maintenant je vais voir si j'utilise sage ou si j'essaye de le recoder à la main

-
Edité par BunshinKage 29 août 2019 à 17:07:56

Ah oui effectivement ça va être long de compter à la main ! Du coup effectivement je n'avais pas vu Schoof.

Bon courage

Edit : c'est pour un challenge type CTF ? Si oui, il est possible que l'ordre soit très faible, ça peut valoir le coup de tenter pour un ordre < 1000000

-
Edité par melepe 29 août 2019 à 11:21:12

C'est bien pour un challenge CTF, c'est pour ça que je suis un peu avare en détails, ça serait dommage que quelqu'un tombe sur le Thread par hasard

Même si l'ordre est faible, le faire me permet d'avoir une boîte à outils, dans le cas improbable où j'en aurai besoin à nouveau pour un autre CTF