En Sage, pour définir un corps fini du type $\mathbf Z/p\mathbf Z$, avec $p$ premier, on dispose de la commande IntegerModRing
.
A=IntegerModRing(13); A
En donnant un nom à l'anneau, on peut alors utiliser l'application quotient canonique $\mathbf Z \to \mathbf Z/p\mathbf Z$.
A(54)
Les "modèles" pour les corps finis à $p^n$ éléments sont des quotients de l'anneau de polynômes $\mathbf Z/p\mathbf Z[X]$. En Sage, on ne peut pas introduire une nouvelle indéterminée sans la définir.
3*X+5
Pour définir l'anneau de polynômes $\mathbf Z/p\mathbf Z[X]$, on procède comme suit:
R.<X> = PolynomialRing(A);R
Ou bien comme cela:
R1 = PolynomialRing(A,'X'); R1
3*X+5
On dispose des fonctions usuelles pour l'arithmétique des polynômes: %, //, gcd, xgcd
.
(3*X^5+5)%(5*X^2+5)
Normalement, vous devriez pouvoir les recoder en quelques lignes et minutes...
def pgcd(P,Q):
return 1
On peut alors définir le quotient de $R$ par un idéal (quelconque).
P=2*X^2+3*X+1
RR=QuotientRing(R,ideal(P)); RR
RR(5*X^6+4*X^5+5)^-1
Noter que la construction précédente est très générale: $P$ n'est pas supposé irréductible!
Vérifiez que vous êtes capables de coder vous mêmes la fonction qui teste si un élément est inversible dans $RR$ et le cas échéant en renvoie son inverse.
Au fait, le $P$ précédent est-il irréductible?
def inverse_dans_RR(Q):
return 0
En Sage, il existe un raccourci pour définir un corps fini à $p^n$ éléments, il s'agit de la fonction GF()
(comme Galois Field).
R2=GF(8); R2
Sage a défini notre corps à 8 éléments comme un quotient de $\mathbf Z/2\mathbf Z[x]$ par un certain polynôme irréductible de degré $3$ qu'il a choisi tout seul (avantage ou inconvénient?). Notez qu'il a aussi choisi tout seul le nom du générateur...
On peut accéder à ce polynôme et aux éléments:
R2.modulus()
R2.gen()
Ici, gen
veut bien entendu dire générateur. En quel sens $z_3$ est-il un générateur?
for i in R2:
print (i)
On peut bien spécifier le nom du générateur et le polynôme:
R3.<y>=GF(13^4,modulus=x^4 + 3*x^2 + 12*x + 1); R3
R3.modulus()
Il est utile d'avoir accès aux fonctions suivantes:
R3.cardinality()
z=R3.multiplicative_generator(); z
z.minimal_polynomial()
y.multiplicative_order()
z1=z.polynomial(); z1.coefficients()
Il y a aussi une fonction renvoyant l'ordre additif d'un élément. Qu'en pensez-vous?
Codez vos propres fonctions ordre
et generateur
pour R3.
def ordre(a):
return 0
def generateur():
return 0
Coder votre fonction pol_min
en utilisant les fonctions d'algèbre linéaire suivantes pour définir des matrices, en calculer le rang et le noyau.
M=Matrix(A,3,3,[i for i in range(9)]); M
M.rank()
V=M.right_kernel(); V
V.gen()
Sage sait factoriser les polynômes à coefficients dans un corps fini, grâce à la commande factor
.
R1.<X>=PolynomialRing(Zmod(7)); R1
P=X^6 + X^4 + 5*X^3 + 4*X^2 + 6*X + 3
factor(P)
Qu'en déduit-on sur $P$?
K1.<X>=PolynomialRing(GF(7^6));
factor(K1(P))
Était-ce prévisible?
K2.<X>=PolynomialRing(GF(7^3));
factor(K2(P))
Était-il prévisible d'avoir 3 facteurs de degré 2?
a) Montrer que le polynôme $P=X^3 + 3X + 3 \in \mathbf F_5[X]$ est sans facteur carré.
b) Utiliser l'algorithme de Berlekamp pour montrer que $P$ est irréductible.
c) Utiliser cet algorithme pour factoriser les polynômes suivants dans $(\mathbf F_5)[X]$: $P_1:=X^5+3X^2+3X+1$ et $P_2=X^6 + 2X^5 + 3X^3 + 4X^2 + 2X + 2$.
d) Ecrire une fonction Berlekamp(p,P)
qui factorise le polynôme $P$ dans $\mathbf F_p[X]$.
Exercice : définir en Sage un corps $K$ à $5^4$ éléments.
A partir de quel polynôme irréductible est-il construit?
Déterminer un sous-corps $K_1$ à $5^2$ éléments de $K$: