Course list Sign in

Information

Author(s) Nikita Tyunyayev
Deadline No deadline
Submission limit No limitation

Sign in

Sign in

Théorie des nombres - Algorithme d'Euclide étendu

Dans cette tâche, vous allez implémenter l'algorithme d'Euclide étendu, puis l'utiliser pour (i) calculer des inverses modulaires et (ii) résoudre des équations modulaires \(ax \equiv b \pmod{n}\).

Les fonctions de la bibliothèque standard qui font ce travail à votre place (math.gcd, math.lcm, pow(a, -1, n)) sont interdites. Les tests utilisent de grands nombres (plus de 30 chiffres) : une recherche exhaustive (essayer toutes les valeurs de x) est beaucoup trop lente.

Algorithme d'Euclide étendu

Identité de Bézout. Le PGCD de deux entiers \(a\) et \(b\) est une combinaison linéaire entière de \(a\) et \(b\) : il existe des entiers \(u\) et \(v\) tels que \(\gcd(a, b) = au + bv\).

L'algorithme d'Euclide calcule \(\gcd(a, b)\) en remplaçant \((x, y)\) par \((y, x \bmod y)\) tant que \(y \neq 0\), car \(\gcd(x, y) = \gcd(y, x \bmod y)\). À chaque itération, \(x\) et \(y\) sont des combinaisons linéaires entières de \(a\) et \(b\). L'algorithme d'Euclide étendu garde en plus les coefficients de ces combinaisons : \(x = a \cdot \alpha_x[0] + b \cdot \alpha_x[1]\) et \(y = a \cdot \alpha_y[0] + b \cdot \alpha_y[1]\). Il calcule ainsi \(u\), \(v\) et \(\gcd(a, b)\) :

In : entiers positifs \(a\) et \(b\) (avec \(a\) ou \(b\) non-nul).

Init : \((x, y, \alpha_x, \alpha_y) \gets (a, b, (1, 0), (0, 1))\) si \(a \ge b\), \((b, a, (0, 1), (1, 0))\) sinon.

Loop : tant que \(y \neq 0\) :

  1. \((\alpha_x, \alpha_y) \gets (\alpha_y,\; \alpha_x - \operatorname{div}(x, y) \cdot \alpha_y)\)
  2. \((x, y) \gets (y,\; x \bmod y)\)

Result : \(x = \gcd(a, b)\) et \((u, v) = \alpha_x\) tels que \(\gcd(a, b) = au + bv\).

Par exemple, pour \((a, b) = (50, 18)\) :

\(x\) \(y\) \(\operatorname{div}(x, y)\) \(\alpha_x\) \(\alpha_y\)
50 18 2 (1, 0) (0, 1)
18 14 1 (0, 1) (1, -2)
14 4 3 (1, -2) (-1, 3)
4 2 2 (-1, 3) (4, -11)
2 0 — (4, -11) (-9, 25)

On obtient \(\gcd(50, 18) = 2 = 4 \cdot 50 - 11 \cdot 18\).

Inverse modulaire

Rappel : \(a\) est congru à \(b\) modulo \(n\), noté \(a \equiv b \pmod{n}\), si \(n | (a - b)\), c'est-à-dire si \(a \bmod n = b \bmod n\).

Soit \(n \ge 2\). Un inverse modulaire de \(a\) modulo \(n\) est un entier \(x\) tel que \(ax \equiv 1 \pmod{n}\).

Propriété. \(a\) possède un inverse modulo \(n\) si et seulement si \(a\) et \(n\) sont premiers entre eux (ou co-premiers) : \(\gcd(a, n) = 1\). Cet inverse est alors unique modulo \(n\).

En effet, si \(\gcd(a, n) = 1\), l'identité de Bézout donne \(au + nv = 1\), donc \(au \equiv 1 \pmod{n}\) : \(u\) est un inverse de \(a\). Inversement, si \(ax \equiv 1 \pmod{n}\), alors \(ax + ny = 1\) pour un certain entier \(y\), et tout diviseur commun de \(a\) et \(n\) divise 1.

Exemple : \(\gcd(3, 7) = 1 = 3 \cdot (-2) + 7 \cdot 1\), donc \(-2 \equiv 5\) est l'inverse de 3 modulo 7 (\(3 \cdot 5 = 15 \equiv 1 \pmod 7\)). Par contre, 6 n'a pas d'inverse modulo 9, car \(\gcd(6, 9) = 3\).

Équations modulaires

