Expliquer un corps fini

Cet article parlera de mathématiques, contrairement aux autres. On présentera ce qu’est, de manière générale, un corps puis nous construirons un corps fini premier pour, dans l’article suivant, obtenir le corps dont nous avons besoin et les structures algébriques utiles à l’aide de briques orientées objet.

1. Un peu de mathématiques

Nous commençons par définir ce qu’est un corps avant de nous intéresser à une construction possible.

1.1. Qu’est-ce qu’un corps ?

En gros, un corps est un ensemble de « nombres » dans lequel on peut effectuer les quatre opérations sans se demander s’il n’y a pas un loup (dans Paris) ou une impossibilité (à part, bien sûr, diviser par 0).

Formellement, on se donne un ensemble K sur lequel on a deux opérations notées habituellement + et ×.

L’addition a les propriétés suivantes :

• Elle est commutative : a+b=b+a pour tous a et b de K ;
• Elle est associative : (a+b)+c=a+(b+c) quels que soient a, b, c∈K ce qui veut dire en pratique qu’on n’est pas tenu d’utiliser ni d’écrire des parenthèses ;
• La loi possède un élément neutre 0 pour lequel ∀a∈K, a+0=0+a=a ;
• Tout élément a a un « inverse » b qu’on appelle opposé, c’est-à-dire que a+b=b+a=0. On note b=−a et a−b=a+(−b).

Ceci veut dire que (K,+) est un groupe commutatif.

(K*,×) est aussi un groupe, non nécessairement commutatif (K* signifie K sans 0). L’inverse de a≠0 est noté 1/a ou a⁻¹ puisque a⁻¹×a=a×a⁻¹=1.

Enfin, la multiplication est distributive par rapport à l’addition, ce qui veut dire que ∀a, b, c∈K, (a+b)×c=a×c+b×c et de même à gauche. Par convention, la multiplication est prioritaire sur l’addition, ce qui veut dire que a+b×c=a+(b×c).

On a tous déjà calculé dans des corps comme ℝ (l’ensemble des nombres réels) ou ℂ (les nombres complexes utilisés par exemple en électronique analogique). Ces deux derniers corps contiennent tous les deux le corps ℚ des fractions des entiers relatifs, c’est même le plus petit sous-corps qu’ils contiennent (on appelle ce sous-corps leur sous-corps premier). Ces trois corps sont infinis.

En revanche, l’ensemble ℤ des entiers relatifs n’est pas un corps car seuls 1 et −1 ont des inverses dans ℤ pour la multiplication (qui sont eux-mêmes), ℤ est cependant un anneau muni d’une division euclidienne.

1.2 Premiers corps finis

Évidemment, un corps fini ne contient pas ℚ, ilest construit autrement.

On commence par choisir un nombre premier p, le reste de la division d’un nombre entier relatif par p est donc entre 0 et p−1. Voilà notre premier corps fini : {0,1,…,p−1} muni de l’addition et de la multiplication modulo p qu’on note ℤ/pℤ ou ℤ_p, parfois ℤ/p. Les corps finis ont tous pour sous-corps premier un corps fini du type ℤ/pℤ avec p premier (p est sa caractéristique).Pour distinguer les éléments de ℤ/pℤ des nombres entiers classiques, on les écrira surmontés d’une barre.

Ainsi, modulo 7 :  car 11=1×7+4 et .

Qu’en est-il de la division, par exemple par  ?

Si le corps est petit, on peut chercher l’inverse à la mainautrement dit par force brute : . Donc diviser par  revient à multiplier par son inverse qui est . L’algorithme efficace utilisé dans notre cas sera l’algorithme d’Euclide étendu qui donne les coefficients de Bezout u et v dans l’équation 4×u+7×v=1 (où u et v sont des entiers relatifs). En fait, seul u nous est utile, on l’obtient facilement à la main par la méthode de Blankinship (ou pivot de Gauß) [4] où on effectue des opérations élémentaires (combinaisons linéaires ou permutations) sur les lignes de la matrice suivante :

La première colonne contient un seul 1 et le reste est constitué de 0, on a terminé l’algorithme : u=2, v=−1 et 7×(−1)+2×4=1 donc l’inverse de  est bien  dans ℤ/7ℤ.

Voici la fonction qui retourne l’inverse de a modulo n, elle se trouve dans qrcodeoutils.py :

Il s’agit ici de l’algorithme classique qu’on peut alléger des variables v et vv qui n’ont aucune utilité dans la suite. On n’a pas vérifié si le PGCD était bien égal à 1, ce qui est immédiat dans un corps, on n’a pas non plus vérifié si a==0.

Le corps fini utilisé dans les codes QR n’a pas cette structure, trop simple, qu’on verra dans la partie suivante : un corps fini est un espace vectoriel de dimension finie sur un corps fini premier, tout comme ℂ est un espace vectoriel de dimension 2 sur ℝ (qui n’est cependant pas un corps premier). Voyons comment construire un corps ℤ/pℤ en créant une classe munie de toutes les méthodes adéquates.

