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 03-03-2009 10:58:51

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 874

[Python] Calcul de l'inverse modulo n d'un nombre

Bonjour,

Voici le pendant en Python du script de Shengao. Il sera modifié pour boucler sur le choix des nombres...

#!/usr/bin/env python
# -*- coding: cp1252 -*-

def pgcd(a,modulo,pgcd):
    c,d=max(a,modulo),min(a,modulo)   # détermination du Dividende et du diviseur
    while d>0:
        c,d=d,c%d
    pgcd = c
    return pgcd


a,modulo=1572,5441
pgcd=pgcd(a,modulo,1)

if pgcd != 1:
    print "Désolé, votre nombre et le modulo ne sont pas premiers entre eux."
    print "Sélectionner un autre couple de valeurs."
else:
    k=int(5441/1572)+1
    mo=1
    while mo != 0:
        k += 1
        mo = (1 + modulo * k) % a
    print "L'inverse de",a,"modulo",modulo,"est :",((1+modulo*k)/a)%modulo

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#2 10-05-2009 14:02:41

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : [Python] Calcul de l'inverse modulo n d'un nombre

Salut yoshi,
je n'avais pas vu ce programme. Je te propose cette version qui est plus courte et beaucoup plus efficace :

#!/usr/bin/python
# -*- coding: utf-8 -*-

def bezout(a, b):
    ''' Calcule (u, v, p) tels que a*u + b*v = p et p = pgcd(a, b) '''
    if a == 0 and b == 0: return (0, 0, 0)
    if b == 0: return (a/abs(a), 0, abs(a))
    (u, v, p) = bezout(b, a%b)
    return (v, (u - v*(a/b)), p)

def inv_modulo(x, m):
    ''' Calcule y dans [[0, m-1]] tel que x*y % abs(m) = 1 '''
    (u, _, p) = bezout(x, m)
    if p == 1: return u%abs(m)
    else: raise Exception("%s et %s ne sont pas premiers entre eux" % (x, m))


if __name__ == "__main__":
    from sys import argv
    try :
        x, m = int(argv[1]), int(argv[2])
        print "L'inverse de %s modulo %s est : %s" % (x,m,inv_modulo(x,m))
    except Exception, m:
        print m
        print "Merci de choisir un autre couple de valeurs"

[Edit] J'ai ajouté à mon code de quoi le rendre autonome pour répondre à la question de yoshi
Il s'utilise maintenant de la ligne de commande en lui fournissant comme argument le nombre et le modulo. Exemple, si je l'enregistre sous le nom "inv_modulo.py" :

$ ./inv_modulo.py 2 5
L'inverse de 2 modulo 5 est : 3
$ ./inv_modulo.py 2 4
2 et 4 ne sont pas premiers entre eux
Merci de choisir un autre couple de valeurs

++

Dernière modification par Barbichu (10-05-2009 15:23:07)


Barbichu

Hors ligne

#3 10-05-2009 14:37:22

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 874

Re : [Python] Calcul de l'inverse modulo n d'un nombre

Salut,

Intéressant...
Mais est-ce destiné à remplacer un morceau de mon code ? la totalité ? Dans les deux cas d'où appelles-tu tes fonctions ?
D'autre part
1. Tu aurais pu préciser à l'intention de ceux qui te liraient que tu utilises la récursivité,
2. Peux-tu précise le sens du _  fonction inv_modulo ligne 3 ? Je n'ai encore jamais rencontré cette notation.

Merci

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#4 10-05-2009 14:55:28

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : [Python] Calcul de l'inverse modulo n d'un nombre

Re,
C'est sensé remplacer l'integralité de ton code, à condition de rajouter à la fin

a,modulo=1572,5441
print "L'inverse de %s modulo %s est : %s" % (a,modulo,inv_modulo(a,modulo))

et de supprimer toute la partie if __name__ ....

Et sinon
1. Oui, ma fonction bezout est récursive, je pourrais la dérécursifier, mais elle est plus agréable et mieux compréhensible ainsi
2. le "_" est une variable "puits", que je n'utiliserai donc pas. J'aurais très bien pu mettre "v" ou "toto", ce qui aurait mis un nom inutile dans l'espace de nom de ma fonction.

[edit] voila qui devrait te renseigner un peu mieux
++

Dernière modification par Barbichu (10-05-2009 15:18:25)


Barbichu

Hors ligne

#5 10-05-2009 15:33:30

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : [Python] Calcul de l'inverse modulo n d'un nombre