On cherche tous les entiers \(x\) tels que \(ax \equiv b \pmod{n}\). Posons \(g = \gcd(a, n)\).

  • Si \(g\) ne divise pas \(b\), l'équation n'a aucune solution : \(ax - b\) serait un multiple de \(n\), donc de \(g\), alors que \(g\) divise \(ax\) mais pas \(b\).
  • Si \(g\) divise \(b\), on peut tout diviser par \(g\) : l'équation est équivalente à \(\frac{a}{g} x \equiv \frac{b}{g} \pmod{\frac{n}{g}}\). Comme \(\gcd(\frac{a}{g}, \frac{n}{g}) = 1\), \(\frac{a}{g}\) est inversible modulo \(m = \frac{n}{g}\) et les solutions sont exactement les \(x \equiv x_0 \pmod{m}\), avec \(x_0 = \left(\frac{a}{g}\right)^{-1} \cdot \frac{b}{g} \bmod m\).

Exemple : \(4x \equiv 6 \pmod{10}\). \(g = \gcd(4, 10) = 2\) divise 6, l'équation devient \(2x \equiv 3 \pmod 5\). L'inverse de 2 modulo 5 est 3, donc \(x \equiv 3 \cdot 3 \equiv 4 \pmod 5\). Les solutions sont \(x \in \{\dots, -1, 4, 9, 14, \dots\}\) : modulo 10, il y en a deux, 4 et 9.

Les opérateurs // et % de Python
Pour \(n > 0\), a // n et a % n correspondent exactement à \(\operatorname{div}(a, n)\) et \(a \bmod n\) du cours, même si a est négatif : -7 % 3 vaut 2 (et non -1 comme en Java ou en C). N'utilisez pas /, qui renvoie un nombre à virgule (float) et perd en précision sur les grands nombres.
Question 1: Algorithme d'Euclide étendu

Écrivez une fonction euclide_etendu(a, b) qui renvoie un triplet (g, u, v) d'entiers tel que g est le PGCD de a et b, et a * u + b * v == g (identité de Bézout).

euclide_etendu(50, 18)   # (2, 4, -11)
euclide_etendu(18, 50)   # (2, -11, 4)
euclide_etendu(3, 5)     # (1, 2, -1)
euclide_etendu(17, 0)    # (17, 1, 0)

La paire \((u, v)\) n'est pas unique (par exemple \(2 = (-5) \cdot 50 + 14 \cdot 18\) aussi) : n'importe quelle paire \((u, v)\) telle que \(au + bv = \gcd(a, b)\) est acceptée.

Évaluation. Votre fonction est testée sur des entrées petites et grandes (jusqu'à \(2^{127}\), 2 secondes par test), dont des cas particuliers : a < b, a == b, a ou b nul. Pour un test raté sur de petites valeurs, le feedback montre le tableau d'exécution de l'algorithme.

Question 2: Inverse modulaire

Écrivez une fonction inverse_modulaire(a, n) qui renvoie l'inverse de a modulo n, c'est-à-dire l'unique entier x tel que 0 <= x < n et \(ax \equiv 1 \pmod{n}\), ou None si a n'a pas d'inverse modulo n.

a est un entier quelconque : il peut être négatif ou plus grand que n.

inverse_modulaire(3, 7)     # 5, car 3 * 5 = 15 ≡ 1 (mod 7)
inverse_modulaire(-3, 7)    # 2, car -3 * 2 = -6 ≡ 1 (mod 7)
inverse_modulaire(6, 9)     # None, car gcd(6, 9) = 3

Votre code de la question 1 est ajouté avant celui-ci : vous pouvez appeler euclide_etendu. Attention aux préconditions de euclide_etendu (a >= 0) : pensez à réduire a modulo n.

Évaluation. La note est le plus petit des deux taux de réussite (inverses trouvés quand ils existent, None quand ils n'existent pas) : une fonction qui renvoie toujours None obtient 0.

Question 3: Résoudre une équation modulaire

Écrivez une fonction resoudre_congruence(a, b, n) qui résout l'équation \(ax \equiv b \pmod{n}\).

  • Si l'équation n'a aucune solution, la fonction renvoie None.
  • Sinon, les solutions sont exactement les entiers \(x \equiv x_0 \pmod{m}\) pour un certain module \(m\) (voir plus haut). La fonction renvoie le couple (x0, m), avec 0 <= x0 < m.

a et b sont des entiers quelconques (éventuellement négatifs ou plus grands que n).

resoudre_congruence(3, 4, 7)     # (6, 7)  : 3 * 6 = 18 ≡ 4 (mod 7)
resoudre_congruence(4, 6, 10)    # (4, 5)  : x ∈ {4, 9, 14, ...} et {-1, -6, ...}
resoudre_congruence(4, 5, 10)    # None    : 4x est pair, 4x - 5 n'est jamais multiple de 10
resoudre_congruence(0, 0, 9)     # (0, 1)  : tout x est solution

Votre code de la question 1 est ajouté avant celui-ci : vous pouvez appeler euclide_etendu. Résolvez l'équation directement avec l'algorithme d'Euclide étendu (le code de la question 2 n'est pas disponible ici).

Évaluation. La note est le plus petit des deux taux de réussite (équations avec solutions résolues, None pour les équations sans solution).