Ordre Multiplicatif

L'ordre multiplicatif de $ a $ modulo $ n $ est le plus petit entier strictement positif $ k $ tel que $ a^k \equiv 1 \pmod{n} $.

L'ordre multiplicatif mesure la longueur du cycle parcouru par un nombre élevé à ses puissances successives modulo un autre nombre. Élever un entier $ a $ à des puissances successives modulo un entier $ n $ finit toujours par retomber sur 1, à condition que $ a $ et $ n $ soient premiers entre eux. Les puissances $ a^1, a^2, a^3, \ldots $ décrivent un cycle fermé dans l'ensemble des résidus modulo $ n $, et l'ordre est la longueur de ce cycle : c'est l'analogue arithmétique de la période d'une fonction périodique.

Soit $ n \geq 2 $ et $ a $ un entier inversible modulo $ n $, c'est-à-dire premier avec $ n $. L'ordre multiplicatif de $ a $ modulo $ n $, noté $ \operatorname{ord}_n(a) $, est défini par $ \operatorname{ord}_n(a) = \min\{k \in \mathbb{N}^* : a^k \equiv 1 \pmod{n}\} $.

Si $ a $ et $ n $ partagent un facteur commun, alors $ a^k $ reste divisible par ce facteur pour tout $ k $, et $ a^k \bmod n $ ne vaut jamais 1 : l'ordre n'existe pas. La condition $ \pgcd(a, n) = 1 $ garantit au contraire que $ a $ possède un inverse modulo $ n $, et le petit théorème de Fermat ainsi que le théorème d'Euler assurent que $ a^{\varphi(n)} \equiv 1 \pmod{n} $ : l'ensemble des exposants valides n'est donc jamais vide, et un minimum existe toujours.

C'est une conséquence directe du théorème de Lagrange : dans un groupe fini, l'ordre d'un élément divise l'ordre du groupe.

Or le groupe $ (\mathbb{Z}/n\mathbb{Z})^* $ compte exactement $ \varphi(n) $ éléments, où $ \varphi $ est l'indicatrice d'Euler.

Ainsi $ \operatorname{ord}_n(a) $ divise $ \varphi(n) $.

Lorsque $ \operatorname{ord}_n(a) = \varphi(n) $, l'élément $ a $ parcourt à lui seul tout le groupe des inversibles : $ a $ est une racine primitive (ou générateur) modulo $ n $, et le groupe est cyclique.

Autrement dit, les puissances de $ a $ engendrent tous les inversibles, chacun exactement une fois par tour de cycle.

L'algorithme peut se résumer à :

fonction ordre_multiplicatif(a, n)

si pgcd(a, n) ≠ 1 → renvoyer "ordre non défini"

e ← φ(n) # via la factorisation de n

factoriser e = ∏ p_i^{e_i} # factorisation de φ(n)

pour chaque facteur premier p de e →

tant que e mod p = 0 et a^(e/p) ≡ 1 (mod n) :

e ← e / p

renvoyer e

Ou en code Python : def ordre_multiplicatif(a, n):

if math.gcd(a, n) != 1:

return None

e = phi(n)

for p in facteurs_premiers(e):

while e % p == 0 and pow(a, e // p, n) == 1:

e //= p

return e

Le logarithme discret est le problème inverse de l'exponentiation : étant donnés $ g $ et $ g^x \bmod p $, retrouver $ x $.

L'ordre multiplicatif est le garde-fou de plusieurs protocoles.

Pour RSA : si l'exposant de chiffrement partagait un petit ordre avec certains messages, des cycles courts apparaîtraient et rendraient le texte chiffré prévisible ; la sécurité suppose implicitement des ordres grands et mal connus.

Pour l'échange de clés Diffie-Hellman : la sécurité repose sur un générateur de grand ordre premier, choisir un sous-groupe de petit ordre permettrait de dérober des secrets.

Pour ElGamal et DSA : mêmes exigences, l'ordre du générateur doit être un grand premier, souvent un diviseur premier $ q $ de $ p - 1 $.

Globalement, une règle d'or : tout élément de petit ordre est une faille cryptographique.