Multiples modulo n, liste circulaire et inverse modulaire

L'inverse de a modulo n est un entier a' tel que a × a' ≡ 1 [n] ; il existe si et seulement si a et n sont premiers entre eux, c'est-à-dire si PGCD(a, n) = 1. Par exemple, l'inverse de 7 modulo 26 est 15, car 7 × 15 = 105 = 4 × 26 + 1. Cette condition découle d'une propriété au programme du BTS SIO : modulo n, les multiples de a sont exactement les multiples de PGCD(a, n). Ce chapitre explique cette propriété, son application au parcours d'une liste circulaire par sauts, puis le calcul de l'inverse modulaire et la résolution d'équations du type a × x ≡ b [n], indispensable pour déchiffrer un message.

Les multiples de a modulo n

Calcule les multiples de 8 et réduis-les modulo 12 :

Modulo 12, les multiples de 8 ne prennent que trois valeurs : 0, 4 et 8. Ce sont exactement les multiples de 4, et 4 = PGCD(8, 12).

Avec 5 au lieu de 8 :

Cette fois, on obtient tous les restes de 0 à 11, chacun une fois. Ce sont les multiples de 1 = PGCD(5, 12).

Et avec 9 : 0, 9, 18 ≡ 6, 27 ≡ 3, 36 ≡ 0… les multiples de 9 modulo 12 sont 0, 3, 6 et 9, les multiples de 3 = PGCD(9, 12).

Pourquoi ? Deux choses sont à montrer.

1. Un multiple de a, réduit modulo n, est un multiple de d. Le reste r de a × k dans la division par n s'écrit r = a × k − n × q. Or d divise a et d divise n, donc d divise r.
2. Tout multiple de d est atteint. Reprends l'algorithme d'Euclide pour PGCD(8, 12) : 12 = 8 × 1 + 4, donc 4 = 12 − 8 × 1. Chaque reste de l'algorithme s'écrit ainsi comme « un multiple de n plus un multiple de a », et c'est vrai du dernier, d. Modulo n, le multiple de n disparaît : d est congru à un multiple de a. Ici, 4 ≡ −8 ≡ 8 × 11 [12] (vérification : 8 × 11 = 88 = 7 × 12 + 4). Une fois d atteint, ses multiples le sont aussi : 2d ≡ a × 2u, 3d ≡ a × 3u…

Le programme n'exige pas cette démonstration, mais il faut savoir utiliser la propriété, souvent sous la forme d'un parcours circulaire.

Parcourir une liste circulaire par sauts

Une liste circulaire de n éléments est une liste dont le dernier élément est suivi du premier, comme les positions d'un cadran. On la parcourt par sauts d'amplitude constante a : on part de la position 0, puis on avance de a positions à chaque étape, modulo n. Après k sauts, on est en position a × k mod n : les positions visitées sont les multiples de a modulo n.

D'après la propriété :

Exemple. Une équipe de 12 techniciens, numérotés de 0 à 11, assure une astreinte le week-end. Pour ne pas solliciter des voisins de bureau d'affilée, le responsable désigne chaque semaine le technicien situé 8 rangs plus loin que le précédent. Avec des sauts de 8, seuls les techniciens 0, 8 et 4 sont désignés, et toujours les mêmes : PGCD(8, 12) = 4, et 12 ÷ 4 = 3. Avec des sauts de 5, premier avec 12, les 12 techniciens sont désignés à tour de rôle avant que le cycle recommence.

On retrouve ce mécanisme en informatique :

• Tables de hachage à adressage ouvert. Quand la case calculée pour une donnée est occupée, on essaie la case située s positions plus loin, puis encore s plus loin, modulo la taille m de la table. Pour être sûr de trouver une case libre s'il en reste une, il faut que s et m soient premiers entre eux ; c'est l'une des raisons pour lesquelles on choisit souvent une taille m première.
• Parcourir des éléments dans un ordre mélangé sans en oublier ni en répéter : avancer par sauts d'un pas premier avec le nombre d'éléments (pour une playlist, un jeu de questions, une liste de serveurs à tester).
• Engrenages, horloges et calendriers : une roue de 12 dents entraînée par sauts de 8 ne présente que 3 positions.

L'inverse modulo n

Dans la table de multiplication modulo 5 du chapitre 8, chaque ligne non nulle contient un 1 : 2 × 3 ≡ 1 [5]. On dit que 3 est l'inverse de 2 modulo 5.

C'est une conséquence directe de la propriété : 1 est un multiple de a modulo n si et seulement si 1 est un multiple de d = PGCD(a, n), c'est-à-dire si d = 1.

• 7 a un inverse modulo 26, car PGCD(7, 26) = 1 : c'est 15 (7 × 15 = 105 ≡ 1 [26]).
• 9 a un inverse modulo 26 : c'est 3 (9 × 3 = 27 ≡ 1 [26]).
• 13 n'a pas d'inverse modulo 26 : PGCD(13, 26) = 13. Ses multiples modulo 26 ne valent que 0 ou 13.
• Modulo un nombre premier p, tout entier non multiple de p a un inverse.

