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 = PUI ∗ 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 :
PUI ∗A
P
= PUI ∗(A ∗ A)
P/2
(mod N)
et quand P est impair on a la relation :
PUI ∗A
P
= PUI ∗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
Comentários a estes Manuais