Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 13-06-2009 16: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

from math import log

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 16:41:22)


« c’est cette infinité, insondable et obscure, cause des plus vils combats ! … »

Hors ligne

#2 13-06-2009 17:07:27

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 944

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

#3 13-06-2009 17:21:16

Golgup
Membre actif
Inscription : 09-07-2008
Messages : 574

Re : [Python] expo modulaire

Voila!

@+


« c’est cette infinité, insondable et obscure, cause des plus vils combats ! … »

Hors ligne

#4 13-06-2009 19:41:52

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 944

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  :

def prod(prod,t3):
    for i in t3:
        prod*=i
    return prod
prod=prod(1,t3)

Et écrire simplement à la place :

prod=reduce(lambda x, y: x *y, t3)

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#5 13-06-2009 21:40:58

Golgup
Membre actif
Inscription : 09-07-2008
Messages : 574

Re : [Python] expo modulaire

Voilà qui est fait ; )


« c’est cette infinité, insondable et obscure, cause des plus vils combats ! … »

Hors ligne

#6 27-06-2011 19: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 19:20:36)

Hors ligne

#7 27-06-2011 19:46:15

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 944

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 11:27:36

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 944

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

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
quatre-vingt dix-huit plus cinquante cinq
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums