Question sur l'exponentiation rapide

Utilisation à l'épreuve de modélisation de l'agrégation de mathématiques

Modérateur : xcasadmin

laurenth
Messages : 5
Inscription : lun. sept. 19, 2011 5:43 pm

Question sur l'exponentiation rapide

Message par laurenth » 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.

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
}:;
Est-ce que l'algorithme d'exponentiation modulaire est juste l'exponentation rapide dans l'anneau Z/nZ?

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
}:;
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".

parisse
Messages : 4842
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Question sur l'exponentiation rapide

Message par parisse » ven. janv. 11, 2013 11:55 am

Oui, l'algo est valable de maniere plus generale que pour calculer dans Z/nZ, mais il n'est pas forcement plus rapide que multiplier b-1 fois par a, parce que tout depend du temps necessaire pour faire une multiplication. Dans le cas de Z/nZ, ce temps est en O(log(n)^2) si la multiplication est naive, independamment de la taille de b, donc le temps de calcul est en O(log(b)*log(n)^2) (ou mieux si on utilise une multiplication plus rapide), contre O(b*log(n)^2). Par contre si a est un polynomes a 1 variable (pas modulo un polynome), c'est deja moins clair qui l'emporte, et en plusieurs variables il vaut mieux faire la multiplication b-1 fois.
Sinon, pour ecrire l'algorithme dans Z/nZ utilise de preference irem a %, car % genere des elements de Z/nZ qui ne sont pas des entiers.

laurenth
Messages : 5
Inscription : lun. sept. 19, 2011 5:43 pm

Re: Question sur l'exponentiation rapide

Message par laurenth » ven. janv. 11, 2013 12:17 pm

Bien reçu! merci :)

Répondre