Stampa

Sujet 15: Courbes elliptiques sur les corps finis II: comptage de points

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