Question sur l'exponentiation rapide
Publié : ven. janv. 11, 2013 9:32 am
Bonjour,
je me pose une question: l'algorithme d'exponentiation rapide (ou binaire) est valable pour une opération dans n'importe quel monoïde.
Est-ce que l'algorithme d'exponentiation modulaire est juste l'exponentation rapide dans l'anneau Z/nZ?
En ce qui concerne la complexité d'exporapide, je peux compter le nombre d'itérations qui est en O(log_2(b)) car partie_entiere(log_2(b))+1 est le nombre de termes dans le développement binaire de b.
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".
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".