Premiers pas

Consulter l'aide de la commande EllipticCurve. Définir la courbe elliptique $E$ d'équation $y^2 = x^3 + x^2 - x$ sur le corps $\mathbb Q$.

On accède à l'aide en évaluant : EllipticCurve? . L'aide détaille la syntaxe de cette commande. Pour construire la courbe ci-dessus, on fait :

{{{id=3| E = EllipticCurve([0,1,0,-1,0]) /// }}} {{{id=1| E /// Elliptic Curve defined by y^2 = x^3 + x^2 - x over Rational Field }}}

Par défaut, cette courbe a été construite sur le corps $\mathbb Q$.

Tracer le graphe de la courbe $E$ dans le plan (utiliser la commande plot).

{{{id=5| plot(E) /// }}}

Définir un point $P$ de votre choix dans $E(\mathbb Q)$.

On voit que, par exemple, le couple $(1,1)$ satisfait l'équation de la courbe. Comme il est à coordonnées dans $\mathbb Q$, cela définit un point de $E(\mathbb Q)$. La commande suivante de Sage le créé.

{{{id=8| P = E((1,1)) P /// (1 : 1 : 1) }}}

On aurait aussi pu faire :

{{{id=10| P = E.point((1,1)) P /// (1 : 1 : 1) }}}

Représenter $P$ et $E$ sur le même dessin (la commande + permet de les superposer).

Pour mieux distinguer le point $P$, on choisit de changer sa taille et sa couleur.

{{{id=12| plot(E) + plot(P,size=50,color='red') /// }}}

Courbes elliptiques sur un corps fini

Définir la courbe elliptique $E$ d'équation $y^2 = x^3 + x+1$ sur le corps fini $\mathbb F_5$.

Le corps fini à $5$ éléments se fabrique dans Sage par la commande GF(5), ou encore FiniteField(5).

{{{id=14| E = EllipticCurve(GF(5),[1,1]) E /// Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 5 }}}

Grâce à l'aide contextuelle (touche TAB après le nom de l'objet suivi d'un point), calculer le discriminant de $E$.

L'aide contextuelle suggère la commande .discriminant

{{{id=17| E.discriminant() /// 4 }}}

Calculer l'ensemble $E(\mathbb F_5)$ des points de $E$ (regarder la commande .points).

{{{id=19| E.points() /// [(0 : 1 : 0), (0 : 1 : 1), (0 : 4 : 1), (2 : 1 : 1), (2 : 4 : 1), (3 : 1 : 1), (3 : 4 : 1), (4 : 2 : 1), (4 : 3 : 1)] }}}

Pour compter combien il y a de points, on peut demander à Sage la longueur de cette liste.

{{{id=21| len(E.points()) /// 9 }}}

Vérification de la structure de groupe commutatif

SageMath permet d'additionner des points sur une courbe elliptique grâce à la commande +. Vérifier à l'aide de SageMath que $(E(\mathbb F_5),+)$ vérifie bien les axiomes d'un groupe commutatif.

Commençons par vérifier que la loi est associative. On appelle L la liste des points.

{{{id=26| L = E.points() /// }}} {{{id=23| for P in L: for Q in L: for R in L: if P+(Q+R) != (P+Q)+R: print("non") /// }}}

Le programme ci-dessus compare $P+(Q+R)$ à $(P+Q)+R$ pour chaque triplet de points $P,Q,R$ sur la courbe, et affiche "non" si ces quantités diffèrent.

Ainsi la loi est bien associative.

Vérifions que le point à l'infini $O = (0,1,0)$ est bien un élément neutre. Pour cela on compare $P+O$ et $P$ pour tout point $P$ sur la courbe.

{{{id=31| O = E(0,1,0) /// }}} {{{id=25| [ P + O == P for P in L ] /// [True, True, True, True, True, True, True, True, True] }}}

On fait de même avec $O+P$ et $P$.

{{{id=29| [ O + P == P for P in L ] /// [True, True, True, True, True, True, True, True, True] }}}

Montrons que tout élément admet un opposé.

Dans Sage, l'opposé du point $P$ s'obtient par $-P$. On vérifie simplement que $P+(-P)=O$, et de même pour $(-P)+P$.

{{{id=32| [P+(-P) == E(0,1,0) for P in L] /// [True, True, True, True, True, True, True, True, True] }}} {{{id=34| [(-P)+P == E(0,1,0) for P in L] /// [True, True, True, True, True, True, True, True, True] }}}

Enfin on vérifie que la loi est commutative.

{{{id=35| for P in L: for Q in L: if P+Q != Q+P: print("non") /// }}}

Le programme ci-dessus affiche "non" dès qu'il rencontre un couple $(P,Q)$ avec $P+Q \neq Q+P$.

Calculer l'ordre de chacun des points de $E(\mathbb F_5)$ et la structure de groupe sur $E(\mathbb F_5)$ (regarder la commande .abelian_group).

{{{id=37| E.abelian_group() /// Additive abelian group isomorphic to Z/9 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 5 }}}

Sage nous dit que le groupe $E(\mathbb F_5)$ est donc un groupe abélien cyclique, isomorphe à $\mathbb Z / 9 \mathbb Z$.

Calculons maintenant l'ordre de chaque élément à l'aide de la commande .order

{{{id=40| [ (P,P.order()) for P in L] /// [((0 : 1 : 0), 1), ((0 : 1 : 1), 9), ((0 : 4 : 1), 9), ((2 : 1 : 1), 3), ((2 : 4 : 1), 3), ((3 : 1 : 1), 9), ((3 : 4 : 1), 9), ((4 : 2 : 1), 9), ((4 : 3 : 1), 9)] }}}

On voit qu'il existe au moins un élément d'ordre 9, ce qui corrobore le fait que le groupe est cyclique d'ordre 9.

Pour chacune des équations suivantes :
$y^2=x^3+2x$
$y^2=x^3+2x+1$
$y^2 = x^3 +2$
vérifier que ce sont des équations de courbes elliptiques sur $\mathbb{F}_5$. Pour chacune de ces courbes, déterminer le groupe $E(\mathbb{F}_5)$ et discuter la structure.

{{{id=42| E = EllipticCurve(GF(5),[2,0]) E E.abelian_group() /// Additive abelian group isomorphic to Z/2 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 5 }}} {{{id=45| E = EllipticCurve(GF(5),[2,1]) E E.abelian_group() /// Additive abelian group isomorphic to Z/7 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x + 1 over Finite Field of size 5 }}} {{{id=46| E = EllipticCurve(GF(5),[0,2]) E E.abelian_group() /// Additive abelian group isomorphic to Z/6 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field of size 5 }}}

Trouver 5 courbes elliptiques sur $\mathbb F_5$ telles que $\# E(\mathbb F_5) $ vaut respectivement $2,3,5,7,8$.

On peut parcourir tous les couples $(a,b)$ dans $\mathbb F_5\times \mathbb F_5$ jusqu'à trouver une équation de courbe qui convienne.

{{{id=47| for a in GF(5): for b in GF(5): Disc = 4*a^3+27*b^2 if Disc != 0: E = EllipticCurve(GF(5),[a,b]) print (E,E.abelian_group()) /// (Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 5, Additive abelian group isomorphic to Z/6 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field of size 5, Additive abelian group isomorphic to Z/6 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 5, Additive abelian group isomorphic to Z/6 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 5, Additive abelian group isomorphic to Z/6 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 4 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 5, Additive abelian group isomorphic to Z/2 + Z/2 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 5, Additive abelian group isomorphic to Z/9 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 5, Additive abelian group isomorphic to Z/4 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + x + 3 over Finite Field of size 5, Additive abelian group isomorphic to Z/4 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 3 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + x + 4 over Finite Field of size 5, Additive abelian group isomorphic to Z/9 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + x + 4 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 5, Additive abelian group isomorphic to Z/2 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + 2*x + 1 over Finite Field of size 5, Additive abelian group isomorphic to Z/7 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x + 1 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + 2*x + 4 over Finite Field of size 5, Additive abelian group isomorphic to Z/7 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 2*x + 4 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 5, Additive abelian group isomorphic to Z/10 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 3*x over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + 3*x + 2 over Finite Field of size 5, Additive abelian group isomorphic to Z/5 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 3*x + 2 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + 3*x + 3 over Finite Field of size 5, Additive abelian group isomorphic to Z/5 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 3*x + 3 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 5, Additive abelian group isomorphic to Z/4 + Z/2 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 4*x over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + 4*x + 1 over Finite Field of size 5, Additive abelian group isomorphic to Z/8 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 4*x + 1 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + 4*x + 2 over Finite Field of size 5, Additive abelian group isomorphic to Z/3 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 4*x + 2 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + 4*x + 3 over Finite Field of size 5, Additive abelian group isomorphic to Z/3 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 4*x + 3 over Finite Field of size 5) (Elliptic Curve defined by y^2 = x^3 + 4*x + 4 over Finite Field of size 5, Additive abelian group isomorphic to Z/8 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 4*x + 4 over Finite Field of size 5) }}}

Dans cette liste, les courbes suivantes répondent à la question posée :

$y^2 = x^3+2x$ ($\# E(\mathbb F_5) = 2$)

$y^2 = x^3+4x+2$ ($\# E(\mathbb F_5) = 3$)

$y^2 = x^3 + 3x+ 3$ ($\# E(\mathbb F_5) = 5$)

$y^2 = x^3 + 2x+4$ ($\# E(\mathbb F_5) =7$)

$y^2 = x^3 + 4x + 4$ ($\# E(\mathbb F_5) = 8$)

Revenons à la courbe d'équation $y^2 = x^3 + x+1$ sur $\mathbb F_5$. Sans utiliser la commande .points, déterminer à l'aide de SageMath et par une méthode naïve l'ensemble des points $E(\mathbb F_5)$. Comparer ce résultat à celui obtenu par SageMath.

{{{id=50| E = EllipticCurve(GF(5),[1,1]) E /// Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 5 }}}

On détermine tous les points de $E(\mathbb F_5)$ de manière naïve en cherchant toutes les solutions $(x,y)$ de l'équation dans $\mathbb F_5 \times \mathbb F_5$ (et en n'oubliant pas le point à l'infinii $O$).

{{{id=54| L = [] # creation d'une liste vide dans laquelle les points seront stockes for x in GF(5): for y in GF(5): if y^2-(x^3+x+1) == 0: L.append(E(x,y)) # la commande append permet d'ajouter un élément à la fin d'une liste existante /// }}} {{{id=56| L /// [(0 : 1 : 1), (0 : 4 : 1), (2 : 1 : 1), (2 : 4 : 1), (3 : 1 : 1), (3 : 4 : 1), (4 : 2 : 1), (4 : 3 : 1)] }}} {{{id=57| len(L) /// 8 }}} {{{id=58| len(E.points()) /// 9 }}}

On compare aux points obtenus par Sage.

{{{id=59| E.points() /// [(0 : 1 : 0), (0 : 1 : 1), (0 : 4 : 1), (2 : 1 : 1), (2 : 4 : 1), (3 : 1 : 1), (3 : 4 : 1), (4 : 2 : 1), (4 : 3 : 1)] }}}

Ce sont bien les mêmes.

Même question pour la courbe elliptique sur le corps $\mathbb F_{3571}$ définie par  $y^2 =  x^3 + x+2$.

{{{id=61| E = EllipticCurve(GF(3571),[1,2]) E /// Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 3571 }}} {{{id=63| %time L = [] for x in GF(3571): for y in GF(3571): if y^2-(x^3+x+2) == 0: L.append(E(x,y)) /// CPU time: 56.70 s, Wall time: 56.74 s }}}

Le temps nécessaire à ce calcul est assez long... Comparons avec la méthode déjà existante dans Sage.

{{{id=64| %time L = E.points() /// CPU time: 0.01 s, Wall time: 0.01 s }}}

Cette fonction est beaucoup plus rapide ! Elle repose sur des algorithmes pointus et performants de calcul de points de courbes elliptiques sur les corps finis.

{{{id=65| /// }}}