Function ExpoMod(ByVal p As Long, ByVal j As Long, ByVal n As Long) As Long
' EXPONENTIATION MODULAIRE RAPIDE
ExpoMod = 1
Do
If j And 1 Then j = j - 1: ExpoMod = p * ExpoMod
ExpoMod = ExpoMod Mod n
j = j / 2
p = (p * p) Mod n
Loop Until j = 0
End Function
Remarque :
ExpoMod(2,13,5) renvoie 2.
car 2^13 mod 5 => 8192 mod 5 = 1638*5 + 2
function ExpMod(n, e, m: Longword): Longword;
begin
Result := 1; { Initialisation }
while e <> 0 do { Tant que l'exposant n'est pas arrivé à 0 }
begin
if (e and 1) <> 0 then { Si e est impair }
begin
Dec(e); { On décrémente e }
Result := Result * n; { On multiplie le résultat par n }
end;
Result := Result mod m; { On prend le résultat modulo m }
e := e shr 1; { On divise e par deux (décalage binaire ici ) }
n := Sqr(n) mod m; { On effectue l'exponentiation modulaire }
end;
end;
Remarque :
Effectue une exponentiation modulaire de n à la puissance e modulo m.
Attention à ne pas mettre de trop grandes valeurs de n, car si n² > 2^32, la fonction ne va plus fonctionner à cause des limitations du Longword.
Exemple : ExpMod(61, 3, 23) = 17