Wiki du cours

Rédacteur: [Laurane Marco]

A traiter [edit]

• Théorème 4.1 avec preuve.
• Théorème de Hasse sans preuve.
• Détailler des exemples intéressants de courbes elliptiques sur des corps finis, (voir le début de la Section 4.1). Au lieu de 4.3, qui est en caractéristique \(2\), cas que l'on n'a pas étudié, prenez un exemple de courbe de votre choix sur \( F_q, 6 < q < 15 \). Identifiez le groupe sous-jacent et calculez l'appariement de Weil sur quelques points.

Théorèmes [edit]

Théorème 4.1: Soit \(E\) une courbe elliptique sur un corps fini \(F_q\) alors \(E(F_q)≃Z_n\)ou \(E(F_q)≃Z_{n_1}⊕Z_{n_2}\) pour \(n\) entier positif et \(n_1\),\(n_2\) entiers positifs tels que \(n_1\) divise \(n_2\)

Rappels:

(1) Théorème de classification des groupes abéliens finis: Soit \((G, +)\) un groupe abélien fini, alors il existe une unique suite d'entiers positifs \(d_n \geqslant\ d_{n-1} \geqslant\ ... \geqslant\ d_1 \geqslant\ 1\) tel que \(d_i\) divise \(d_{i+1}\) pour tout \(i=1,...,n\) et \(G≃ Z_{d_1}⊕Z_{d_2}⊕ ... ⊕Z_{d_n}\)

(2) Théorème 3.2: Soit \(E\) une courbe elliptique sur un corps K de caractéristique \(p\) et soit \(n\) entier positif alors on a :

• si \(p\) ne divise pas \(n\) ou si \(p=0\) alors \(E[n]≃Z_n⊕Z_n\)
• si \(p>0\) divise \(n\), on pose \(n=p^rm\), \(p\) ne divise pas \(m\) alors \(E[n]≃Z_m⊕Z_m\) ou \(E[n]≃Z_n⊕Z_m\)

Preuve: On sait que \(E(F_q)\) est un groupe abélien fini, par (1) on a que \(E(F_q)≃ Z_{n_1}⊕Z_{n_2}⊕ ... ⊕Z_{n_r}\) pour une unique suite d'entiers positifs \(n_r \geqslant\ n_{r-1} \geqslant\ ... \geqslant\ n_1 \geqslant\ 1\) tel que \(n_i\) divise \(n_{i+1}\) pour tout \(i=1,...,r\). Montrons que \(r \leqslant\ 2 \). Pour chaque \(i\), on a que \(Z_i\) possède \(n_1\) éléments dont l'ordre divise \(n_1\). Donc, \(E(F_q)\) possède \(n_1^r\) éléments dont l'ordre divise \(n_1\). Par (2), on sait qu'il y a au plus \(n_1^2\) éléments de ce type. Donc \(0 \leqslant\ r \leqslant\ 2\). Si \(r=0\), alors \(E(F_q)\) est le groupe trivial et donc on a \(E(F_q)≃Z_1 \) ce qui correspond au théorème avec \(n=1\). Si \(1 \leqslant r \leqslant 2\), alors \(E(F_q)≃Z_n\) ou \(E(F_q)≃Z_{n_1}⊕Z_{n_2}\) avec \(n_1\)divise \(n_2\). \(\Box\)

Théorème 4.2: (Théorème de Hasse) Soit \(E\) une courbe elliptique sur un corps fini \(F_q\). Alors on a que l'ordre de \(E(F_q)\) noté #\(E(F_q) \) satisfait
|\(q+1-\)# \(E(F_q)\)| \( \leqslant\ 2\sqrt{q} \)

La preuve de ce théorème ne sera pas traitée dans ce séminaire. On peut noter que le théorème ne donne pas le nombre exact de point sur la courbe mais plutôt un encadrement. Cependant, pour des applications cryptographiques connaître le nombre exact de points est utile. En utilisant ce théorème on peut construire des algorithmes qui permettent de calculer le nombre exact de points.

Exemples [edit]

Exemple 4.1 : Considérons la courbe elliptique \(E: y^2=x^3+x+1\) sur le corps \(F_5\). On commence par lister les points de \(E(F_5)\). Dans le tableau suivant, toutes les opérations sont simplifiées modulo 5.

A chaque fois pour trouver la valeur de y on se demande: existe-il \(y\in F_5\) tel que \(y^2=x^3+x+1\) ? Par exemple, dans la deuxième ligne on n'a pas de valeur pour y car 3 n'est pas un carré dans \(F_5\). Les carrés modulo 5 sont uniquement 0,1 et 4.

On a que l'ordre de \(E(F_5)\) est 9. On sait que c'est un groupe abélien fini donc par le théorème 4.1 on a que \(E(F_5)≃Z_9\)ou \(E(F_5)≃Z_{3}⊕Z_{3}\) car ce sont les seuls groupes abéliens d'ordre 9 à isomorphisme près. Montrons qu'en fait \(E(F_5)≃Z_9\). On va montrer qu'il est cyclique de générateur \((0,1)\).

On va utiliser les formules pour la loi de groupe dérivées au sujet 4.

Rappel:

• Pour calculer \(2P_1\) où \(P_1=(x_1,y_1)\) on a \(m=(3x_1^2+A)(2y_1)^{-1}\) et \( x=m^2-2x_1 ,y=m(x_1-x)-y_1 \)
• Pour calculer \(P_1+P_2\) où \(P_1=(x_1,y_1), P_2=(x_2,y_2)\) on a \(m=(y_2-y_1)(x_2-x_1)^{-1}\) et \( x=m^2-x_1-x_2, y=m(x_1-x)-y_1 \)

\(2(0,1)=?\)
On calcule \(m=(3\cdot 0 +1)(2)^{-1}\). On cherche l'inverse multiplicatif de 2 dans \(F_5\), on a \(2\cdot 3=6 \equiv 1 mod(5) \)
Donc \(m=1 \cdot3 =3\) d'où \(x=3^2 -2\cdot 0 =9 \equiv 4 mod(5)\) et \(y=3(0-4)-1=-13 \equiv 2 mod(5)\)
Donc \(2(0,1)=(4,2)\).
Maintenant, calculons \(3(0,1)=(0,1)+2(0,1)=(0,1)+(4,2)\). On a \(m=(2-1)(4-0)^{-1}\) et l'inverse multiplicatif de 4 dans \(F_5\) est 4.
D'où \(m=4\) et donc \(x=4^2-0-4=12 \equiv 2 mod(5)\) et \(y=4(0-2)-1=-9 \equiv 1 mod(5)\)
Donc \(3(0,1)=(2,1)\). Par des calculs similaires, on trouve : \(4(0,1)=(3,4), 5(0,1)=(3,1), 6(0,1)=(2,4), 7(0,1)=(4,3), 8(0,1)=(0,4), 9(0,1)= \infty \) Donc on a bien que \(E(F_5)\) est un groupe abélien cyclique d'ordre 9 et donc \(E(F_5)≃Z_9\).

Autre exemple: Considérons la courbe elliptique \(E: y^2= x^3+3x-1\) sur le corps fini \(F_7\) On commence par lister les points de \(E(F_7)\). Dans le tableau suivant, toutes les opérations sont simplifiées modulo 7.

[1] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Section 4.1