Lipsum.dev

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 🙂

F1=F2=1Fn+2=Fn+Fn+1\mathcal{F}_1 = \mathcal{F}_2 = 1 \\ \mathcal{F}_{n+2} = \mathcal{F}_{n} + \mathcal{F}_{n+1}

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 Fn\mathcal{F}_{n} en fonction de nn.

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

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

En cherchant une solution sous forme d’une combinaison linéaire des (x1n)(x_1^n) et (x2n)(x_2^n) et en choisissant les coefficients permettant de vérifier les conditions initiales requises, on obtient alors la formule explicite : Fn=15(x1nx2n){\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 x2x1{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 a0+a1x+a2x2+...+anxna_0 + a_1 x + a_2 x^2 + ... + a_n x^n, où les coefficients (ai)0<i<n(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 x2x1{x^2 - x - 1} pour trouver une expression des termes de la suite de Fibonacci.

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

Considérer un polynôme a0+a1X+a2X2+...+anXna_0 + a_1 X + a_2 X^2 + ... + a_n X^n est équivalent à se donner une suite finie de nombres (a0,a1,...,an){(a_0, a_1, ..., a_n)}, nn étant l’indice du dernier terme non nul s’il existe (nn 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 :

(1+2X)×(23X2)=2+4X3X26X3(1 + 2X) \times (2 - 3X^2) = 2 + 4X - 3X^2 - 6X^3

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

Ses coefficients (c0,c1,...,cm+n){(c_0, c_1, ..., c_{m+n})} sont définis par ck=a0×bk+a1×bk1+...+ak1×b1+ak×b0{c_k = a_0 \times b_k + a_1 \times b_{k-1} + ... + a_{k-1} \times b_1 + a_k \times b_0}
(ckc_k est la somme des produits ai×bja_i \times b_j avec i+j=ki + 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 AA est divisible par un polynôme BB si il existe un polynôme QQ tel que A=B×QA = 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 XX » :

>>> 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 aa par b0b \neq 0 consiste à obtenir une écriture de la forme a=b×q+ra = b \times q + r avec 0r<b0 \leq r \lt b. Un algorithme pour obtenir cette décomposition consiste à retrancher bb à aa jusqu’à obtenir la condition requise.

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

AA et BB étant des polynômes avec B0B \neq 0, il existe des polynômes QQ (quotient) et RR (reste) uniques vérifiant : A=B×Q+RA = B \times Q + R avec degR<degB\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+X3=(2X2X)×(12X+14)+94X+11 + 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 rbXdegRdegB\frac{r}{b} X^{\deg{R} - \deg{B}}, où rr et bb désignent les coefficients de plus haut degré de RR et de BB.
  • On ajoute ce monôme à QQ et on retranche à RR le produit de ce monôme par BB.
    La quantité A=B×Q+RA = 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 RR, dont le degré diminue ainsi à chaque itération, jusqu’à être inférieur à celui de BB.

💡 Nous utilisons dans cet algorithme le nombre rb=r×b1\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/nZ\Z/n\Z, vous savez que compter dans cet ensemble revient à compter « à un multiple de nn près ».

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

Quel intérêt à cela ?

  • Pour les entiers, le calcul modulo nn a permis de ramener le calcul dans Z\Z, un ensemble infini, à du calcul dans un ensemble à nn éléments.
    Pour les polynômes, le calcul modulo PP près va nous permettre grâce à la division euclidienne de ne considérer que des polynômes de degré <n\lt n, qui correspondent donc à des séquences finies de nn nombres.
  • Nous avons vu que sous certaines conditions le calcul dans Z/nZ\Z/n\Z autorise la division : si nn 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 PP, à certaines conditions sur le polynôme PP choisi.

Voici quelques exemples de calcul modulo P=2+4X3X26X3P = 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+2X1 + 2X et 23X22 - 3X^2 sont des diviseurs de 00 modulo PP. Ceci s’explique par le fait que P=(1+2X)(23X2){P = (1 + 2X)(2 - 3X^2)}.

Inversion modulo un polynôme PP

Si l’on veut pouvoir introduire une division sur les polynômes modulo P,P0P, 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 PP comme produit de polynômes non constants (cas précédent), on dit alors que PP est irréductible. Nous allons voir que cette condition est en fait suffisante.

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

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

💻 Identité de Bézout

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

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

  • A0=A,B0=BA_0 = A, B_0 = B
  • Si Bn0B_n \neq 0, notons An=Bn×Qn+RnA_n = B_n \times Q_n + R_n la division euclidienne de AnA_n par BnB_n. On pose An+1=BnA_{n+1} = B_n et Bn+1=RnB_{n+1} = R_n, on a donc degBn+1<degBn\deg{B_{n+1}} < \deg{B_n}.
  • Lorsque Bn=0B_n = 0, on arrête le procédé

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

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

I(An+1,Bn+1)=I(Bn,AnBn×Qn)=I(Bn,An)=I(An,Bn)I(A_{n+1}, B_{n+1}) = I(B_n, A_n - B_n \times Q_n) = I(B_n, A_n) = I(A_n, B_n)

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

Notons CC le polynôme unitaire 1aAn\frac{1}{a} A_n (où aa est le coefficient dominant de AnA_n).

I(An,0)=I(C,0)I(A_n, 0) = I(C, 0) est l’ensemble des polynômes multiples de CC (en particulier AA et BB sont donc multiples de CC).

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

Il existe un unique polynôme unitaire CC, appelé le PGCD de AA et BB, tel que :

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

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)I(A, B) est l’idéal engendré par AA et BB. L’algorithme nous montre que cet idéal est principal, c’est-à-dire engendré par un unique élément CC.

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 UU et VV de l’identité de Bézout, en maintenant à chaque étape cette décomposition pour AA et BB.

>>> 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 AA est inversible pour la multiplication modulo PP si et seulement si gcd(A,P)=1\gcd(A, P) = 1 (on dit que AA est premier avec PP).

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

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

💡 Analogies avec les entiers

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

Entiers relatifs Z\ZPolynômes R[X]\R[X]
Addition des entiersAddition terme à terme des coefficients
MultiplicationMultiplication étendue à XX par distributivité
Division euclidienne avec critère sur la valeur absolue du resteDivision euclidienne avec critère sur le degré du reste
PGCD : Plus grand diviseur en valeur absoluePGCD : Polynôme diviseur de plus grand degré
Calcul modulo un nombres premier (i.e. dans Z/pZ\Z/p\Z)Calcul modulo un polynôme irréductible (i.e. dans R[X]/(P)\R[X]/(P))

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 PP irréductible sur R\R, en notant nn son degré, on pourra calculer sur les séquences finies (x0,x1,...,xn1)(x_0, x_1, ..., x_{n-1}) comme on calcule sur R\R : avec des symboles ++, -, ×\times et //

Tous ces résultats ont été obtenu en partant de R\R, grâce à des algorithmes qui utilisent les opérateurs de R\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 Q\Bbb{Q} et les corps finis Z/pZ\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 KK) et d’un polynôme P=a0+a1X+a2X2+...+anXn{P = a_0 + a_1 X + a_2 X^2 + ... + a_n X^n} irréductible sur KK, on peut constuire un nouveau corps dont les éléments sont des séquences (x0,x1,...,xn1)(x_0, x_1, ..., x_{n-1}) d’éléments de KK.

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

Un tel corps est appelé une extension finie de KK.

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

Extensions finies de Q\Bbb{Q}

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

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

Calculer avec des polynômes rationnels modulo X22X^2 - 2 revient à calculer avec des nombres de la forme a+b2a + b \sqrt{2}aa et bb 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+22)(122)=12(1 + \frac{\sqrt{2}}{2})(1 - \frac{\sqrt{2}}{2}) = \frac{1}{2}.

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

Extensions finies de R\R

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

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

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

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

Mathématiquement, on définit donc C=R[X]/(1+X2)\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)(a, b).

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

Le résultat suivant n’est par exemple que la traduction du calcul (1+i)2=2i(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)(a,b), au a+bXa + bX, on obtient les règles de calcul suivantes :

(a+bX)×1=a+bXmod1+X2(a+bX)×X=aX+bX2=b+aXmod1+X2(a + bX) \times 1 = a + bX \mod{1 + X^2} \\ (a + bX) \times X = aX + bX^2 = -b + aX \mod{1 + X^2}

C’est-à-dire :

(a,b)×(1,0)=(a,b)(a,b)×(0,1)=(b,a)(a, b) \times (1, 0) = (a, b) \\ (a, b) \times (0, 1) = (-b, a)

Le produit d’un polynôme par un autre modulo PP é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 :

(abba)=a2+b2(cosθsinθsinθcosθ)\begin{pmatrix} a & -b \\ b & a \end{pmatrix} = \sqrt{a^2 + b^2} \begin{pmatrix} \cos{\theta} & -\sin{\theta} \\ \sin{\theta} & \cos{\theta} \end{pmatrix}

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\R (par exemple, il n’est pas possible de définir une structure de corps sur les triplets (a,b,c)(a, b, c) de nombres réels…).

Extensions finies de F2F_2

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

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

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

Addition

+01
001
110

Multiplication

×01
000
101

Si l’on identifie 00 et 11 à 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 F2F_2 (et donc sur les polynômes à coefficients dans F2F_2) très rapidement.

💻 Calcul avec des polynômes binaires

Bien que les éléments de F2F_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 F2F_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 22, l’inversion pow(x, -1) est ici très simple puisque 11 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 F2F_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 F2F_2

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

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

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

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

Les produits correspondant sont : X2X^2, X(1+X)=X+X2{X(1+X) = X + X^2} et (1+X)2=1+(1+1)X+X2=1+X2{(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)(a, b) de chiffres binaires identifiés à des polynômes modulo PP 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 F2F_2 : P=1+X2+X3+X4+X8{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 11 et 44, représentés en binaire par des entiers compris entre 22 et 2512^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é F256F_{256}.

💡 En fait, on montre que pour tout nombre premier pp et pour tout entier n>0n > 0, on peut construire un corps fini de taille pnp^n, qui est une extension algébrique simple de FpF_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 :

QR code partiellement lisible

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 F2F_2

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

On définit :

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

Encodage

  • T=M×XdegGT = M \times X^{\deg{G}} est un polynôme de degré degM+degG=15\deg{M} + \deg{G} = 15 qui correspond en binaire au message décalé « degG\deg{G} fois » à gauche.
  • On effectue sa division euclidienne par GG : T=G×Q+RT = G \times Q + R avec degR<degG\deg{R} < \deg{G}
  • On retranche RR à TT pour ne conserver que le polynôme P=G×QP = G \times Q, multiple du générateur et de degré 1515.
  • C’est la représentation de PP en binaire qui est stockée, sur 1515 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 F2F_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 F256F_{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 0\neq 0 du corps peut s’écrire sous la forme αk\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 :



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

© 2020 Lipsum.dev — Contactez-moi (questions, remarques, etc.)