Polynômes, extensions de corps et QR codes

02 mai 2020 — Python

Si vous arrivez ici, vous avez peut-être lu l’article sur la construction des nombres réels.

Avant de vous parler d’un autre ensemble de nombres fondamentaux en mathématiques, les nombres complexes, je voudrais faire un petit détour par les polynômes.

Ceci permettra d’une part de définir précisément les nombres complexes, mais aussi de généraliser le concept sous-jacent d’extension de corps par un polynôme irréductible.

Nous finirons avec une application pratique des polynômes en informatique, en parlant de QR codes et de codes correcteurs.

Fibonacci et la reproduction des lapins 🐰

D’après Wikipedia, Leonardo Fibonacci aurait posé quelque part autour de 1202 une énigme sur l’évolution mois après mois du nombre de couples de lapins en partant d’un unique couple placé dans un enclos.

Cette modélisation très sommaire a donné une suite qui porte son nom, et qui a bien plus d’utilité pour illustrer des notions mathématiques ou algorithmiques que pour réellement compter des lapins 🙂

Le calcul des valeurs de cette suite est un exercice classique de programmation.

💻 Algorithme naïf

Une approche naïve avec une fonction récursive est la suivante :

def fibonacci(n):
  if n in (0, 1):
    return 1
  else:
    return fibonacci(n-2) + fibonacci(n-1)
>>> fibonacci(5)
8
>>> fibonacci(30)
1346269

Cette approche est assez mauvaise, chaque appel à la fonction lançant deux nouveaux appels pour calculer les termes précédents, la complexité algorithmique est alors exponentielle.

On peut trouver des algorithmes qui améliorent ce temps de calcul, je vous laisse par exemple proposer une version qui calcule les différents termes de façon itérative.

Formule explicite

En fait, il est possible de donner une formule explicite pour $\mathcal{F}_{n}$ en fonction de $n$.

Une « astuce » consiste à remarquer que si l’on considère une suite géométrique de la forme $(x^n)_{n \in \N}$, la condition de récurrence $x_{n+2} = x_{n+1} + x_n$ nous ramène à l’équation polynomiale $x^2 = x + 1$.

Cette équation s’écrit encore $(x - \frac{1}{2})^2 = \frac{5}{4}$ et a donc deux solutions données par $x_1 = \cfrac{1 + \sqrt{5}}{2}$ et $x_2 = \cfrac{1 - \sqrt{5}}{2}$.

En cherchant une solution sous forme d’une combinaison linéaire des $(x_1^n)$ et $(x_2^n)$ et en choisissant les coefficients permettant de vérifier les conditions initiales requises, on obtient alors la formule explicite : ${\mathcal{F}_n = \frac{1}{\sqrt{5}} (x_1^n - x_2^n)}$

Pourquoi cette astuce ?

L’astuce que nous avons utilisée ci-dessus semble un peu « parachutée ». En tout cas, c’est l’impression que j’ai eue la première fois qu’on me l’a présentée.

Elle correspond en fait à un cas particulier de recherche des valeurs propres d’une application linéaire, via l’étude de son polynôme caractéristique (ici le polynôme ${x^2 - x - 1}$).

Cette même astuce est utilisée, souvent de façon implicite, dans de nombreux domaines de la physique lorsque les systèmes étudiés sont modélisés par des équations linéaires.

Une chose remarquable est qu’elle reste utilisable pour trouver des formules explicites même lorsque l’équation polynomiale correspondante n’admet pas de solution réelle, ce qui est à l’origine de l’utilisation des nombres complexes dans beaucoup de problèmes issus du monde réel… nous aurons l’occasion d’y revenir 😉

Notion de polynôme

Les expressions polynômiales sont celles de la forme $a_0 + a_1 x + a_2 x^2 + ... + a_n x^n$, où les coefficients $(a_i)_{0 \lt i \lt n}$ sont des nombres réels (pour l’instant, mais nous étendrons ce concept à d’autres ensembles).

Par exemple, nous avons étudié le polynôme ${x^2 - x - 1}$ pour trouver une expression des termes de la suite de Fibonacci.

Les mathématiciens utilisent plutôt un $X$ majuscule pour écrire les polynômes formels, notation que nous adopterons ici.

