ordre d'un élément dans (Z/nZ)*
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 \]
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
-
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 ! -
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,+,*)$. -
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)}$ -
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). -
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 -
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.
-
"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 -
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) -
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!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 63 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 313 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres