ordre d'un élément dans (Z/nZ)*

Niazov
Niazov
dans Arithmétique
Bonjour,

je voulais savoir s'il existe une formule, ou un moyen (autre qu'algorithmique) pour déterminer l'ordre d'un élément du groupe des inversibles de $\Z / n \Z$.
Autrement dit, si $u$ est premier à $n$, trouver le plus petit $k$ tel que
\[u^k \equiv 1 \mod n \]

Réponses

  • rakam
    rakam
    Bonjour !
    Je pense que les coefficients de Bézout $\alpha,\beta$ associés à $u,n$ donneraient la solution. Si $\alpha u+\beta n=1$ tu as TOUTES les solutions de $xu+yn=1$ en faisant la différence soit $u(x-\alpha)+n(y-\beta)=0$. Tu utilises ensuite le théorème de Gauss et tu choisis le plus petit $x$ qui t'arrange !
  • Niazov
    Niazov
    Bonjour Rakam,

    Je ne souhaite pas calculer l'ordre d'un élément du goupe additif $(\Z / n \Z,+)$, auquel cas ta méthode est correcte, mais l'ordre d'un élément du goupe multiplicatif constitué par les inversibles de l'anneau $(\Z / n \Z,+,*)$.
  • Foufoux
    Foufoux
    De façon général,
    Soit C un groupe cyclique à n éléments et soit a un générateur de C.
    Alors pour tout $q \in Z$, l ordre de $a^q$ est $\frac{n}{pgcd(n,q)}$
  • Alban_
    Alban_
    Bonjour, la réponse de Foufoux ne permet que de tourner en rond : vu la question de Niazov, il s'agit maintenant de déterminer q tel que $u = a^q$.

    En fait, il me semble qu'il n'y a pas de moyen de faire rapidement ce que Niazov demande : cela ne doit pas être loin du problème du logarithme discret qui n'a pas de solution rapide (il y a quand même des choses : algorithme rho de Pollard, baby-step/giant-step de Shanks, etc).
  • Foufoux
    Foufoux
    Bonjour,

    Tout à fait d'accord, la formule que je donne n'avance à rien dans le cas général mais permet pour certains $u$ (par exemple cas $q=1$) d'avoir l'ordre rapidement.

    Cependant, il est clair que trouver une méthode générale qui n'a pas un cout algorithme monstrueux, revient alors à casser mathématiquement (entre autre) RSA...

    Je doute donc qu'une telle méthode existe (et encore moins qu'elle soit publiée :))

    ++,
    Foufoux
  • Alban_
    Alban_
    Foufoux : est-ce que tu peux expliquer pourquoi tu dis qu'avoir un algorithme rapide pour déterminer q tel que $u = a^q$ permet de casser RSA ? Pour moi, cela permet de résoudre le problème du logarithme discret mais je ne vois pas le lien avec RSA, qui est basé sur la difficulté de factoriser.
  • Foufoux
    Foufoux
    "Casser RSA" est souvent résumé à savoir factoriser des grands nombres...
    Une fois que tu as factorisé l'exposant public (généralement nommé N), que fait-il faire pour déchiffrer un message ?

    ++
    Foufoux
  • Alban_
    Alban_
    Une fois que l'on a la factorisation N = pq, on a aussi e qui est public (je ne pense pas que ma notation soit standard, c'est l'entier premier avec (p - 1)(q - 1) choisi par celui qui a généré la clé), donc il suffit de calculer la clé privée d avec $d e \equiv 1 \mod (p - 1)(q - 1)$, ce qui se fait rapidement par l'algorithme d'Euclide.
    Enfin, on intercepte un message de la forme $t = x^e$ modulo n destiné à celui dont la clé publique est (N,e) et on calcule $t^d$ modulo n, ce qui donne le message x ?

    Je ne vois pas où intervient ce log discret (ou quelque chose d'approchant)
  • Foufoux
    Foufoux
    Mon propos est de dire que trouver l'ordre d'un élément quelconque modulo $N$ est équivalent à savoir retrouver $\varphi(N)$.

    ++,
    Foufoux
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

Qui est en ligne 6

Azothceline_Letanche +3 Invités