Considérer un polynôme $a_0 + a_1 X + a_2 X^2 + ... + a_n X^n$ est équivalent à se donner une suite finie de nombres ${(a_0, a_1, ..., a_n)}$, $n$ étant l’indice du dernier terme non nul s’il existe ($n$ est le degré du polynôme).

Opérations sur les polynômes

L’addition de deux polynômes est définie assez naturellement en additionnant terme à terme.

La multiplication de deux polynômes se fait en étendant les règles usuelles de distributivité de la multiplication :

Plus généralement, si l’on considère le produit du polynôme de coefficients ${(a_0, a_1, ..., a_n)}$ par le polynôme de coefficients ${(b_0, b_1, ..., b_m)}$, le développement du produit nous donne un polynôme de degré $n + m$.

Ses coefficients ${(c_0, c_1, ..., c_{m+n})}$ sont définis par ${c_k = a_0 \times b_k + a_1 \times b_{k-1} + ... + a_{k-1} \times b_1 + a_k \times b_0}$
($c_k$ est la somme des produits $a_i \times b_j$ avec $i + j = k$)

💡 La formule ci-dessus est un cas particulier d’une opération appelée produit de convolution. Le produit de convolution est utilisé dans différents domaines des mathématiques, par exemple pour déterminer la loi d’une somme de variables aléatoires indépendantes…

Divisibilité

Tout comme pour les entiers, on définit une notion de divisibilité sur les polynômes :

Un polynôme $A$ est divisible par un polynôme $B$ si il existe un polynôme $Q$ tel que $A = B \times Q$.

💻 Implémentation des polynômes en Python

Voici une implémentation simple d’un type Polynomial, avec Python 3 : voir le code source.

Nous avons vu qu’un polynôme est défini par une suite finie de coefficients, que nous pouvons modéliser à l’aide d’une liste. J’ai privilégié l’utilisation des tuples, qui sont immuables.

Ce type utilise la définition des opérateurs en Python, en particulier les opérateurs numériques (addition, multiplication, etc.).

Quelques détails d’implémentation :

• Cette implémentation n’est pas optimale. On peut par exemple améliorer la fonction pow en utilisant un algorithme d’exponentiation rapide. Je vous laisse le faire en exercice 😉
• Les coefficients doivent implémenter la classe abstraite Number. On peut par exemple utiliser des flottants (le calcul sera alors approximatif).
• Il est nécessaire de définir les opérateurs à droite (__radd__, etc.) pour supporter des opérations comme 1 + Polynomial(0, 1).

Effectuons quelques calculs :

>>> Polynomial(1, 2, 3) * Polynomial(3, 0, -5)
(3, 6, 4, -10, -15)

Ou, si vous préférez l’écriture « avec des $X$ » :

>>> X = Polynomial(0, 1)
>>> (1 + 2*X) * (2 - 3*X**2)
(2, 4, -3, -6)

💻 Division euclidienne

Une opération moins évidente sur les polynômes est la division euclidienne.

Pour les entiers naturels, la division euclidienne de $a$ par $b \neq 0$ consiste à obtenir une écriture de la forme $a = b \times q + r$ avec $0 \leq r \lt b$. Un algorithme pour obtenir cette décomposition consiste à retrancher $b$ à $a$ jusqu’à obtenir la condition requise.

Pour des polynômes, la notion de degré permet d’obtenir une décomposition analogue :

$A$ et $B$ étant des polynômes avec $B \neq 0$, il existe des polynômes $Q$ (quotient) et $R$ (reste) uniques vérifiant : $A = B \times Q + R$ avec $\deg{R} < \deg{B}$

L’algorithme est un peu plus complexe, puisque cette fois-ci on doit retrancher à chaque étape un polynôme bien choisi de façon à faire diminuer le degré du reste.

Voici l’implémentation de la division euclidiene dans le type Polynomial :

def __divmod__(self, other):
    other = Polynomial.from_obj(other)
    if other is None:
        return NotImplemented
    if other.iszero:
        raise ZeroDivisionError
    Q, R = 0, self
    while R.degree >= other.degree:
        ratio = R[R.degree] * other[other.degree]**-1
        monomial = Polynomial(*([0] * (R.degree - other.degree) + [ratio]))
        R -= monomial * other
        Q += monomial
    return (Q, R)

Prenons un exemple simple :

>>> X = Polynomial(0, 1)
>>> divmod(1 + 2*X + X**3, 2 * X**2 - X)
((0.25, 0.5), (1.0, 2.25))

Ce qui traduit l’égalité : $1 + 2X + X^3 = (2X^2 - X) \times (\frac{1}{2}X + \frac{1}{4}) + \frac{9}{4}X + 1$

Explications du fonctionnement de l’algorithme :

• À chaque étape on calcule le monôme $\frac{r}{b} X^{\deg{R} - \deg{B}}$, où $r$ et $b$ désignent les coefficients de plus haut degré de $R$ et de $B$.
• On ajoute ce monôme à $Q$ et on retranche à $R$ le produit de ce monôme par $B$.
  La quantité $A = B \times Q + R$ est donc conservée : c’est un invariant de boucle.
• Le monôme retranché est calculé précisément de façon à éliminer le terme dominant de $R$, dont le degré diminue ainsi à chaque itération, jusqu’à être inférieur à celui de $B$.

💡 Nous utilisons dans cet algorithme le nombre $\frac{r}{b} = r \times b^{-1}$.
Lorsque nous considérerons des polynômes dont les coefficients sont dans d’autres ensembles que les réels, il faudra toujours avoir une notion d’inverse pour la multiplication afin que cet algorithme fonctionne : il restera valable pour des polynômes à coefficients dans des corps.

Calcul modulo un polynôme P

Si vous avez lu l’article d’introduction à l’arithmétique modulaire et la construction de $\Z/n\Z$, vous savez que compter dans cet ensemble revient à compter « à un multiple de $n$ près ».

Cette idée s’étend aux ensembles de polynômes. Si l’on particularise un polynôme $P$ de degré $n$, on va pouvoir compter « à un polynôme multiple de $P$ près », c’est-à-dire modulo $P$.

Quel intérêt à cela ?

• Pour les entiers, le calcul modulo $n$ a permis de ramener le calcul dans $\Z$, un ensemble infini, à du calcul dans un ensemble à $n$ éléments.
  Pour les polynômes, le calcul modulo $P$ près va nous permettre grâce à la division euclidienne de ne considérer que des polynômes de degré $\lt n$, qui correspondent donc à des séquences finies de $n$ nombres.
• Nous avons vu que sous certaines conditions le calcul dans $\Z/n\Z$ autorise la division : si $n$ est premier, tous les éléments non nuls ont un inverse pour la multiplication.
  Nous verrons qu’il est aussi possible d’introduire des inverses modulo $P$, à certaines conditions sur le polynôme $P$ choisi.

Voici quelques exemples de calcul modulo $P = 2 + 4X - 3X^2 - 6X^3$.

>>> P = Polynomial(2, 4, -3, -6)
>>> Polynomial(1, 2, 3) * Polynomial(4, 5, 6) % P
(10.0, 31.0, 31.0)
>>> Polynomial(1, 2) * Polynomial(2, 0, -3) % P
0

On constate dans le second exemple que les polynômes $1 + 2X$ et $2 - 3X^2$ sont des diviseurs de $0$ modulo $P$. Ceci s’explique par le fait que ${P = (1 + 2X)(2 - 3X^2)}$.

Inversion modulo un polynôme $P$

Si l’on veut pouvoir introduire une division sur les polynômes modulo $P, P \neq 0$ et ainsi pouvoir y calculer « comme sur les réels », il ne doit pas y avoir de diviseur de zéro.

Cela nécessite qu’on ne puisse pas exprimer $P$ comme produit de polynômes non constants (cas précédent), on dit alors que $P$ est irréductible. Nous allons voir que cette condition est en fait suffisante.

La question de savoir si un polynôme $A$ a un polynôme inverse $A^{-1}$ modulo $P$ revient en fait à savoir si il existe des polynômes $U$ et $V$ tels que ${A \times U + P \times V = 1}$. Dans ce cas, on pourra poser $A^{-1} = U$.

Étudions ci-dessous les conditions pour que cela soit possible.

💻 Identité de Bézout

Notons $I(A, B)$ l’ensemble des polynômes qui peuvent s’écrire sous la forme ${A \times U + B \times V}$, avec $U$ et $V$ des polynômes quelconques (on peut voir $I$ comme une fonction qui à deux polynômes associe un ensemble de polynômes).

On peut construire deux suites finies de polynômes $(A_n)$ et $(B_n)$ en posant :

