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 19-10-2018 13:18:38

Zazoux60
Membre
Inscription : 19-10-2018
Messages : 1

système de congruences

Bonjour à tous,

mon problème est tout simple: peut-on résoudre le système:

a^x mod n = 1
b^x mod n = 1
c^x mod n = 1 ?

Je sait que seulement une des ces conditions n'est pas suffisante pour trouver facilement une solution, et que le problème avec une seule equation s'apparente au problème du logarithme discret, qui est reputé difficile a resoudre, mais d'adjonction de plusieurs equations simplifie elle la situation ?
exemple concret : 2^x mod 77 = 1, 3^x mod 77 = 1, 5^x mod 77 = 1, avec solution x = 30.
Pour moi ce problème resemble vaguement au théorème chinois des restes, mais je peut me tromper.
J'ajoute également que n est arbitraire, donc eventuèllement premier, ou composé de deux ou plusieur facteurs inconnus. Sur d'autres sites j'ai trouvé la solution pour le cas ou les facteurs de n sont connus d'avance, maintenant si ça sera possible d'avoir une solution plus générale, tant mieux.

merci en avance pour tout commentaire ou suggestion ou réference bibliographique

cordialement

Dernière modification par Zazoux60 (21-10-2018 17:33:59)

Hors ligne

#2 28-10-2018 19:14:59

Rossignol
Membre
Inscription : 19-06-2015
Messages : 290

Re : système de congruences

Bonjour Zazoux60,

Une solution de votre système, très facile à trouver, est $x=0$.
Mais j'ai comme l'intuition que ce n'est pas ce que vous attendez :-)

On cherche une solution strictement positive.

Si $a$ est premier avec le module $n$, on a d'après Euler $a^{\phi(n)}\equiv 1\pmod{n}$ où $\phi$ est l'indicatrice d'Euler.

Pour votre exemple numérique $\phi(77) = (7-1)(11-1)=60$ donc $a^{60}\equiv 1 \pmod{77}$ pour tout $a$ premier avec $77$.

Si on veut un résultat amélioré, on peut utiliser l'indicatrice de Carmichael $\lambda$.

$\lambda(77) = \mathrm{ppcm}\,(7-1, 11-1) = 30$ donc $a^{30}\equiv 1 \pmod{77}$ si $a$ est premier avec $77$.

L'égalité $a^{\lambda(n)}\equiv 1 \pmod{n}$ est vraie pour tout $a$ qui est premier avec le module, donc prendre plusieurs équations n'apporte rien de plus.

Si $a$ n'est pas premier avec $n$ alors l'équation $a^{x}\equiv 1\pmod{n}$ n'a pas d'autre solution que $0$.

Pour un $a$ particulier, ce qu'il est intéressant de connaitre, c'est le plus petit exposant strictement positif $m$ tel que $a^m\equiv 1 \pmod{n}$ : c'est l'ordre multiplicatif de $a$ modulo $n$ ; on le note $\mathrm{ord}_n(a)$.

$\mathrm{ord}_n(a)$ est la période de l'exponentielle de base $a$ modulo $n$.

Par exemple, $\mathrm{ord}_{77}(13) = 10$ donc les solutions de l'équation $13^x\equiv 1 \pmod{77}$ sont $x=10k$ pour $k\in\mathbb{Z}$.

Le calcul de l'ordre multiplicatif n'est pas simple. On peut utiliser la propriété suivante qui découle du théorème des restes chinois.

Si $n = n_1 n_2$ avec $n_1$ et $n_2$ premiers entre eux, alors pour $a$ premier avec $n$, on a

$$\mathrm{ord}_n(a) = \mathrm{ppcm}(\mathrm{ord}_{n_1}(a), \mathrm{ord}_{n_2}(a))$$

En décomposant $n$ en facteurs premiers, on est ramené à trouver l'ordre pour des puissances de nombres premiers. On peut trouver cet algorithme exprimé dans différents langages de programmation ici.

On trouve un autre algorithme dans le Handbook of Applied Cryptography Chapitre 4 algorithme 4.79.

Le principe est simple : puisque $\mathrm{ord}_{n}(a)$ est un diviseur de $\phi(n)$, la décomposition de $\phi(n)$ en facteurs premiers permet de trouver la décomposition de $\mathrm{ord}_{n}(a)$.

Voilà une version en Python de cet algorithme :

# coding: utf-8

def Factorise(n):
    """Retourne la decomposition de n en facteurs premiers sous la forme
       d'un dic {facteur_premier: exposant}
    """

    f = {}            # hash p --> exposant
    p = 2             # diviseur à tester
    while n > 1:
        if n % p == 0:
            if p in f:
                f[p] += 1
            else:
                f[p] = 1
            n //= p
        else:
            if p == 2:
                p = 3
            else:
                p += 2
    return f

def pgcd(a, b):
    """Retourne le pgcd des entiers a et b
    """

    while b != 0:
        a, b = b, a % b
    return a

def phi(a):
    """Indicatrice d'Euler.
       phi(n) = nombre d'entier de [1..n] premiers avec n
    """

    f = Factorise(a)
    r = a
    for p in f:
        r //= p
        r *= p-1
    return r

def ZnOrder(a, n):
    """Retourne l'ordre multiplicatif de a modulo n
       (retourne 0 si a n'est pas premier avec n)
    """

    if pgcd(a, n) != 1:
        return 0
    t = phi(n)
    h = Factorise(t)
    for p in h:
        t = t//(p**h[p])
        a1 = pow(a, t, n)
        while a1 != 1:
            a1 = pow(a1, p, n)
            t = t*p
    return t

print(ZnOrder(17, 10**20-1)) # 1499522760

Pour ces deux algorithmes il est nécessaire de déterminer la décomposition de $n$ en facteurs premiers, ce qui n'est pas toujours possible dans un temps raisonnable si les facteurs premiers sont très grands.

Je ne connais pas d'algorithme permettant de calculer l'ordre multiplicatif sans connaitre la décomposition du module en facteurs premiers.

Néanmoins, Antoine Joux dans son livre Algorithmic Cryptanalysis donne page 216 une méthode pour trouver l'ordre du groupe en utilisant le logarithme discret. C'est tout à fait théorique, car les algorithmes de calcul du logarithme discret (comme Pohlig-Hellman) utilisent l'ordre du groupe. On tourne en rond.

Voilà tout ce que je connais sur le sujet.

@+

P.S. Pour les nostalgiques du bon vieux temps où il n'y avait pas d'ordinateurs, je renvoie à la table des Haupt-Exponents de Cunningham :-)

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