Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 13-06-2009 17:05:37
- Golgup
- Membre actif
- Inscription : 09-07-2008
- Messages : 574
[Python] expo modulaire
Bonjour,
Ci dessous un programme d'exponentiation modulaire qui, rappelons le calcul rapidement a^s[n] avec a et s tres grand.(merci à Yoshi pour son aide a la fin
a=input('Entrez la base a:')
s=v=input('Entrez la puissance s:')
n=input ('Entrez le module n:')
f=u=0
t1,t2,t3,p=[],[a],[],-1
j=z=a
while s!=f:
s-=f
c=int(log(s)/log(2))
f=2**c
t1.append(c)
while u!=t1[0]:
z=j**2%n
j=z
u+=1
t2.append(z)
while p<len(t1)-1:
p+=1
t3.append(t2[t1[p]])
print a,'^',v,'(mod',n,')','=', reduce(lambda x, y: x *y, t3)%n
ex:
398739982207337^18385708273137722392365558530530732883 (mod 32401410322810681)=12322382122411856
@+
Dernière modification par Golgup (12-07-2009 17:41:22)
« c’est cette infinité, insondable et obscure, cause des plus vils combats ! … »
Hors ligne
#2 13-06-2009 18:07:27
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 989
Re : [Python] expo modulaire
Bonsoir,
Je viens justement de lire une page où il était fortement déconseillé d'écrire la ch'tite étoile de :
from math import *
- parce qu'on charge inutilement la mule,
- parce qu'on risque des conflits entre nos noms de variables et les mots-clés du module,
- parce qu'on risque des "télecopages" et donc des résultats inattendus.
J'en tiendrai compte à l'avenir : jusque là, ça ne m'avait pas effleuré...
En fait, dans ton prog tu n'as besoin que du log, alors écris :
from math import log
Je note au passage :
p=p+1
prod=prod*i
Plus court : remplacer par p+= 1 et prod*=i
Joli, cela dit !
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#4 13-06-2009 20:41:52
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 989
Re : [Python] expo modulaire
Bonsoir,
Hey Golgup, dans ton autre discussion, je t'ai donné :
L=[1,3,6,2,5,12]
reduce(lambda x, y: x *y,L)
Tu peux supprimer :
for i in t3:
prod*=i
return prod
prod=prod(1,t3)
Et écrire simplement à la place :
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#6 27-06-2011 20:18:52
- ngatilio
- Membre
- Inscription : 18-09-2010
- Messages : 14
Re : [Python] expo modulaire
On peut faire l'exponentiation modulaire avec le pascal 7.0
program exp_modu (input , output);
uses crt;
var
emod , a , b , c : longint;
function exmod ( x , y , z : longint):longint ;
var p , q ,i: longint;
begin
p:= x mod y ;
for i:=1 to p do
begin
q : = z * p ;
end;
exmod := q ;
end;
{appel de l'exponentiation modulaire}
begin
clrscr;
gotoxy(50,20);
Textbackground (5);
write ('on suppose qu'on fait a^(b mod c). Entrer les valeurs de a , b et c :' );
read (a , b , c);
emod : = exmod (b , c , a);
gotoxy(50,20);
write('l''exponentielle modulaire est de :', emod);
read();
end.
Dernière modification par ngatilio (27-06-2011 20:20:36)
Hors ligne
#7 27-06-2011 20:46:15
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 989
Re : [Python] expo modulaire
Bonsoir,
ngatlio bravo...
MAIS,
le sujet commence par [Python], alors pourquoi ne pas ouvrir ta propre discussion avec la mention [Pascal] : ça aurait été sympa, non ?
Quelle est la longueur maxi des longint en Pascal ?
En Python : illimité (c'est la taille de la RAM qui décide).
Ainsi j'ai pu calculer grâce à un artifice les 20000 premières décimales du nombre d'or (temps < 3 s)...
Je peux faire mieux mais j'ai la flemme d'attendre ;-)
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#8 20-07-2011 12:27:36
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 989
Re : [Python] expo modulaire
Re,
Je viens de découvrir que cette fonction était implémentée directement dans Python :
il suffit de taper pow(a,b,[c]), le c étant optionnel et permet (en plus rapide) l'équivalence de pow(a,b)%c
pow(7,4) = 7**4 = 2041 et pow(7,4,9) = (7**4)%9 = 3.
Et voilà qui permet de vérifier, au passage, que le programme de Golgup marche très bien.
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
Pages : 1