Étape 4

Dans cette étape, nous allons coder les opérations sur le corps fini qui nous intéresse: Nos éléments seront des polynômes aux coefficients binaires modulo un polynôme \(p\) dit primitif. On note ce corps \(\mathbf{F}_2[X]/(p)\).

Pour ce projet, nous utiliserons le polynôme primitif \(p = x^8 + x^4 + x^3 + x^2 + 1\) (représenté en Python par le nombre entier 285, ou 0b100011101 en notation binaire). Comme le degré de ce polynôme primitif est de 8, les éléments de notre corps seront des polynômes aux coefficients binaires de dégré au maximum 7. Au final, nos éléments peuvent être vu comme des nombres sur 8 bits (entre 0 et 255), donc des octets. On note parfois ce corps \(\mathbf{F}_{256}\) ou encore \(GF(256)\).

Le code que vous allez implémenter aujourd'hui nous servira au calcul des octets de correction d'erreur des QR-codes générés par votre programme.

Corps de Galois

Nous allons implémenter une classe (CorpsGalois) pour représenter le corps fini \(\mathbf{F}_2[X]/(p)\). Cette classe prend comme paramètre un polynôme primitif \(p\), représenté par un entier p. Les diverses opérations du corps fini (addition, soustraction, multiplication, division, puissance) correspondent à des méthodes de la classe.

Dans le fichier galois.py, copiez le code suivant:

class CorpsGalois(object):

    def __init__(self, p):
        # Initialisation des champs.
        self.degre_max = (2 ** degre(p)) - 1
        self.exps = [0] * self.degre_max
        self.logs = [0] * (self.degre_max + 1)

        # À compléter.
        # Remplir les listes self.exps et self.logs

    def plus(self, a, b):
        return a ^ b
       
    def moins(self, a, b):
        return a ^ b

    def fois(self, a, b):
        # À implémenter
        pass

    def division(self, a, b):
        # À implémenter
        if b == 0:
            raise ZeroDivisionError()
        pass
    
    def puissance(self, a, b):
        # À implémenter
        pass

Les méthodes plus et moins vous sont données, alors que les méthodes fois, division et puissance sont à implémenter.

La raison pour laquelle nous utilisons une classe est le fait que cela permette de partager facilement des valeurs entre les différentes méthodes. Les valeurs partagées sont: self.degre_max, self.exps, self.logs. Ces valeurs sont calculées dans le constructeur de la classe (la méthode __init__). Ces valeurs servent à faciliter le calcul des opérations fois, division, et puissance, tel que nous allons le discuter.

Générateur

Dans le corps fini \(\mathbf{F}_2[X]/(p)\), si \(p\) est un polynôme primitif (comme ce sera le cas dans le cadre de ce projet), le polynôme \(x\) (soit 0b10 ou 2) est ce qu'on appelle un générateur de \(\mathbf{F}_2[X]/(p)\): tous les éléments du corps, sauf 0, sont des puissances de ce générateur !

Ci-dessous sont listées les puissances de \(x\) de 0 à 255 (c'est-à-dire \(q-1\)) étant donnée le polynôme primitif \(p = x^8 + x^4 + x^3 + x^2 + 1\). On remarque que tous les nombres entre 1 et 255 correspondent tous à une puissance de \(x\) (vous pouvez vérifier !).

De plus, à la puissance 255, le résultat est le même qu'à la puissance 0, c'est à dire 1 ! Le générateur est la racine-255 de l'unité.

Nous allons faire usage de ce générateur et de ses propriétés pour implémenter très efficacement les opérations qui nous intéressent.

Compléter le constructeur

Votre premier travail consiste à terminer l'implémentation du constructeur (la méthode __init__) de la classe. Le but ici est de remplir les listes self.exps et self.logs (initialement remplies de 0). La liste self.exps devra contenir, pour chaque index \(i\) de 0 à self.max_degre (non-compris), la valeur \(x^i\) prise modulo le polynôme primitif \(p\).

La table présentée dans la section précédente montre le contenu de self.exps dans le cas particulier où le polynôme primitif est \(x^8 + x^4 + x^3 + x^2 + 1\).

Quant à self.logs, il faudra faire en sorte que self.logs[a] == i quand self.exps[i] == a. On ne se souciera pas de la valeur à l'index 0 qui restera inutilisé.

Une fois ces deux listes remplies, vous pouvez procéder à la suite: l'implémentation des méthodes de CorpsGalois. La méthode d'addition vous est directement donnée.

Indices

Pour rappel, pour multiplier un polynôme par \(x\), il suffit simplement de décaler les bits de sa représentation binaire de un cran sur la gauche (ce que vous pouvez faire en utilisant << 1).

Pour calculer le modulo avec le polynôme primitif, vous pouvez simplement faire appel à votre fonction modulo. Il est aussi possible de se passer de cette méthode et de soustraire (^) directement le polynôme primitif p du polynôme résultat de la multiplication par \(x\) lorsque celui-ci atteint le même degré que \(p\). (Voyez-vous pourquoi ?)

Utiliser le générateur et les propriétés des logarithmes pour calculer

L'existence du générateur \(x\), ainsi que les propriétés des logarithmes, nous permettent de calculer très efficacement les différentes opérations du corps fini grâces aux propriétés suivantes:

1. \(x^a \cdot x^b = x^{a + b}\)
2. \(x^a / x^b = x^{a - b}\)
3. \((x^a)^n = x^{a \cdot n}\)
4. \(x^{q-1} = x^0 = 1\)

Ces propriétés peuvent être utilisées pour implémenter efficacement les différentes méthodes de la classe CorpsGalois. Les détails sont présentés ci-après.

Multiplication

Pour multiplier deux valeurs \(a\) et \(b\), on prend simplement (grâce à self.logs) la puissance de \(x\) correspondant respectivement à \(a\) et à \(b\). Il suffit ensuite de calculer la somme de ces deux puissances, puis de trouver la valeur correspondante (grâce à self.exps).

Un détail subsiste: Comme vous avez uniquement rempli la liste self.exps de 0 à self.degre_max - 1, il faudra s'assurer de retirer self.degre_max de la somme des puissances si celle-ci sort de l'intervalle. Grâce à la 4^ième propriété, cette soustraction ne changera rien à la valeur du résultat !

Aussi, il vous faudra traîter à part le cas où a ou b sont égaux à 0. En effet, la valeur 0 n'a pas de puissance associée. Il est donc impossible d'utiliser self.logs dans ce cas.

Division

Le procédé est similaire à celui de la multiplication. À la place d'additionner les puissances, il faudra procéder à une soustraction. De plus, il faudra s'assurer que la puissance résultante soit dans le bon intervalle pour la liste.

Dans le cas où le diviseur b est 0, on lancera une exception. Le cas où a est 0 sera ensuite traité à part.

Puissance

Pour calculer la puissance n d'un élément a, on utilisera la même technique que pour les opérations précédente :

• On utilise self.logs pour trouver la puissance de \(x\) correspondante,
• On multiplie cette puissance par n,
• On retourne dans l'intervalle entre 0 et self.degre_max - 1,
• On utilise self.exps pour calculer la valeur du polynôme \(x\) pris à cette puissance.

De nouveau, il faudra traiter le cas où a est égal à 0 à part.

Tester votre code

À la fin de cette quatrième étape du projet, vous pouvez exécuter la commande suivante dans le Terminal pour vérifier si vous avez bien implémenté les fonctionnalités attendues:

python3 -m unittest test.Etape4