HP Calculatrice graphique HP 39g - Manuel (Page 135)

Calcul de A P mod N 135
fonction puismod (A, P, N)
local PUIS, I
1->PUIS
pour I de 1 a P faire
A*PUIS mod N ->PUIS
fpour
resultat PUIS
ffonction
-Deuxi`eme algorithme
On utilise une seule variable locale PUI mais on fait varier P de fa¸con
qu’`
a chaque ´etape de l’it´eration on ait :
resultat = P U I ∗ A P (mod N )
fonction puismod (A, P, N)
local PUI
1->PUI
tant que
P>0 faire
A*PUI mod N ->PUI
P-1->P
ftantque
resultat PUI
ffonction
-Troisi`eme algorithme
On peut ais´ement modifier ce programme en remarquant que :
A
2 ∗P
= (A
∗ A) P .
Donc quand P est pair on a la relation :
P U I
∗ A P = P U I ∗ (A ∗ A) P/2 (mod N )
et quand P est impair on a la relation :
P U I
∗ A P = P U I ∗ A ∗ A P −1
(mod N ).
On obtient alors un algorithme rapide de A P (mod N ).
fonction puismod (A, P, N)
local PUI
1->PUI
tant que
P>0 faire
si P mod 2 =0 alors
P/2->P
A*A mod N->A
sinon
A*PUI mod N ->PUI
P-1->P
fsi
ftantque