Algorithme de calcul rapide des puissances

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 .

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