• $A_0 = A, B_0 = B$
• Si $B_n \neq 0$, notons $A_n = B_n \times Q_n + R_n$ la division euclidienne de $A_n$ par $B_n$. On pose $A_{n+1} = B_n$ et $B_{n+1} = R_n$, on a donc $\deg{B_{n+1}} < \deg{B_n}$.
• Lorsque $B_n = 0$, on arrête le procédé

La suite des $\deg{B_n}$ étant strictement décroissante, on atteint la condition $B_n = 0$ en un nombre fini d’étapes.

Toute la subitlité de cet algorithme consiste à identifier l’invariant suivant :

À la fin du procédé, on a $B_n = 0$ et donc $I(A, B) = I(A_n, 0)$.

Notons $C$ le polynôme unitaire $\frac{1}{a} A_n$ (où $a$ est le coefficient dominant de $A_n$).

$I(A_n, 0) = I(C, 0)$ est l’ensemble des polynômes multiples de $C$ (en particulier $A$ et $B$ sont donc multiples de $C$).

Si l’on résume les résultats obtenus :

Il existe un unique polynôme unitaire $C$, appelé le PGCD de $A$ et $B$, tel que :

• $C$ divise $A$ et $C$ divise $B$
• $C$ peut s’écrire sous la forme $C = A \times U + B \times V$ (identité de Bézout)
• Tout diviseur commun de $A$ et $B$ divise $C$.

On déduit le dernier point de l’identité de Bézout, et il justifie le nom de « plus grand ».

💡 Dans le cadre de la théorie des anneaux, $I(A, B)$ est l’idéal engendré par $A$ et $B$. L’algorithme nous montre que cet idéal est principal, c’est-à-dire engendré par un unique élément $C$.

Voici une implémentation de cet algorithme en Python :

@classmethod
def bezout_identity(cls, A, B):
    U, V = 1, 0     # Invariant: A = U*A_n + V*B_n
    u, v = 0, 1     # Invariant: B = u*A_n + v*B_n
    while not B.iszero:
        Q, R = divmod(A, B)
        A, B = B, R
        # A' = B, B' = A - Q B
        U, V, u, v = u, v, U - Q * u, V - Q * v
    mult = A[A.degree]**-1
    return (mult * U, mult * V, mult * A)

Dans cette implémentation, on calcule aussi les polynômes $U$ et $V$ de l’identité de Bézout, en maintenant à chaque étape cette décomposition pour $A$ et $B$.

>>> Polynomial.bezout_identity(2*X**6 - 2, X**9 - 1)
((0.0, 0.0, 0.0, -0.5), 1.0, (-1.0, 0.0, 0.0, 1.0))

Critère d’inversibilité

On déduit de ce qui précède le critère suivant d’inversibilité, similaire à celui qu’on avait obtenu pour les entiers :

Un polynôme $A$ est inversible pour la multiplication modulo $P$ si et seulement si $\gcd(A, P) = 1$ (on dit que $A$ est premier avec $P$).

On déduit de ce qui précède :

Tous les polynômes non nuls ont un inverse modulo $P$ si et seulement si $P$ est irréductible.

💡 Analogies avec les entiers

Beaucoup des résultats ci-dessus sont des analogues de résultats sur les entiers :

Les mathématiciens aiment bien identifier des structures communes entre différents ensembles et pouvoir généraliser les résultats et théorèmes sur ces structures.

Dans ce cas, la structure commune est celle des anneaux euclidiens, la notion de degré d’un polynôme étant l’analogue de la valeur absolue d’un entier.

La dernière ligne du tableau fait apparaître la structure d’anneau quotient.

Extensions de corps

Que nous disent les résultats ci-dessus ?

Ils nous disent que si l’on trouve un polynôme $P$ irréductible sur $\R$, en notant $n$ son degré, on pourra calculer sur les séquences finies $(x_0, x_1, ..., x_{n-1})$ comme on calcule sur $\R$ : avec des symboles $+$, $-$, $\times$ et $/$

Tous ces résultats ont été obtenu en partant de $\R$, grâce à des algorithmes qui utilisent les opérateurs de $\R$ (en particulier, l’algorithme de la division euclidienne).