Re,
Un petit benchmark, sur ma machine
./inv_modulo_yoshi.py 10000001 100000000000000 => résultat en 15 secondes
./inv_modulo.py 10000001 100000000000000 => résultat en moins d'1 seconde

./inv_modulo_yoshi.py 100000001 1000000000 => résultat en 2min 12 secondes
./inv_modulo.py 100000001 1000000000; => résultat en moins d'1 seconde

++

Dernière modification par Barbichu (10-05-2009 15:39:52)


Barbichu

Hors ligne

#6 10-05-2009 15:39:59

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 874

Re : [Python] Calcul de l'inverse modulo n d'un nombre

Salut p'tit père,

Ton truc marche peut-être en ligne de commande sous Nunux mais pas sous Windows...
Voilà mes essais :

IDLE 2.6      
>>> $ ./inv_modulo.py 2 5
SyntaxError: invalid syntax
>>>
>>> ./inv_modulo.py 2 5
SyntaxError: invalid syntax
>>>
>>> inv.modulo.py 2 5
SyntaxError: invalid syntax
>>>
>>> import inv_modulo.py
Traceback (most recent call last):
  File "<pyshell#3>", line 1, in <module>
    import inv_modulo.py
ImportError: No module named py
>>>
>>> import inv_modulo
>>> inv_modulo 2 5
SyntaxError: invalid syntax
>>>
>>> inv_modulo.py 2 5
SyntaxError: invalid syntax

Ou alors, je ne comprends pas comment l'utiliser depuis ligne de commande

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#7 10-05-2009 15:46:39

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : [Python] Calcul de l'inverse modulo n d'un nombre

Erf,
Le $ représente le prompt de ma ligne de commande bash. Il faudrait que tu essayes depuis la ligne de commande cmd de windows, mais je ne sais pas si c'est compatible.

Sinon le "import inv_modulo" dans le shell python devrait marcher ... Et d'ailleurs il marche.
Ensuite il faut que tu utilises la fonction python. Donc que tu tapes :

>>> from inv_modulo import inv_modulo
>>> inv_modulo(3,5)

Dernière modification par Barbichu (10-05-2009 15:50:46)


Barbichu

Hors ligne

#8 10-05-2009 15:57:32

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 874

Re : [Python] Calcul de l'inverse modulo n d'un nombre

Re,

J'ai essayé de supprimer le if _main_ et de remplacer : ça colle, mais pas en ligne de commande via le cmd.
J'ai pourtant vu le passage de paramètres à un script Python, via ligne de commande, qq part : faut que je retrouve où j'ai vu ça !

@+

from ... etc marche.
Mais pourquoi mon "import inv_modulo" n'était-il pas suffisant ?
D'autre part, je ne pige pas ton algo ton Bezout, ou alors, il faudrait que je réfléchisse un moment et je n'en ai pas envie ce soir...


Arx Tarpeia Capitoli proxima...

Hors ligne

#9 10-05-2009 16:02:58

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : [Python] Calcul de l'inverse modulo n d'un nombre