L'inverse joue le rôle de la division : multiplier par l'inverse de a modulo n revient à « diviser par a » modulo n. C'est ce qui permet de déchiffrer un message codé par chiffrement affine.

Calculer un inverse modulaire

Méthode 1 : essayer les multiples. On calcule a × 1, a × 2, a × 3… modulo n, jusqu'à obtenir 1. Pour l'inverse de 7 modulo 26 :

C'est exactement l'algorithme demandé au sujet de l'E3 de la session 2026, écrit en pseudo-code :

Fonction inverse(a)
    c ← 1
    Tant que reste(a × c, 26) ≠ 1 faire
        c ← c + 1
    Fin Tant que
    Renvoyer c

Attention : cet algorithme ne s'arrête jamais si a n'a pas d'inverse. Il faut vérifier avant que PGCD(a, 26) = 1.

Raccourci de tête : cherche parmi 1 + 26 = 27, 1 + 2 × 26 = 53, 1 + 3 × 26 = 79, 1 + 4 × 26 = 105… le premier nombre divisible par a. Pour a = 7 : 27, 53 et 79 ne sont pas divisibles par 7, mais 105 = 7 × 15. L'inverse est 15. Pour a = 9 : 27 = 9 × 3, l'inverse est 3.

Méthode 2 : l'algorithme d'Euclide étendu (complément hors programme, utile pour les grands nombres). On fait l'algorithme d'Euclide, puis on « remonte » les égalités pour écrire 1 comme une combinaison de a et n.

• 26 = 7 × 3 + 5, donc 5 = 26 − 3 × 7
• 7 = 5 × 1 + 2, donc 2 = 7 − 5
• 5 = 2 × 2 + 1, donc 1 = 5 − 2 × 2

En remontant : 1 = 5 − 2 × (7 − 5) = 3 × 5 − 2 × 7 = 3 × (26 − 3 × 7) − 2 × 7 = 3 × 26 − 11 × 7.

Modulo 26, le terme 3 × 26 disparaît : 7 × (−11) ≡ 1 [26]. L'inverse est −11 ≡ −11 + 26 = 15 [26].

Méthode 3 : Python (pour vérifier) : pow(7, -1, 26) renvoie 15 (Python 3.8 et plus). Si l'inverse n'existe pas, Python lève une erreur ValueError.

Les inverses modulo 26, à connaître ou à savoir retrouver vite pour le chiffrement affine. Les 12 entiers de 1 à 25 premiers avec 26 = 2 × 13 sont les nombres impairs différents de 13 :

Remarque que les inverses vont par paires (3 et 9, 5 et 21, 7 et 15…) : si a' est l'inverse de a, alors a est l'inverse de a'. Et 25 ≡ −1 [26] est son propre inverse, car (−1) × (−1) = 1.

Résoudre une équation a × x ≡ b [n]

Si a a un inverse a' modulo n, on multiplie les deux membres par a' : x ≡ a' × b [n]. L'équation a une solution unique modulo n.

Exemple : 7x ≡ 3 [26]. L'inverse de 7 est 15, donc x ≡ 15 × 3 = 45 ≡ 19 [26]. Vérification : 7 × 19 = 133 = 5 × 26 + 3.

Même chose avec une équation affine : si y ≡ 7x + 3 [26], alors 7x ≡ y − 3, et x ≡ 15(y − 3) = 15y − 45 ≡ 15y + 7 [26] (car −45 + 52 = 7). C'est la formule de déchiffrement d'un chiffrement affine de clé (7, 3).

Si a n'a pas d'inverse, d = PGCD(a, n) > 1. D'après la propriété, a × x ne prend modulo n que les valeurs multiples de d :

• si b n'est pas un multiple de d, il n'y a aucune solution ;
• si b est un multiple de d, il y a d solutions entre 0 et n − 1.

Exemple : 8x ≡ 4 [12]. PGCD(8, 12) = 4 et 4 est un multiple de 4 : il y a 4 solutions. En essayant : x = 2, 5, 8 ou 11 (8 × 2 = 16 ≡ 4, 8 × 5 = 40 ≡ 4, 8 × 8 = 64 ≡ 4, 8 × 11 = 88 ≡ 4). En revanche, 8x ≡ 6 [12] n'a aucune solution : 6 n'est pas un multiple de 4.

Exercices

Fonction inverse(a, n)
    Si pgcd(a, n) ......... alors
        Renvoyer −1
    Fin Si
    c ← 1
    Tant que reste(a × c, n) ......... faire
        c ← .........
    Fin Tant que
    Renvoyer c

Fonction inverse(a, n)
    Si pgcd(a, n) ≠ 1 alors
        Renvoyer −1
    Fin Si
    c ← 1
    Tant que reste(a × c, n) ≠ 1 faire
        c ← c + 1
    Fin Tant que
    Renvoyer c