Nous avons vu dans des articles précédents que les ensembles munis des opérateurs $+$, $-$, $\times$ et $/$ avec certaines propriétés (en particulier, la distributivité de la multiplication) s’appellent des corps.

Les résultats obtenus ci-dessus peuvent donc se généraliser à n’importe quel corps (notamment $\Bbb{Q}$ et les corps finis $\Z/p\Z$ de l’arithmétique modulaire, ainsi qu’aux nouveaux corps que nous allons construire à partir de ceux-ci).

Si l’on dispose d’un corps (notons le $K$) et d’un polynôme ${P = a_0 + a_1 X + a_2 X^2 + ... + a_n X^n}$ irréductible sur $K$, on peut constuire un nouveau corps dont les éléments sont des séquences $(x_0, x_1, ..., x_{n-1})$ d’éléments de $K$.

Les polynômes de degré $1$ sont irréductibles mais correspondent à des séquences de $1$ élément (on retrouve le calcul sur $K$). On s’intéresse donc aux polynômes irréductibles de degrés supérieurs.

Un tel corps est appelé une extension finie de $K$.

On est donc amené à chercher des polynômes irréductibles de degré $\geq 2$ sur les corps que nous connaissons.

Extensions finies de $\Bbb{Q}$

Le polynôme $X^2 - 2$ est irréductible dans $\Bbb{Q}$, mais pas dans $\R$.

En effet, bien qu’on puisse le décomposer sous la forme $X^2 - 2 = (X + \sqrt{2})(X - \sqrt{2})$ en utilisant deux polynômes de degré $1$, les coefficients de ces polynômes sont $(1, \pm \sqrt{2})$, pas tous rationnels.

Calculer avec des polynômes rationnels modulo $X^2 - 2$ revient à calculer avec des nombres de la forme $a + b \sqrt{2}$ où $a$ et $b$ sont rationnels.

Par exemple, en utilisant le type Fraction pour que les coefficients soient rationnels :

>>> from fractions import Fraction
>>> P = X**2 - 2
>>> (1 + Fraction(1, 2) * X) * (1 - Fraction(1, 2) * X) % P
Fraction(1, 2)

Ce qui traduit l’égalité $(1 + \frac{\sqrt{2}}{2})(1 - \frac{\sqrt{2}}{2}) = \frac{1}{2}$.

💡 Un nombre comme $\sqrt{2}$ qui est racine d’un polynôme à coefficients dans $\Bbb{Q}$ est un nombre algébrique.
Si $\alpha$ est un nombre algébrique de degré $n$ (le degré minimal d’un polynôme rationnel $P$ annulant $\alpha$), on peut construire une extension algébrique de $\Bbb{Q}$ en comptant avec les nombres de la formes ${x_0 + x_1 \alpha + x_2 \alpha^2 + ... + x_{n-1} \alpha^{n-1}}$ où les coordonnées $x_i$ sont des rationnels.
Les calculs obtenus sont alors les mêmes que si on considère les séquences $(x_0, x_1, ..., x_{n-1})$ comme les coefficients d’un polynôme et qu’on calcule modulo $P$.

Extensions finies de $\R$

Il s’agit de trouver un polynôme à coefficients réels qui soit irréductible.

En cherchant des polynômes de degré $2$, on trouve par exemple le polynôme $P = 1 + X^2$.

Ce polynôme est irréductible car sinon on aurait une égalité de la forme ${1 + X^2 = (X - a)(X - b)}$ avec $a$ et $b$ des nombres réels et donc $1 \leq a^2 + 1 = 0$.

On obtient en comptant avec des polynômes ${a + bX}$ modulo ${1 + X^2}$ les nombres complexes.

Mathématiquement, on définit donc $\Complex = \R[X]/(1 + X^2)$ (notation des ensembles quotient, qui est la transcription mathématique de ce qu’on vient de dire) qu’on appelle l’ensemble des nombres complexes.

Dans cet ensemble, on calcule avec des couples de nombres réels $(a, b)$.

On appelle alors $i$ le couple $(0, 1)$, correspondant au polynômes $X$. L’égalité $i^2 = -1$ est alors une autre façon de dire qu’on calcule modulo $1 + X^2$.

Le résultat suivant n’est par exemple que la traduction du calcul $(1 + i)^2 = 2i$ :

>>> (1 + X)**2 % (X**2 + 1)
(0.0, 2.0)