Re,
le passage avec if __name__ ... ne sert que pour la ligne de commande shell (et ms-dos si c'est compatible)
(sous ligne de commande ms-dos, il doit falloir faire C:\chemin_complet_vers_python\python inv_modulo.py 2 5)

Par contre pour l'utiliser dans le shell python, il suffit de faire l'import et d'utiliser la fonction, comme une fonction python, grâce au petit bout de code de mon dernier message en exemple ; et je suis certain que ça marche chez toi, vu que "import inv_modulo" a marché dans ton shell python. (Et il n'y a rien à modifier par rapport au fichier que j'ai soumis ici)
++

Dernière modification par Barbichu (10-05-2009 16:06:15)


Barbichu

Hors ligne

#10 10-05-2009 16:15:46

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 874

Re : [Python] Calcul de l'inverse modulo n d'un nombre

'lut,

>>> import inv_modulo
>>> inv.modulo(3,5)

me renvoie ça :
TypeError: 'module' object is not callable

alors que :
>>> from inv_modulo import inv_modulo
>>> inv.modulo(3,5)
2

Python sous Win a l'air de faire la différence entre une "bibliothèque" de scripts, math par ex, et un script de cette bibli comme log, exp...
en faisant from inv_modulo import inv_modulo, ça lève l'objection, même si c'est le même nom...
Une idée plus claire ?

@+

PS

il doit falloir faire C:\chemin_complet_vers_python\python inv_modulo.py 2 5

J'avais essayé avec C:\Python26\python inv_modulo.py 2 5 : ça m'ouvre une fenêtre qui se ferme aussitôt.
J'avais alors essayé d'y glisser raw_input pour l'obliger à attendre : nada ! pas mieux !


Arx Tarpeia Capitoli proxima...

Hors ligne

#11 10-05-2009 16:28:27

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : [Python] Calcul de l'inverse modulo n d'un nombre

Re,
I/
Le "import inv_modulo" importe le fichier inv_modulo.py en temps que module.
Tu peux donc utiliser la fonction inv_modulo en la désignant par inv_modulo.inv_modulo et la fonction bezout en la désignant par inv_modulo.bezout.
Comme on a pas envie de toujours préciser que ça vient du module inv_modulo, on importe chacune des fonctions du module indépendamment.
Par exemple, on peut faire

>>> from inv_modulo import bezout
>>> from inv_modulo import inv_modulo

ou alors les deux d'un seul coup

from inv_modulo import bezout, inv_modulo

[edit> Ça marche pareil avec tous les modules, sous linux comme sous windows.]
[edit2> Ce qui peut aussi prêter à confusion est que le fichier (donc le module) porte le même nom qu'une des fonctions qu'il contient, ce qui peut sembler peu judicieux, mais c'est discutable ...]

II/
Pour l'algo de bezout, c'est celui qu'on fait à la main pour trouver les coefficients de bezout.
On va supposer qu'on ne l'applique que sur les couples a, b tels que [tex]a\geq b[/tex].

Cas de base n°1 : [tex]a=b=0[/tex] => trivial
Cas de base n°2 ; [tex]a>0, b=0[/tex] => [tex]u = 1, v=0[/tex] et [tex]p = a[/tex]
Étape de récurence, [tex]b>0[/tex] et [tex]a \geq b[/tex]
   * soient [tex]q[/tex] et [tex]r < q[/tex] le quotient et le reste dans la div eucl de [tex]a[/tex] par [tex]b[/tex] : on a [tex]a = qb + r[/tex]
   * on applique bezout sur [tex](b,r)[/tex]. (qui est strictement plus petit que [tex](a,b)[/tex] pour l'ordre lexicographique)
        on obtient [tex]u[/tex], [tex]v[/tex] et [tex]p[/tex] tels que [tex]bu+rv=p[/tex] et [tex]\textrm{pgcd}(b,r) = p[/tex]
   * Or [tex]r = a - bq[/tex], donc [tex]bu+(a-bq)v=p[/tex] et  [tex]\textrm{pgcd}(b,a-bq) = p[/tex]
       ou encore : [tex]av + (u-qv)b = p[/tex] et  [tex]\textrm{pgcd}(b,a) = p[/tex]
   * Donc les coefficients de bezout sont [tex]v[/tex] et [tex]u-qv[/tex], et le pgcd est [tex]p[/tex]


III/ Pour conclure, on passe au modulo dans la relation de bezout [tex]xu+mv = 1[/tex]
Ce qui donne : [tex]xu = 1 \mod m[/tex]

Dernière modification par Barbichu (10-05-2009 16:35:34)


Barbichu

Hors ligne

#12 10-05-2009 16:46:05

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 874

Re : [Python] Calcul de l'inverse modulo n d'un nombre

Re,

ok, pour ton point 1. c'est ce que je ressentais...
Point 2.

Barbichu a écrit :

Pour l'algo de bezout, c'est celui qu'on fait à la main pour trouver les coefficients de bezout.

La seule méthode "à la main" que je connaisse est celle que je décris dans cette discussion :
http://www.bibmath.net/forums/viewtopic.php?id=2312
a priori, ça n'y ressemble pas : je vais voir ça de plus près...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#13 10-05-2009 16:51:12

Barbichu
Membre actif
Inscription : 15-12-2007
Messages : 405

Re : [Python] Calcul de l'inverse modulo n d'un nombre

Re, c'est pourtant celle-là même, mais formalisée pour être implémentée. ++

Edit> si je reprends l'exemple du dernier post (#10) du thread que tu m'indiques :
aux lignes 2, 5 9 et 13 de ton calcul, on retrouve le fameux [tex]bu + (a - bq)v[/tex],
et les lignes intermédiaires à ces dernières consistent à mettre le terme sous la forme [tex]av + b(u - qv)[/tex]  ...

Dernière modification par Barbichu (10-05-2009 17:02:25)


Barbichu

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-sept plus neuf
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