Exponentiation modulaire python

Bonsoir,

Pour m'exercer, j'ai programmé une exponentiation modulaire qui est très efficace ( https://fr.wikipedia.org/wiki/Exponentiation_modulaire , dernière méthode exposée).
Pour résumer, il faut convertir l'exposant en binaire et en partant de la droite, faire certaines opérations si on rencontre un 0 ou 1.
Mon code semble fonctionnel (je compare le résultat avec la fonction powmod de gmpy2), cela fonctionne.
Mais cela déraille avec de plus grands nombres, mais parfois aussi avec de plus petits nombres.

Ma question est : ai-je fait une erreur quelque part ou alors c'est la conversion en binaire sur des grands nombres qui ne se fait pas correctement ?

Voici le code :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

import time import gmpy2 from gmpy2 import mpz a=215 b=54 c=10485   exposant=bin(b)[2:] exposant=list(exposant) base=a result=1 start=time.time()   for i in range(int(len(exposant))-1,0,-1): if int(exposant[i])==0: base=pow(base,2) % c else:   result = (base*result) % c base = pow(base, 2) % c end=time.time() print("Méhode 4 : ",end-start," ",result)   start=time.time() nombreb=gmpy2.powmod(a,b,c) end=time.time() print("Méthode 3 : ",end-start," ",nombreb)

---

Si quelqu'un pouvait m'éclairer, merci par avance !

Salut !

int(len(exposant)) pas besoin de mettre un int(), len() renvoie déjà un entier.

Question concernant la ligne 15 :

Code:

---

1 2 3 4 5 6 7 8 9

for i in range(5,0,-1): i     5 4 3 2 1

---

Est-ce que c'est ce que tu souhaites ?
Ou plutôt :

Code:

---

1 2 3 4 5 6 7 8 9 10

for i in range(5,-1,-1): i     5 4 3 2 1 0

---

Bonjour

Citation:

---

Envoyé par LeNarvalo

Est-ce que c'est ce que tu souhaites ?
Ou plutôt :

Code:

---

1 2 3 4 5 6 7 8 9 10

for i in range(5,-1,-1): i     5 4 3 2 1 0

---

---

Bien vu :ccool:
Sauf qu'en réalité ça ne sert à rien du tout. Wikipedia donne un algo présenté comme étant le plus rapide, suffit de l'appliquer sans se poser de questions

Code:

---

1 2 3 4 5 6 7 8 9

def expo(b, e, m): res=1 while e > 0: if e&1: res=(res * b) % m e>>=1 b=b**2 % m # while return res # expo()

---

Même pas besoin de convertir l'exposant en binaire, la conversion se fait implicitement lors de l'évaluation de e&1 puis sa division par 2.
Je l'ai testé sur les nombres de l'exemple (b=4, e=13, m=497) et ça donne le résultat attendu (445).

Citation:

---

Envoyé par blaidddrwg

Pour m'exercer, j'ai programmé une exponentiation modulaire qui est très efficace ( https://fr.wikipedia.org/wiki/Exponentiation_modulaire , dernière méthode exposée).

---

Ben ton code ne ressemblait pas vraiment à ladite dernière méthode exposée...

En dehors du fait qu'il est vraiment vraiment pas performant, il contient au minimum deux inutilités

• exposant=list(exposant) totalement inutile, exposant étant une string, on peut parfaitement itérer dessus sans le transformer en liste. Mais si vraiment tu y tiens, alors autant le mettre en tuple qui est plus léger
• Code:

  ---

  1 2 3 4 5

  if int(exposant[i])==0: base=pow(base,2) % c else: result = (base*result) % c base = pow(base, 2) % c

  ---

  Répéter deux instructions identiques dans le "if" et dans le "else" (avec valeurs de variables identiques elles aussi) c'est une fois de trop...

& et >>= ça fait quoi ?

Je trouve la "Méthode utilisant moins de mémoire" plus explicite :

Code:

---

1 2 3 4

def expo(b, e, m, r = 1): for i in range(0, e): r = (b*r)%m return r

---

Citation:

---

Envoyé par LeNarvalo

& et >>= ça fait quoi ?

---

Oh non!!! Comment peux-tu ignorer cela??????
"&" est un opérateur bit à bit. Il produit un "et" entre chaque bit des opérandes demandés (on place les opérandes écrits en binaire l'un au dessus de l'autre et on fait le "&" sur les bits de chaque colonne). 6&3 donnera 2 (parce que 6 c'est 110 et 3 c'est 011 donc 1&0 fait 0; 1&1 fait 1 et 0&1 fait 0 ce qui donne 010 soit 2).
Dans le cas présent, il sert à détecter la valeur 0 ou 1 du dernier bit de "e"

">>n" (parce que ">>=n" c'est comme "+=n" c'est ">>n" avec affectation) produit un décalage vers la droite de n bits.
Et un décalage vers la droite de n c'est équivalent à une division par 2^n (exemple 14 c'est 1110 ; si je le décale vers la droite de 1 ça donne 0111 soit 7, qui est aussi égal à 14/2)

Donc au résultat, on teste le dernier bit de "e" puis on décale vers la droite ce qui supprime ce dernier bit et place le suivant à sa place. Or tester la valeur binaire du dernier bit puis décaler et supprimer ce dernier bit en le remplaçant par celui placé à sa gauche c'est exactement l'opération qu'on fait quand on convertit un décimal en binaire.

Citation:

---

Envoyé par LeNarvalo

Je trouve la "Méthode utilisant moins de mémoire" plus explicite :

Code:

---

1 2 3 4

def expo(b, e, m, r = 1): for i in range(0, e): r = (b*r)%m return r

---

---

Oui, plus explicite parce que plus simpliste. C'est celle qui utilise le principe que (b*b)%m est égal à ((b%m) * (b%m))%m. Mais mettre le résultat renvoyé en tant que paramètre entrant...8O
Accessoirement on doit pouvoir mettre la boucle et les opérations dans un reduce() mais j'ai pas encore trouvé comment...

Citation:

---

Oh non!!! Comment peux-tu ignorer cela??????

---

Je ne manipule jamais des bits... :ange:

Citation:

---

Mais mettre le résultat renvoyé en tant que paramètre entrant...

---

Ca faisait une ligne en moins, c'est original, n'est-ce pas ? ^^

Citation:

---

Accessoirement on doit pouvoir mettre la boucle et les opérations dans un reduce()...

---

Ca ferait des lignes en moins ! :D :mouarf:

Citation:

---

Envoyé par LeNarvalo

Ca faisait une ligne en moins, c'est original, n'est-ce pas ? ^^

---

8O :zen:

Citation:

---

Envoyé par LeNarvalo

Ca ferait des lignes en moins ! :D :mouarf:

---

Code:

---

1 2 3

from functools import reduce def expo(b, e, m): return reduce(lambda b, r: (b*r)%m, (b,) * e, 1)

---

Un grand merci à la factorielle de tyrtamos, celle qui utilise reduce(), qui m'a beaucoup aidé. J'ai un peu de mal avec cette fonction.

En tout cas, plus je regarde la dernière méthode plus je suis impressionné. En divisant à chaque fois e par 2, ça transforme la complexité O(n) en O(log(n)). Si e vaut 1 267 650 600 228 229 401 496 703 205 376 (2**100), ça ne fera que 100 itérations...:hola:

Citation:

---

Envoyé par LeNarvalo

Salut !

int(len(exposant)) pas besoin de mettre un int(), len() renvoie déjà un entier.

Question concernant la ligne 15 :

Code:

---

1 2 3 4 5 6 7 8 9

for i in range(5,0,-1): i     5 4 3 2 1

---

Est-ce que c'est ce que tu souhaites ?
Ou plutôt :

Code:

---

1 2 3 4 5 6 7 8 9 10

for i in range(5,-1,-1): i     5 4 3 2 1 0

---

---

Bonjour,

Oui c'est cela, j'ai fini par trouver de mon côté, merci pour vos réponses ainsi que pour l'optimisation :D

Bonne journée,