L'inverse Modulo

Mastic
Mastic
dans Arithmétique
Bonsoir,

Je ne sais pas comment calculer l'inverse mod d'un nombre par exemple : trouver l'inverse de 39 mod 53

J'aimerai bien que quelqu'un m'explique la méthode parfaitement, & me donner un exemple

Merci..

Réponses

  • Auteur
    Auteur
    Tu cherches n, tel que 39n soit congru à 1 modulo 53, c'est à dire que 39n-1 est un multiple de 53, c'est à dire tel qu'il existe k, 39n-1=53k, soit 1=39n-53k. L'identité de Bézout te dit qu'il existe n et k vérifiant cette relation, car 1 est le pgcd de 39 et 53, et l'algorithme d'Euclide étendu te donne la procédure pour trouver une paire.
  • Fin de partie
    Fin de partie
    Mastic:

    A quel niveau étudies-tu?

    Sais-tu résoudre en nombres entiers une équation à deux inconnues du type ax+by=1 où a,b sont deux entiers donnés qui n'ont pas facteurs communs hormis 1?
  • Mastic
    Mastic
    Fin de partie

    Deuxième année génie informatique
    Pour répondre à ta question, je sais très bien résoudre une équation à deux inconnues, mais pour ce cas e ne sais pas d'où commencer

    [Inutile de répéter le message précédent. AD]
  • Fin de partie
    Fin de partie
    Pour répondre à ta question, je sais très bien résoudre une équation à deux inconnues, mais pour ce cas j'sais pas d'où commencer a écrit:

    Que penses-tu des solutions de l'équation (en particulier les valeurs de x) 39x+53y=1 ?
  • Mastic
    Mastic
    Fin de partie

    La division euclidienne ? C'est facile alors
  • nicolas.patrois
    nicolas.patrois
    C’est la version étendue.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Mastic
    Mastic
    Merci les gars
  • Juan
    Juan
    Dans le cadre des problèmes du project Euler, j'ai souvent à calculer des inverses modulo $n$ sur ordinateur. Pour cela, j'utilise toujours le théorème d'Euler qui stipule que, si $a$ et $n$ sont premiers entre eux $a^{\varphi (n)} \equiv 1 [n]$. On a donc que l'inverse de $a$ modulo $n$ est $a^{\varphi (n)-1} [n]$.
    À condition de connaître la décomposition en facteurs premiers de $n$, ce calcul me paraît peu coûteux en utilisant l'exponentiation modulaire. N'étant spécialiste ni d'arithmétique ni d'informatique, je ne sais pas si cette méthode est meilleure que l'algorithme d'Euclide étendu.
    Quelqu'un aurait-il un avis éclairé sur la question ?
    Merci
  • nicolas.patrois
    nicolas.patrois
    Je pense que le calcul de phi(n) est plus lourd que l’algorithme d’Euclide, mais mon niveau 4 au projet ne me donne pas l’autorité pour l’affirmer. :D
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Juan
    Juan
    Je supposais que l'on connaissait la décomposition en facteurs premiers de $n$ (c'est vrai que c'est une restriction). Dans ce cas-là, le calcul de $\varphi(n)$ est assez rapide ...
  • Fin de partie
    Fin de partie
    Mon niveau 5 ne me donne pas autorité non plus pour répondre définitivement à la question. :D
    Mais je penche néanmoins en faveur de l'algorithme d'Euclide étendu
    (on peut aussi se contenter d'une recherche en mode bourrin)
  • Juan
    Juan
    Merci à tous les deux. Je vais changer de ce pas ma fonction Python.
  • Aleg
    Aleg
    Bonsoir,

    Une possibilité en Python : 
    # deux fonctions arithmétiques pour trouver l'inverse de a modulo q

def bezout(p,q): #fct récursive qui renvoie (g,x,y) tq ax+by=g (=pgcd(a,b))
    if p==0:
        return (q,0,1)
    else:
        g,y,x=bezout(q%p,p)
        return (g,x-(q//p)*y,y)

def invmod(a): #inverse modulaire de a modulo q
    g,x,y=bezout(a,q)
    if g!=1:
        raise Exception('pas inversible')
    else:
        return x%q

    (heu..; petit pb : sur le forum, les indentations ne passent pas..!)
    [Mais si, il faut seulement utiliser les commandes adéquates. ;) AD]
  • Juan
    Juan
    Merci beaucoup

    PS il manque juste de déclarer q comme variable dans la seconde fonction.
  • Fin de partie
    Fin de partie
    Sous GP-PARI:
    Mod(39,53)^{-1}
  • Guego
    Guego
    Sous maple : 
    > (1/39) mod 53;
                                      34

    Sous python, j'utilise également l'algo d'Euclide étendu :
    def invmod(n,p):
	(n1,p1,u1,u2)=(n,p,1,0)
	while p1>0:
		q=n1/p1
		(n1,p1,u1,u2)=(p1,n1-q*p1,u2,u1-q*u2)
	return (u1%p)

    Ce qui donne : 
    >>> print(invmod(39,53))
34
  • vquesnoit
    vquesnoit
    Pour le cas de python, le plus rapide est pow(n,mod-2,mod) car l'exponentiation modulaire est O(log(puissance)) et elle est en C. cela évite de factoriser pour calculer phi. Dans d'autres langages, Euclide est probablement plus rapide.
  • Dom
    Dom
    [small]Que signifient ces histoires de "niveau" ?[/small]
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Français