Les complexes comme transformations dans le plan

En identifiant un point dans le plan, de coordonnées $(a,b)$, au $a + bX$, on obtient les règles de calcul suivantes :

C’est-à-dire :

Le produit d’un polynôme par un autre modulo $P$ étant une opération linéaire, ceci permet de voir les nombres complexes comme des fonctions linéaires représentées par des matrices de la forme :

On en déduit alors l’interprétation géométrique des nombres complexes, telle qu’on la voit au lycée.

💡 Un théorème fondamental concernant les nombres complexes a pour conséquence qu’on ne peut pas constuire d’autres extensions finies de $\R$ (par exemple, il n’est pas possible de définir une structure de corps sur les triplets $(a, b, c)$ de nombres réels…).

Extensions finies de $F_2$

Nous avons construit dans l’article d’introduction à l’arithmétique modulaire les ensembles $\Z/p\Z$.

Nous avons vu que si $p$ est un nombre premier ces ensembles sont des corps, on privilégie alors la notation $F_p$ pour les désigner.

Dans le cas $p = 2$, on obtient un ensemble à deux éléments ($0$ et $1$) sur lequel sont définies les opérations suivantes :

Addition

Multiplication

Si l’on identifie $0$ et $1$ à des booléens, l’addition peut-être vue comme l’opérateur logique ou exclusif et la multiplication comme l’opérateur logique et.

Ces opérations sont généralement supportées nativement par les processeurs, ce qui permet d’effectuer des calculs sur $F_2$ (et donc sur les polynômes à coefficients dans $F_2$) très rapidement.

💻 Calcul avec des polynômes binaires

Bien que les éléments de $F_2$ puissent être vus comme des booléens, je ne vais pas utiliser les booléens True / False de Python pour les implémenter.

En effet, en Python la classe bool hérite de int et les opérateurs numériques se comportent comme sur des entiers :

>>> True  + True
2

Définissons un type Mod2Number pour représenter un élément de $F_2$, comme il implémente les opérateurs numériques des Number nous pourrons l’utiliser pour créer des instances du type Polynomial.

On se contente de remplacer l’addition et la multiplication par leurs équivalents modulo $2$, l’inversion pow(x, -1) est ici très simple puisque $1$ est le seul nombre inversible.

class Mod2Number(int):
    def __add__(self, other):
        if isinstance(other, int):
            return Mod2Number(super().__add__(other) % 2)
        return NotImplemented
    def __radd__(self, other):
        return self + other
    def __neg__(self):
        return Mod2Number(super().__neg__() % 2)
    def __sub__(self, other):
        return self + (-other)
    def __rsub__(self, other):
        return -self + other
    def __mul__(self, other):
        if isinstance(other, int):
            return Mod2Number(super().__mul__(other) % 2)
        return NotImplemented
    def __rmul__(self, other):
        return self * other
    def __pow__(self, other):
        if other < 0:
            if self == 1:
                return Mod2Number(1)
            else:
                raise ZeroDivisionError
        else:
            return Mod2Number(1)

La fonction ci-dessous nous permettra de constuire un polynôme à coefficients dans $F_2$ à partir d’une chaîne de texte représentant ses chiffres en commençant à gauche avec le poids le plus fort (notation big-endian, donc dans le sens contraire de leur apparition dans le tuple des coefficients).

def getMod2Poly(digits):
    return Polynomial(*(Mod2Number(d) for d in reversed(digits)))
>>> getMod2Poly('100011101')
(1, 0, 1, 1, 1, 0, 0, 0, 1)
>>> getMod2Poly('100011101') * getMod2Poly('10101')
(1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1)

Polynômes irréductibles dans $F_2$

Le polynôme $P = 1 + X + X^2$ est irréductible dans $F_2$.

S’il ne l’était pas, on pourrait le décomposer comme produit de deux polynômes de degré $1$ (les degrés s’additionnent).

Les polynômes de degré $1$ dans $F_2$ correspondent à des couples de coefficients binaires dont le deuxième coefficient est non nul :

• le polynôme $X$ de coefficients $(0, 1)$
• le polynôme $1 + X$ de coefficients $(1, 1)$

Les produits correspondant sont : $X^2$, ${X(1+X) = X + X^2}$ et ${(1 + X)^2 = 1 + (1 + 1)X + X^2 = 1 + X^2}$.

