Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
140 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 
Algorithme de calcul rapide des puissances next up previous contents
suivant: Calcul de l'ordre badm3 monter: bad précédent: Notion d'ordre d'un élément   Table des matières

Algorithme de calcul rapide des puissances


Soit $ G$ un groupe dont la loi est notée multiplicativement. Soit $ g$ un élément de $ G$ et $ n$ un entier $ \geq 2$. Pour calculer $ g^n$, on utilise l'algorithme suivant qui consiste à construire récursivement des suites $ x_k, y_k, q_k$, $ k\geq 1$, où $ x_k, y_k \in G$ et $ q_k \in {\mbox{\bf N}}$ :

1)
Initialisation : on pose $ x_1=g$, $ y_1=e$, $ q_k=n$.
2)
Passage à l'étape $ k$ : on pose $ x_k=x_{k-1}^2$, on prend pour $ q_k$ le quotient de la division de $ q_{k-1}$ par $ 2$ et on pose

\begin{displaymath}
y_k= \left\{
\begin{array}{cc} y_{k-1} & \mbox{si $q_{k-1}$...
...} y_{k-1} & \mbox{si $q_{k-1}$ est impair}
\end{array}\right.
\end{displaymath}

3)
Arrêt : quand $ q_k=1$, l'algorithme s'arrête et la puissance recherchée est $ g^n=x_k y_k$.
Dans la pratique, on organise les suites $ x_k, y_k, q_k$ dans un tableau. Voir les exemples ci-dessous.

Exemples 42   Calculons $ 2^{50}$ dans $ ({\mbox{\bf Z}}/101{\mbox{\bf Z}})^*$ :
$ k$ $ x_k$ $ y_k$ $ q_k$
1 2 1 50
2 4 1 25
3 16 4 12
4 54 4 6
5 88 4 3
6 68 49 1
    100  
Nous trouvons donc que $ 2^{50} \equiv -1 \; (101)$. La première colonne ne dépend que de $ g=2$ et nous pouvons la réutiliser. Dans le tableau suivant, nous utilisons deux fois la même première colonne pour calculer $ 3^{50}$ et $ 3^{20}$ dans $ ({\mbox{\bf Z}}/101{\mbox{\bf Z}})^*$.
$ x_k$ $ y_k$ $ q_k$ $ y_k$ $ q_k$
3 1 50 1 20
9 1 25 1 10
81 9 12 1 5
97 9 6 81 2
16 9 3 81 1
54 43 1    
  100   84  

Lemme L'algorithme décrit ci-dessus est correct.


Démonstration. Nous allons montrer par récurrence que nous avons $ x_k^{q_k} y_k=g^n$. Ceci entraînera l'affirmation car pour $ q_k=e$, cette égalité se spécialise en $ x_k y_k=g^n$.

A l'étape $ k=1$, l'affirmation est vraie par définition de l'initialisation de l'algorithme. Supposons qu'elle est vraie pour l'étape $ k-1$ et montrons-la pour l'étape $ k$. Soit $ q_{k-1}= 2  q_k+r_k$ la division euclidienne de $ q_{k-1}$ par $ 2$. Par l'hypothèse de récurrence, nous avons

$\displaystyle x_{k-1}^{q_{k-1}} y_{k-1}=g^n.
$

Si nous substituons le résultat de la division euclidienne pour $ q_{k-1}$, nous trouvons

$\displaystyle g^n= x_{k-1}^{2  q_k +r_k}y_{k-1} = (x_{k-1}^2)^{q_k} (x_{k-1}^{r_k}) y_{k-1}
= x_k^{q_k} y_k.
$

Pour la dernière égalité, nous avons utilisé la définition de $ x_k$ et $ y_k$ (le nombre $ q_{k-1}$ est pair ssi $ r_k=0$). $ \surd$


next up previous contents
suivant: Calcul de l'ordre badm3 monter: bad précédent: Notion d'ordre d'un élément   Table des matières
Bernhard_Keller
 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page