Wiki du cours

Rédacteur: Lucile Favero Pistoresi

A traiter [تحرير]

• Idée: utilisation de l'ordre des points en combinaison avec le théorème de Hasse (début de la Section 4.3.3).
• Algorithme "Pas de bébé, pas de géant" pour calculer l'ordre des points.
• Exemples 4.7 et 4.11 pour illustrer la méthode.

But et notation [تحرير]

Présenter, expliquer et appliquer l'algorithme "Pas de bébé, pas de géant" permettant de calculer l'ordre des points d'une courbe elliptique.

On pose : \(E\) une courbe elliptique sur \( F_q \) un corps fini, et \( P\in E ( F_q) \) De plus, \(N\) représentera l'ordre de \(E ( F_q) \) .

Rappel [تحرير]

Théorème de Hasse

L'ordre de \(E ( F_q) \) est : \( | q + 1 − N | ≤ 2\sqrt{q}\)

Corollaire du théorème de Lagrange

L'ordre de \(P\) divise toujours l'ordre de \( E ( F_q) \) .

Algorithme "Pas de bébé, pas de géant" [تحرير]

L'algorithme "Pas de bébé, pas de géant" permet de trouver l'ordre de \(P\).

1. Calculer \( Q = (q +1)P\)
2. Choisir un nombre \(m\) tel que \( m>q^{1/4}\) ;
   Calculer et stocker \( jP, j = 0,1,2, ..., m\)
