- A propos de sympy.GF et des corps finis
- Installation et importation de sympy
- Création d'un corps fini GF(p)
- Arithmétique de base dans GF(p)
- Calcul d'inverse modulaire dans GF(p)
- Polynômes irréductibles et extension de corps GF(pn)
- Opérations dans GF(pn) avec les éléments du corps
- Réduction polynomiale et division
- Fonctions utiles : degré, coefficients, évaluation
- Exemple complet : construction d'un code correcteur d'erreurs (simplifié)
Ce tutoriel couvre l'utilisation du module sympy pour travailler avec des corps finis (GF(p) ou GF(p^n)) via la fonction GF et la classe Poly.
Nous aborderons la création, les opérations arithmétiques, le calcul d'inverses, les polynômes et les extensions de corps. Ce tutoriel vous présentera les bases de sympy.GF pour les corps finis qui vous permettera ainsi d'explorer des sujets avancés comme la factorisation de polynômes, les codes correcteurs, ou la cryptographie etc...
1. A propos de sympy.GF et des corps finis
sympy est une bibliothèque de calcul symbolique en Python. Elle permet de travailler avec des corps finis (aussi appelés Galois Fields) via la classe GF et les objets Poly.
Un corps fini noté GF(p) ou GF(p^n) est un ensemble fini d'éléments sur lequel l'addition, la soustraction, la multiplication et la division (sauf par zéro) sont définies.
p est un nombre premier (caractéristique), et n est le degré d'extension.
Dans ce tutoriel, nous utiliserons sympy 1.12+. La fonction GF permet de créer un corps fini, et Poly permet de manipuler des polynômes sur ce corps.
2. Installation et importation de sympy
Avant de commencer, assurez-vous que sympy est installé. Utilisez pip pour l'installer si ce n'est pas déjà fait.
|
1 2 |
# Installation (dans votre terminal) # pip install sympy |
Ensuite, importez les modules nécessaires :
|
1 2 |
from sympy import symbols, Poly, GF from sympy.abc import x |
3. Création d'un corps fini GF(p)
Pour créer un corps fini GF(p) où p est un nombre premier, on utilise GF(p).
|
1 2 3 4 5 6 |
from sympy import GF, Poly from sympy.abc import x # Créer GF(7) - corps fini modulo 7 F7 = GF(7) print("Corps F7 :", F7) |
Sortie :
|
1 |
Corps F7 : GF(7) |
On peut alors créer des polynômes sur ce corps en utilisant Poly avec l'argument domain=F7.
|
1 2 3 |
# Polynôme sur GF(7) : 3x^2 + 5x + 2 poly = Poly(3*x**2 + 5*x + 2, x, domain=F7) print("Polynôme dans F7 :", poly) |
Sortie :
|
1 |
Polynôme dans F7 : Poly(3*x**2 + 5*x + 2, x, domain=GF(7)) |
4. Arithmétique de base dans GF(p)
Les opérations +, -, *, / (avec inverse) sont possibles directement sur les coefficients grâce au domaine GF.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
from sympy import GF, Poly from sympy.abc import x F5 = GF(5) p1 = Poly(2*x + 3, x, domain=F5) p2 = Poly(4*x + 1, x, domain=F5) # Addition print("p1 + p2 =", p1 + p2) # Soustraction print("p1 - p2 =", p1 - p2) # Multiplication print("p1 * p2 =", p1 * p2) """ output: p1 + p2 = Poly(x - 1, x, modulus=5) p1 - p2 = Poly(-2*x + 2, x, modulus=5) p1 * p2 = Poly(-2*x**2 - x - 2, x, modulus=5) """ |
5. Calcul d'inverse modulaire dans GF(p)
Pour calculer l'inverse d'un élément non nul dans GF(p), on utilise la méthode inv de la classe Poly ou l'opérateur **-1.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
from sympy import GF from sympy.abc import x F7 = GF(7) # Créer un élément du corps (pas un polynôme) element = F7(3) inv_element = element ** -1 print("Inverse de 3 dans GF(7) :", inv_element) # output : Inverse de 3 dans GF(7) : 5 mod 7 # Si vous voulez un polynôme from sympy import Poly poly = Poly(inv_element, x, domain=F7) print("Inverse de 3 dans GF(7) (polynôme) :", poly) # output : Inverse de 3 dans GF(7) (polynôme) : Poly(-2, x, modulus=7) |
6. Polynômes irréductibles et extension de corps GF(p^n)
Pour créer une extension de corps GF(p^n), on spécifie un polynôme irréductible de degré n.
Sympy permet de travailler avec des polynômes modulo ce polynôme.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
from sympy import GF, Poly, symbols from sympy.abc import x # Polynôme irréductible sur GF(2) : x^2 + x + 1 (degré 2) F2 = GF(2) irr_poly = Poly(x**2 + x + 1, x, domain=F2) # Créer le corps d'extension GF(2^2) F4 = F2.extension(irr_poly) print("Corps F4 :", F4) # Créer un élément du corps d'extension a = F4(x) # a est la classe de x modulo x^2+x+1 print("a =", a) print("a^2 =", a**2) # devrait donner x+1 (car x^2 = x+1 mod x^2+x+1) |
Sortie :
|
1 2 3 |
Corps F4 : GF(2^2, modulus=x**2 + x + 1) a = x a^2 = x + 1 |
7. Opérations dans GF(p^n) avec les éléments du corps
Les éléments du corps d'extension peuvent être additionnés, multipliés, et inversés.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
from sympy import GF, Poly, symbols from sympy.abc import x F2 = GF(2) irr = Poly(x**2 + x + 1, x, domain=F2) F4 = F2.extension(irr) a = F4(x) b = F4(x + 1) # x+1 print("a =", a) print("b =", b) print("a + b =", a + b) # x + (x+1) = 1 print("a * b =", a * b) # x*(x+1) = x^2+x ≡ (x+1)+x = 1 mod (x^2+x+1) print("a * b =", a * b) print("Inverse de a :", a**(-1)) # inverse de x dans GF(4) est x+1 |
Sortie :
|
1 2 3 4 5 |
a = x b = x + 1 a + b = 1 a * b = 1 Inverse de a : x + 1 |
8. Réduction polynomiale et division
La division de polynômes dans un corps fini peut être effectuée avec div ou quo/rem.
|
1 2 3 4 5 6 7 8 9 10 11 |
from sympy import GF, Poly, div from sympy.abc import x F7 = GF(7) p = Poly(x**3 + 2*x**2 + 3*x + 4, x, domain=F7) q = Poly(x + 1, x, domain=F7) # Division euclidienne dans F7 quotient, reste = div(p, q) print("Quotient :", quotient) print("Reste :", reste) |
Sortie :
|
1 2 |
Quotient : Poly(x**2 + x + 2, x, domain=GF(7)) Reste : Poly(2, x, domain=GF(7)) |
9. Fonctions utiles : degré, coefficients, évaluation
On peut extraire des informations sur les polynômes, comme le degré, les coefficients, et évaluer en un point.
|
1 2 3 4 5 6 7 8 9 |
from sympy import GF, Poly from sympy.abc import x F7 = GF(7) p = Poly(3*x**2 + 5*x + 2, x, domain=F7) print("Degré :", p.degree()) print("Coefficients :", p.all_coeffs()) print("Évaluer en x=2 :", p.eval(2)) # 3*4 + 5*2 + 2 = 12+10+2=24 ≡ 3 mod7 |
Sortie :
|
1 2 3 |
Degré : 2 Coefficients : [3, 5, 2] Évaluer en x=2 : 3 |
10. Exemple complet : construction d'un code correcteur d'erreurs (simplifié)
Voici un exemple d'utilisation de GF(2^3) pour simuler un code de Reed-Solomon miniature.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
from sympy import GF, Poly, symbols from sympy.abc import x # GF(2^3) avec polynôme irréductible x^3 + x + 1 F2 = GF(2) irr = Poly(x**3 + x + 1, x, domain=F2) F8 = F2.extension(irr) # Créer un message : [a, b] avec a=α, b=α^2 (α = x) alpha = F8(x) message = [alpha, alpha**2] print("Message :", message) # Codage simple : évaluer le polynôme M(t) = a + b*t en deux points M = Poly(message[0] + message[1]*x, x, domain=F8) print("M(t) =", M) # Évaluer en t=1 et t=α codeword = [M.eval(1), M.eval(alpha)] print("Mot de code :", codeword) |
Sortie :
|
1 2 3 |
Message : [x, x**2] M(t) = Poly(x*t + x, t, domain=GF(2^3, modulus=x**3 + x + 1)) Mot de code : [x**2 + x, x**3 + x**2] # (les valeurs sont réduites modulo le polynôme) |
Auteur : Younes Derfoufi
Lieu de travail : CRMEF OUJDA
Site Web : www.tresfacile.net
Chaine YouTube : https://www.youtube.com/user/InformatiquesFacile
Me contacter : https://www.tresfacile.net/me-contacter/
