Soit un groupe dont la loi est
notée multiplicativement. Soit un élément de
et un entier . Pour calculer , on utilise
l'algorithme suivant qui consiste à construire
récursivement des suites
, , où
et
:
1)
Initialisation : on pose , , .
2)
Passage à l'étape : on pose
,
on prend pour le quotient de la division de
par et on pose
3)
Arrêt : quand , l'algorithme s'arrête
et la puissance recherchée est
.
Dans la pratique, on organise les suites
dans
un tableau. Voir les exemples ci-dessous.
Exemples 42
Calculons dans
:
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
.
La première colonne ne dépend que de et nous pouvons
la réutiliser. Dans le tableau suivant, nous utilisons deux
fois la même première colonne pour calculer et
dans
.
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
. Ceci entraînera l'affirmation car pour ,
cette égalité se spécialise en
.
A l'étape , l'affirmation est vraie par définition de l'initialisation
de l'algorithme. Supposons qu'elle est vraie pour l'étape et montrons-la
pour l'étape . Soit
la division euclidienne de
par . Par l'hypothèse de récurrence, nous avons
Si nous substituons le résultat de la division euclidienne pour ,
nous trouvons
Pour la dernière égalité, nous avons utilisé la définition de
et (le nombre est pair ssi ).