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

Niazov

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 \]

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

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

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_

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

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_

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

"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_

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

Mon propos est de dire que trouver l'ordre d'un élément quelconque modulo $N$ est équivalent à savoir retrouver $\varphi(N)$.

++,
Foufoux