3. Calculer les points \( Q + k(2mP) , k= -m, ... , m\) jusqu'à ce que l'on ai une correspondance avec un point ( ou son opposé) et un des éléments stocké en 2. ( voir la partie suivante pour l'existence de cette correspondance )
4. Poser \(M= q +1+2mk ∓ j\) On a alors que \( MP = ∞\).
5. Décomposer en facteurs premiers \(M\).
   On nommera \( p_1, ...,p_r\) , les facteurs premiers de M.
6. Calculer \( (M/p_i)P\) pour \( i=1, ...,r\)
   • Si pour au moins un \(i\) on a : \( (M/p_i)P=∞\), remplacer \(M\) par \( (M_i/p_i)\) et refaire l'étape 5.
   • Si pour tout les \(i\) on a : \((M/p_i)P≠∞\), alors \(M\) est l'ordre du point \(P\)

Si on veut trouver l'ordre de \(E ( F_q) \) , il suffit de réitérer les étapes précédentes avec d'autres points de \( E ( F_q) \) , choisis aléatoirement, jusqu'à ce que le ppcm des ordres de ces points divise un unique \(N\) tel que \(q + 1 − 2\sqrt{q} ≤ N ≤ q +1+2\sqrt{q}\) ( cf théorème de Hasse )
Alors \(N\) est l'ordre de \(E ( F_q) \) .

Existence de la correspondance de l’algorithme [تحرير]

Dans l'étape 3 de l'algorithme, on suppose que l'on trouve une correspondance entre \(Q + k(2mP)\) et \(±jP\). Or cette correspondance n'est pas évidente. Prouvons son existence. Pour cela faire, nous aurrons besoin du lemme suivant :
Lemme
Soit \(a\) , un nombre entier tel que \( |a| ≤ 2m^2 \).
Il existe deux entiers, \( a_0, a_1 \in {{-m + 1, ... , m}}\) tels que \( a=a_0 + 2m a_1\)

Nous cherchons à prouver qu'il existe un \(k\) tel que \(Q + k(2mP) = ±jP\)
Avec la notation du lemme et en posant \(a=a_0 +2ma_1\), il suffit de poser \(k=-a_1\) pour avoir l'égalité voulue : \( Q + k(2mP) =(-q+1-2ma_1)P =(q+1-a+a_0)P = NP+a_0P=a_0P= ±jP\)

En quoi l'algorithme calcule l'ordre de \(P\) [تحرير]

Lemme
Soient \(G\) un groupe addictif, \(g \in G\), \( M\) un entier naturel tel que \( Mg = 0\), et \( p_1, ... , p_r\) les nombres premiers de la décomposition en facteur premier de \( M\)
Si \( (M/p_i)g ≠ 0\) pour tout \( i\) , alors l'ordre de \(g\) est \( M\) .
Démonstration
On pose \( k\) l'ordre de g. Nous allons procéder par l'absurde. Pour cela faire, supposons \( k≠M\). Comme \( k\) est l'ordre de g et que par supposition \( Mg = 0\), on a : \(k|M\). De plus si on pose \( p_i\), un nombre premier de la décomposition en facteur premier de \( M/k\), on a que \( p_ik|M\), et donc que \( k|(M/p_i)\). Il en découle que \( (M/p_i)g = 0\), en contradiction avec l'hypothèse de l'énoncé : \( (M/p_i)g ≠ 0\) pour tout \( i\). On en déduit que \( k = M\) \( \blacksquare \)

La situation du lemme est exactement l'action effectuer à l'étape 6 de l'algorithme. Donc l'algorithme donne bien l'ordre de \(P\)

Exemple [تحرير]

Soit \(E\) la courbe elliptique \(y^2 = x^3 −10x+ 21\) sur le corps \(F_{557}\). On cherche \(N\), l'ordre de \(E ( F_{557}) \)

• Calcul de l'ordre de \(P\)
  Appliquons maintenant l'algorithme, pour trouver l'ordre du point \(P (2, 3)\)

1. Calculer \( Q = (q +1)P\)
   Comme dans notre exemple \(q = 557\), on a que \(Q = 558P = (418, 33)\)
2. Choisir un nombre \(m\) tel que \( m>q^{1/4}\) ; On a \(557^{1/4}\), qui vaut environ 4,86. Donc on peut choisir \(m= 5\)
   Calculer et stocker \( jP, j = 0,1,2, ..., m\)
   On a les points suivants : \( ∞, (2, 3), (58, 164), (44, 294), (56, 339), (132, 364)\)
3. Calculer les points \( Q + k(2mP) , k= -m, ... , m\) jusqu'à ce que l'on ai une correspondance avec un point ( ou son opposé) et un des éléments stocké en 2.Quand \( k = 1\), le point \( Q + k(2mP) = (2, 3)\),correspond avec le deuxième point de la liste calculé précédemment. D'où \(j = 1\).
4. Poser \(M= q +1+2mk ∓ j\) On a alors que \( MP = ∞\).
   On a : \( q = 557, m = 5, k = 1, j = 1 \) Donc \(M = 567\) et \(567P = ∞\).
5. Décomposer en facteurs premiers \(M\).
   On nommera \( p_1, ...,p_r\) , les facteurs premiers de M.
   Ici on a : \(M = 567 = 3^4 · 7\)
6. Calculer \( (M/p_i)P\) pour \( i=1, ...,r\)
   
   • Si pour au moins un i on a : \( (M/p_i)P=∞\), remplacer \(M\) par \( (M_i/p_i)\) et refaire l'étape 5.
   • Si pour tout les \(i\) on a : \( (M/p_i)P≠∞\), alors \(M\) est l'ordre du point \(P\) Dans notre cas on a que : \((567/3)P = 189P = ∞\), donc on doit remplacer M par 189 et refaire l'étape 5.
     La décomposition en facteur premier de 189 est \( 3*3^3*7\) , et en calculant \( (M/p_i)P\) pour 3 et 7, on a que :
     \((189/3)P = (38, 535) ≠ ∞ \) , \( (189/7)P =(136, 360) ≠ ∞\)
     

Ainsi, on a que l'ordre de \(P\) est 189.

• Calcul de l'ordre de la courbe

Par le theorème de Hasse on a :
\( | q + 1 − N | ≤ 2√(q)\) avec \(q = 557\) D'où : \(511 ≤ N ≤ 605\)
De plus, en prenant le point \(P(2, 3)\) qui est d'ordre 189, on remarque que l'unique multiple de 189 dans l'intervalle donné par le théorème de Hasse est \(567 ( 3*189 )\) Dans ce cas là, on peut déduire aisément que \(N = 567\).

Références [تحرير]

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