Cette méthode par force brute suffit ici pour montrer l’irréductibilité (évidemment, on ne pourrait pas faire pareil sur un corps infini…).

En comptant avec les couples $(a, b)$ de chiffres binaires identifiés à des polynômes modulo $P$ on définit donc des règles de calcul qui font de cet ensemble un corps.

On peut calculer sa table de multiplication :

>>> P = getMod2Poly('111')
>>> for a in range(4):
>>>     for b in range(a + 1):
>>>         a_digits, b_digits = f"{a:02b}", f"{b:02b}"
>>>         prod = getMod2Poly(a_digits) * getMod2Poly(b_digits) % P
>>>         res = "".join(reversed([str(d) for d in prod])).zfill(2)
>>>         print(f"{a_digits} * {b_digits} = {res}")
00 * 00 = 00
01 * 00 = 00
01 * 01 = 01
10 * 00 = 00
10 * 01 = 10
10 * 10 = 11
11 * 00 = 00
11 * 01 = 11
11 * 10 = 01
11 * 11 = 10

Le polynôme suivant est également irréductible dans $F_2$ : ${P = 1 + X^2 + X^3 + X^4 + X^8}$.

Nous pouvons encore le prouver par force brute, mais cette fois-ci informatiquement. Il suffit de tester tous les polynômes de degré compris entre $1$ et $4$, représentés en binaire par des entiers compris entre $2$ et $2^5 - 1$.

>>> P = getMod2Poly('100011101')
>>> 
>>> for i in range(2, 255):
>>>     T = getMod2Poly("{0:b}".format(i))
>>>     if (P % T).iszero:
>>>         print(T)
>>>         break
>>> else:
>>>     print("No divisor found")
No divisor found

L’existence de ce polynôme irréductible montre que l’on peut construire un corps dont les éléments sont les séquences de huit chiffres binaires, c’est-à-dire des octets. Ce corps est noté $F_{256}$.

💡 En fait, on montre que pour tout nombre premier $p$ et pour tout entier $n > 0$, on peut construire un corps fini de taille $p^n$, qui est une extension algébrique simple de $F_p$.

Polynômes sur les corps finis et codes correcteurs

Je vous laisse scanner le QR code ci-dessous et vérifier si vous arrivez à le lire, malgré le stylo que j’ai mis devant :

Je ne sais pas pour vous mais… chez moi ça marche !

Comment se fait-il que ce QR code soit encore lisible alors qu’une partie des données qu’il encode n’est pas visible ? Nous allons brièvement expliquer la technique utilisée, qui n’est d’ailleurs pas spécifique aux QR code.

Quelques mots sur les QR code

Les QR code utilisent un quadrillage de carrés noirs et blancs pour stocker des données binaires.

Sur l’exemple ci-dessus, j’ai utilisé un QR code version 3, utilisant un quadrillage 29x29.

Différentes zones de ce quadrillage servent à stocker différentes informations :

• Des zones figées permettent de définir l’orientation du code (grâce aux trois gros carrés) et de corriger d’éventuels effets de perspective (grâce au carré vers le bas à droite).
• Des zones précises sont réservées pour stocker des métadonnées nécessaires à la bonne lecture des données, notamment :
  • le masque utilisé (je ne détaille pas)
  • le niveau de correction des erreurs des données stockées
  • des données permettant de corriger d’éventuelles erreurs sur les métadonnées
• Les autres carrés (560 carrés, soit 70 octets) représentent les données stockées, en intégrant des données redondantes pour corriger les erreurs.

Les métadonnées sont évidemment très critiques : si elles ne sont pas lisibles, il sera impossible d’interpréter le reste des données.

Je vous propose ci-dessous de voir comment fonctionne le code correcteur utilisé pour gérer les erreurs sur les métadonnées. Les codes correcteurs utilisés pour les données elles-mêmes sont un peu plus sophistiqués, je les évoque ensuite.

Code polynomial sur $F_2$

Les métadonnées d’un QR code sont codées sur cinq bits, par exemple $01100$.

On définit :

• Un polynôme $G = 1 + X + X^2 + X^4 + X^5 + X^8 + X^{10}$ appelé le polynôme générateur du code ($10100110111$ en notation binaire)
• Le message à encoder, de taille fixe et connue (ici 5 bits), est assimilé à un polynôme $M$ à coefficients binaires.

