je me pose une question: l'algorithme d'exponentiation rapide (ou binaire) est valable pour une opération dans n'importe quel monoïde.
Code : Tout sélectionner
exporapide(a,b):={
si b=0 alors return 1; fsi
si b%2 = 1%2 alors return a*exporapide(a,b div 2)^2;
sinon return exporapide(a,b div 2)^2; fsi
}:;
Code : Tout sélectionner
expomod(a,b,n):={
si b=0 alors return 1; fsi
si b%2 = 1%2 alors return a*exporapide(a,n div 2)^2 mod n;
sinon return exporapide(a,b div 2)^2 mod n; fsi
}:;
Est-ce qu'on peut être plus précis?
Et enfin, n'hésitez pas à me corriger si le code n'est pas très "propre".