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,