Encodage

• $T = M \times X^{\deg{G}}$ est un polynôme de degré $\deg{M} + \deg{G} = 15$ qui correspond en binaire au message décalé « $\deg{G}$ fois » à gauche.
• On effectue sa division euclidienne par $G$ : $T = G \times Q + R$ avec $\deg{R} < \deg{G}$
• On retranche $R$ à $T$ pour ne conserver que le polynôme $P = G \times Q$, multiple du générateur et de degré $15$.
• C’est la représentation de $P$ en binaire qui est stockée, sur $15$ bits (avec du padding à gauche, implémenté ci-dessous avec zfill).

Si l’on implémente cela sur notre exemple, on obtient la chaîne qui sera réellement stockée :

def encode(message, g):
    M = getMod2Poly(message)
    G = getMod2Poly(g)
    T = getMod2Poly('10')**G.degree * M
    R = T % G
    return ("".join(reversed([str(d) for d in T - R]))
              .zfill(len(message) + len(g) - 1))
>>> encode('01100', '10100110111')
011001000111101

Décodage

En l’absence d’erreur de lecture, le message d’origine se retrouve en lisant les cinq premiers bits du message encodé. On le vérifie sur notre exemple ci-dessus, et cela se justifie par les propriétés de la division euclidienne utilisée.

Cependant, tout l’intérêt d’un code détecteur / correcteur d’erreur est de gérer les cas où les données sont altérées, par exemple lorsqu’un QR code est partiellement illisible.

Pour ce code simple, il est possible de précalculer tous les codes valides, puis de chercher celui qui est le plus proche du message lu, on renvoie alors le message correspondant qui est le préfixe de longueur cinq du code obtenu :

valid_codes = {encode(f"{i:05b}", '10100110111') for i in range(2**5)}
def decode(p):
    if p in valid_codes:
        return p[:5]
    else:
        return min(
            valid_codes,
            key=lambda code: sum(1 for i in range(len(code)) if p[i] != code[i])
        )[:5]

Ce code permet de corriger jusqu’à trois erreurs :

>>> decode('011001000111101')    # No error, OK
01100
>>> decode('111001000110101')    # 2 errors, OK
01100
>>> decode('111001010110101')    # 3 errors, OK
01100
>>> decode('101001010110101')    # 4 errors, KO
10010

Le code décrit ci-dessus est utilisé en pratique pour encoder une partie des métadonnées des QR code, qui sont stockées sur cinq bits.

En voici une implémentation en C bien plus efficace, puisqu’elle implémente les opérations au niveau binaire.

Il s’agit de la librairie libqrencode que j’ai utilisée pour générer le QR code plus haut.

Codes correcteurs en pratique

Le type de code décrit au-dessus appartient à une famille de codes correcteurs appelés les codes BCH, inventés autour des années 1960 et très largement utilisés (DVD, disques durs, etc.).

Je n’ai parlé ici que du code utilisé pour les métadonnées, relativement simple car il repose sur un polynôme à coefficients dans $F_2$.

Les codes correcteurs utilisés pour coder les données elles-mêmes reposent sur des polynômes à coefficients dans des corps plus grands, par exemple le corps $F_{256}$ dont on a montré l’existence plus haut et qui permet de compter avec des opérations sur les octets.

Un des résultats fondamentaux sur les corps finis, nécessaire pour bien comprendre le fonctionnement de ces codes, est l’existence d’un élément $\alpha$ tel que tout élément $\neq 0$ du corps peut s’écrire sous la forme $\alpha^k$ (on dit que $\alpha$ est un élément primitif).
En voici une preuve, formulée dans le langage de la théorie des groupes.

Pour en savoir plus sur les codes correcteurs et comprendre pourquoi ils sont efficaces (en terme de nombres d’erreur corrigées par rapport au surplus de données nécessaire), vous pouvez lire :

• ce document, qui les présente sous un angle mathématique
• cette page qui adopte une approche plus pratique, reprenant le cas des codes correcteurs utilisés dans les QR code (code en Python)
• cette longue introduction par la NASA

Maths et applications, avec les mains et avec du code 💻
Suivre sur Twitter

• ← Arithmétique modulaire, RSA et clefs privées
• Histoires de surfaces, de Gauss à OpenStreetMap →