2. Construction effective de ℤ/pℤ

On va construire pour commencer l’anneau ℤ/pℤ dans le cas où p est un nombre premier, c’est-à-dire le corps ℤ/pℤ, en Python.

2.1 Mémorisation

Mon second code, naïf, utilise une fonction qui retourne une classe Zn qui dépend du paramètre p (la classe est donc paramétrée). La construction fonctionne à peu près mais coince quand il faut commencer à vérifier les types dans les classes emboîtées. J’ai donc utilisé le code de Jeremy Kun [5] qui ressemble au mien [2], aux décorateurs prêts.

Un décorateur permet de modifier une fonction sans utiliser une batterie de tests (regardez mon deuxième code où je passe beaucoup de temps à vérifier finement les types). Le code de Jeremy [6] est certes puissant mais j’ai dû le modifier ponctuellement, notamment pour l’opération puissance ou la division euclidienne (sans intérêt dans un corps). Le voici en version francisée, dans qrcodeoutils.py :

Voici la sortie de ce code :

On teste si la valeur est mémorisée. Sinon, on la stocke dans le cache qui est un simple dictionnaire. Évidemment, ce code stocke absolument tout sans contrôle. Dans un code qui tourne indéfiniment, il faudrait au minimum contrôler la taille du cache.

2.2 Construction de la classe modulo p

La fonction defzn définit une classe qui dépend du paramètre p qui est un nombre entier positif. Elle est mémorisée donc deux classes de mêmes paramètres p sont en fait identiques et non deux classes distinctes qui font néanmoins la même chose.

Le constructeur d’un élément de la classe le définit par ses propriétés : sa valeur et le corps auquel il appartient.

On définit l’addition, la soustraction et la multiplication dans ℤ/pℤ qui permettent d’utiliser les opérateurs binaires +, − et *.

La division (/ en Python 3 et non // qui est la division euclidienne que nous utiliserons plus tard mais pas dans un corps, et qui est définie par la méthode __floordiv__) nécessite l’inverse modulo p puisque diviser par un nombre est équivalent à multiplier par son inverse (comme on l’apprend au collège) soit , ∀a∈ℤ/pℤ, ∀b∈ℤ/pℤ*, la fonction _inverse est définie plus loin.

La négation unaire (autrement dit l’opposé) est définie ainsi que le test d’égalité. Remarquez que les comparaisons < ou ⩾ n’ont aucun intérêt.

Il s’agit de l’opérateur de puissance ** y compris si l’exposant est négatif. Dans ce cas, on calcule la puissance positive de l’inverse. L’exponentiation rapide revient à décomposer l’exposant en base 2, c’est l’idée de la multiplication pratiquée en Égypte antique et encore aujourd’hui en Russie.

Par exemple si on doit calculer a⁴⁵=a¹a⁴a⁸a³², la suite des divisions de 45 par les puissances de 2 donne :

La première fonction est utilisée par les fonctions internes str et print, la deuxième quand on affiche une liste d’éléments de la classe, voir ci-après.

Dans la fonction qui calcule l’inverse, on ne vérifie pas si l’élément est bien inversible, comme on travaille dans un corps fini, on suppose que tout va bien. Au cas où on diviserait quand même par 0, une exception sera levée dans la boucle dans la fonction bezout lors de la division euclidienne (ligne 04 du code source de bezout, voir plus haut).

Enfin, on dote la classe elle-même des deux propriétés : son cardinal et son nom et on la retourne.

Jouons un peu avec notre classe :

On obtient ceci :

Conclusion

Voici ce qu’on peut faire en Python. Le problème est qu’il faut empiler beaucoup de briques par-dessus cette structure alors qu’en fait, on peut accélérer le processus. Ce qu'il ne faut pas faire pour corriger un code QR... et ce n'est pas fini !

Références

[1]  PATROIS N., « Décoder un code QR », GNU/Linux Magazine n°194, p. 32 à 41.

[2] Le code et les exemples sont présents ici : https://github.com/GLMF/GLMF194.

[3] LANGROGNET F., « Peut-on vraiment calculer avec un ordinateur : les opérations », GNU/Linux Magazine n°194, p. 22 à 31.

[4] L’algorithme de Blankinship est présenté ici : http://www.les-mathematiques.net/phorum/read.php?5,516246.

[5] http://jeremykun.com/2014/03/13/programming-with-finite-fields/. J’ai francisé le code et je lui ai ajouté et supprimé ce qui me semble ou non pertinent mathématiquement (par exemple, la division euclidienne ou la valeur absolue n’ont aucun intérêt dans un corps fini).

[6] http://jeremykun.com/2012/03/22/caching-and-memoization/.