{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Corps finis" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## $\\mathrm {I}$- Définition et éléments" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "En Sage, pour définir un corps fini du type $\\mathbf Z/p\\mathbf Z$, avec $p$ premier, on dispose de la commande `IntegerModRing`." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Ring of integers modulo 13" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A=IntegerModRing(13); A" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "En donnant un nom à l'anneau, on peut alors utiliser l'application quotient canonique $\\mathbf Z \\to \\mathbf Z/p\\mathbf Z$." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "A(54)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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]$.\n", "En Sage, on ne peut pas introduire une nouvelle indéterminée sans la définir. " ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "ename": "NameError", "evalue": "name 'X' is not defined", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mInteger\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0mX\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0mInteger\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mNameError\u001b[0m: name 'X' is not defined" ] } ], "source": [ "3*X+5" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour définir l'anneau de polynômes $\\mathbf Z/p\\mathbf Z[X]$, on procède comme suit:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Univariate Polynomial Ring in X over Ring of integers modulo 13" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "R. = PolynomialRing(A);R" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ou bien comme cela:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Univariate Polynomial Ring in X over Ring of integers modulo 13" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "R1 = PolynomialRing(A,'X'); R1" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3*X + 5" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "3*X+5" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On dispose des fonctions usuelles pour l'arithmétique des polynômes: `%, //, gcd, xgcd`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Normalement, vous devriez pouvoir les recoder en quelques lignes et minutes..." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "def pgcd(P,Q):\n", " if (Q.degree()==0):\n", " return Q;\n", " elif (Q.degree()<0):\n", " return P;\n", " else:\n", " return pgcd(Q,P%Q)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2*X" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pgcd(X*(X+1),X*(X-1))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut alors définir le quotient de $R$ par un idéal (quelconque)." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2*X^2 + 3*X + 1" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P=2*X^2+3*X+1; P" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Univariate Quotient Polynomial Ring in Xbar over Ring of integers modulo 13 with modulus X^2 + 8*X + 7" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "RR=QuotientRing(R,ideal(P)); RR" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Xbar + 12" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "RR(5*X^6+4*X^5+5)^-1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Noter que la construction précédente est très générale: $P$ n'est pas supposé irréductible!\n", "\n", "**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**.\n", "\n", "**Au fait, le $P$ précédent est-il irréductible?**" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "def inverse_dans_RR(Q):\n", " a=xgcd(P,Q)[1];\n", " if a[0]==1:\n", " return a[2]\n", " else:\n", " print(\"Element non inversible.\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Comme P est de degré $2$, on teste facilement s'il est irréductible en testant s'il a des racines." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "6\n", "12\n" ] } ], "source": [ "for i in A:\n", " if P.subs(i)==0:\n", " print(i)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il admet deux racines: il n'est donc pas irréductible!!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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)." ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Finite Field in z3 of size 2^3" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "R2=GF(8); R2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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...\n", "\n", "On peut accéder à ce polynôme et aux éléments:" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^3 + x + 1" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "R2.modulus()" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "z3" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "R2.gen()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Ici,** `gen` **veut bien entendu dire générateur. En quel sens $z_3$ est-il un générateur?**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "C'est un générateur comme algèbre: on obtient tous les éléments du corps comme des sommes de puissances de $z$." ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0\n", "z3\n", "z3^2\n", "z3 + 1\n", "z3^2 + z3\n", "z3^2 + z3 + 1\n", "z3^2 + 1\n", "1\n" ] } ], "source": [ "for i in R2:\n", " print (i)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut bien spécifier le nom du générateur et le polynôme:" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Finite Field in y of size 13^4" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "R3.=GF(13^4,modulus=x^4 + 3*x^2 + 12*x + 1); R3" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^4 + 3*x^2 + 12*x + 1" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "R3.modulus()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il est utile d'avoir accès aux fonctions suivantes:" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "28561" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "R3.cardinality()" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "8*y^3 + 12*y^2 + 9*y + 9" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "z=R3.multiplicative_generator(); z" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^4 + 12*x^3 + x + 11" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "z.minimal_polynomial()" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "595" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "y.multiplicative_order()" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[9, 9, 12, 8]" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "z1=z.polynomial(); z1.coefficients()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Il y a aussi une fonction renvoyant l'ordre additif d'un élément. Qu'en pensez-vous?*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ce n'est pas très utile: dans un corps fini, l'ordre additif d'un élément est toujours $p$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Codez vos propres fonctions** `ordre` **et** `generateur` **pour R3.**" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [], "source": [ "def ordre(a):\n", " i=1;\n", " b=a;\n", " while(b<>1):\n", " b=b*a;\n", " i=i+1\n", " return i" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "595" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ordre(y)" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [], "source": [ "def generateur():\n", " for x in R3:\n", " if x<>0:\n", " if ordre(x)==R3.cardinality()-1:\n", " return x\n", " " ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "y + 8" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "generateur()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0 1 2]\n", "[3 4 5]\n", "[6 7 8]" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M=Matrix(A,3,3,[i for i in range(9)]); M" ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 46, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M.rank()" ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Vector space of degree 3 and dimension 1 over Ring of integers modulo 13\n", "Basis matrix:\n", "[ 1 11 1]" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "V=M.right_kernel(); V" ] }, { "cell_type": "code", "execution_count": 76, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(7, 12, 7)" ] }, "execution_count": 76, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Z=V.gen(); A(1/2)*Z" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "L'idée est la suivante: trouver un polynôme annulateur d'un élément z c'est trouver une combinaison linéaire non triviale qui est nulle entre les puissances de y. Les puissances de z sont des vecteurs dans l'espace vectoriel qu'est notre corps fini, qu'on représente par leurs coordonnées dans la base canonique $(1,y, ..., y^n)$. " ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [], "source": [ "def pol(z): # fonction qui transforme un élément d'un corps fini en le vecteur (de bonne dimension) de ses coefficients.\n", " return [z.polynomial()[k] for k in range(4)]" ] }, { "cell_type": "code", "execution_count": 95, "metadata": {}, "outputs": [], "source": [ "def pol_min(z):\n", " RR.=PolynomialRing(A)\n", " l=[[1,0,0,0]];# On initialise la liste avec z^0=1\n", " M=matrix(A,l);\n", " k=1;\n", " while(M.rank()==k):\n", " l=l+ [pol(z^k)];\n", " k=k+1;\n", " M=matrix(A,l);\n", " V=M.transpose().right_kernel().gen();\n", " V=V*A(1/V[k-1]) # On le normalise pour que le polynôme minimal soit unitaire\n", " return sum([RR(V[r])*x^r for r in range(k)])" ] }, { "cell_type": "code", "execution_count": 97, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^4 + 8*x^3 + 7*x^2 + 9*x + 5" ] }, "execution_count": 97, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pol_min(z^2+1)" ] }, { "cell_type": "code", "execution_count": 98, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^4 + 8*x^3 + 7*x^2 + 9*x + 5" ] }, "execution_count": 98, "metadata": {}, "output_type": "execute_result" } ], "source": [ "(z^2+1).minimal_polynomial()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## $\\mathrm {II}$- Factorisation de polynômes et algorithme de Berlekamp" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Sage sait factoriser les polynômes à coefficients dans un corps fini, grâce à la commande `factor`.**" ] }, { "cell_type": "code", "execution_count": 99, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Univariate Polynomial Ring in X over Ring of integers modulo 7" ] }, "execution_count": 99, "metadata": {}, "output_type": "execute_result" } ], "source": [ "R1.=PolynomialRing(Zmod(7)); R1" ] }, { "cell_type": "code", "execution_count": 100, "metadata": {}, "outputs": [], "source": [ "P=X^6 + X^4 + 5*X^3 + 4*X^2 + 6*X + 3" ] }, { "cell_type": "code", "execution_count": 101, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "X^6 + X^4 + 5*X^3 + 4*X^2 + 6*X + 3" ] }, "execution_count": 101, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factor(P)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Qu'en déduit-on sur $P$?**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Sage dit que $P$ est irréductible..." ] }, { "cell_type": "code", "execution_count": 105, "metadata": {}, "outputs": [], "source": [ "K1.=PolynomialRing(GF(7^6));" ] }, { "cell_type": "code", "execution_count": 106, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(X + 6*z6) * (X + 2*z6^4 + 2*z6^3 + 3*z6^2 + 4*z6 + 6) * (X + z6^5 + 5*z6^4 + 4*z6^3 + 6*z6^2 + 3*z6) * (X + 3*z6^5 + z6^3 + 2*z6^2 + 3*z6 + 1) * (X + 6*z6^5 + 5*z6^4 + z6^2 + 3) * (X + 4*z6^5 + 2*z6^4 + 2*z6^2 + 5*z6 + 4)" ] }, "execution_count": 106, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factor(K1(P))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Était-ce prévisible?**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Oui: par contruction, K1 est contruit en rajoutant une racine de $P$ à $Z/7Z$... Donc $P$ n'est pas construction plus irréductible sur K1. De plus, la théorie des corps finis nous prédisait qu'un corps qui contenait une racine de $P$ les contient en fait toutes: on a ici les formules pour les autres racines. Noter que le vilain Sage est revenu à une notation $z_6$ au lieu de $X$." ] }, { "cell_type": "code", "execution_count": 107, "metadata": {}, "outputs": [], "source": [ "K2.=PolynomialRing(GF(7^3));" ] }, { "cell_type": "code", "execution_count": 108, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(X^2 + (z3^2 + z3 + 4)*X + 4*z3^2 + z3 + 1) * (X^2 + (2*z3^2 + 2*z3 + 1)*X + 3*z3^2 + 5*z3) * (X^2 + (4*z3^2 + 4*z3 + 2)*X + z3)" ] }, "execution_count": 108, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factor(K2(P))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Oui: $K_1$ est un espace vectoriel de dimension 6 sur $Z/7Z$. $K_2$ est un espace vectoriel de 3 sur $Z/7Z$, comme 3 divise 6, $K_2$ est un sous-corps de $K_1$ et $K_1$ est de dimension $2$ sur $K_1$. $P$ doit donc se factoriser par des polynômes de degré $2$. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Était-il prévisible d'avoir 3 facteurs de degré 2?**" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercice\n", "\n", "**a) Montrer que le polynôme $P=X^3 + 3X + 3 \\in \\mathbf F_5[X]$ est sans facteur carré**.\n", "\n", "**b) Utiliser l'algorithme de Berlekamp pour montrer que $P$ est irréductible.**\n", "\n", "**c) Utiliser cet algorithme pour factoriser les polynômes suivants dans $(\\mathbf F_5)[X]$:\n", "$P_1:=X^5+3X^2+3X+1$ et $P_2=X^6 + 2X^5 + 3X^3 + 4X^2 + 2X + 2$.**\n", "\n", "**d) Ecrire une fonction `Berlekamp(p,P)` qui factorise le polynôme $P$ dans $\\mathbf F_p[X]$.**" ] }, { "cell_type": "code", "execution_count": 125, "metadata": {}, "outputs": [], "source": [ "R. = PolynomialRing(IntegerModRing(5));" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On commence par tester si $P$ est sans facteur carré." ] }, { "cell_type": "code", "execution_count": 126, "metadata": {}, "outputs": [], "source": [ "P=x^3+3*x+3;D=P.derivative()" ] }, { "cell_type": "code", "execution_count": 127, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 127, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gcd(P,D)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "P et D étant premiers entre eux, P est sans facteur carré." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On calcule ensuite le noyau de l'application *linéaire* $\\Phi:v\\mapsto v^5-v$. On écrit pour cela sa matrice dans la base $1,x,x^2$." ] }, { "cell_type": "code", "execution_count": 133, "metadata": {}, "outputs": [], "source": [ "def coef(z,r): # fonction qui transforme un élément d'un corps fini en le vecteur (de bonne dimension) de ses coefficients.\n", " return [z[k] for k in range(r)]" ] }, { "cell_type": "code", "execution_count": 134, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0 4 3]\n", "[0 3 2]\n", "[0 2 4]" ] }, "execution_count": 134, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M=matrix(Zmod(5),3,[coef((x^(5*i)-x^i)%P,3) for i in range(3)]).transpose(); M" ] }, { "cell_type": "code", "execution_count": 130, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 130, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M.rank()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "M étant de rang $2$, P est bien irréductible..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On recommence pour P1 et P2." ] }, { "cell_type": "code", "execution_count": 131, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 131, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P1=x^5+3*x^2+3*x+1; D1=P1.derivative(); gcd(P1,D1)" ] }, { "cell_type": "code", "execution_count": 138, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0 4 1 0 1]\n", "[0 1 1 1 3]\n", "[0 2 4 3 0]\n", "[0 0 3 4 1]\n", "[0 0 4 2 3]" ] }, "execution_count": 138, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M1=matrix(Zmod(5),5,[coef((x^(5*i)-x^i)%P1,5) for i in range(5)]).transpose(); M1" ] }, { "cell_type": "code", "execution_count": 139, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 139, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M1.rank()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$A$ est de rang $2$: il y a donc 3 facteurs irréductibles dans $P1$. Pour les trouver, on trouve un élément non constant dans le noyau de $\\Phi$." ] }, { "cell_type": "code", "execution_count": 143, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[\n", "(1, 0, 0, 0, 0),\n", "(0, 1, 0, 1, 1),\n", "(0, 0, 1, 2, 4)\n", "]" ] }, "execution_count": 143, "metadata": {}, "output_type": "execute_result" } ], "source": [ "K1=M1.right_kernel(); K1.basis()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "De façon prévisible, le premier vecteur correspond aux polynômes constants. On en choisit un autre, par exemple le second. " ] }, { "cell_type": "code", "execution_count": 144, "metadata": {}, "outputs": [], "source": [ "y1=K1.basis()[1]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On le reconvertit en polynôme." ] }, { "cell_type": "code", "execution_count": 147, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^4 + x^3 + x" ] }, "execution_count": 147, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Z1=R(list(y1)); Z1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On sait qu'on va trouver un facteur de P1 en parcourant les polynômes Z1-i." ] }, { "cell_type": "code", "execution_count": 150, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, x + 2, 1, x^3 + 2*x^2 + 2*x + 3, x + 1]" ] }, "execution_count": 150, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ll=[gcd(P1,Z1-i) for i in Zmod(5)]; ll" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On a déjà trois facteurs, donc comme on en cherchait trois, on a terminé! Vérifions tout de même:" ] }, { "cell_type": "code", "execution_count": 152, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 152, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P1-ll[1]*ll[3]*ll[4]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "code", "execution_count": 153, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x + 2" ] }, "execution_count": 153, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P2=x^6 + 2*x^5 + 3*x^3 + 4*x^2 + 2*x + 2; D2=P2.derivative(); gcd(P2,D2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ici $P2$ n'est pas sans facteur carré: on le divise par $x+2$ et on peut faire comme avant. (En fait, vu qu'on a trouvé $x+2$, (déjà sous forme factorisé!!), on pourrait même simplifier par (x+2)^2)." ] }, { "cell_type": "code", "execution_count": 162, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 3*x^2 + 3*x + 1" ] }, "execution_count": 162, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Q2=P2//(x+2); Q2" ] }, { "cell_type": "code", "execution_count": 163, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(\n", "[0 4 1 0 1] \n", "[0 1 1 1 3] \n", "[0 2 4 3 0] \n", "[0 0 3 4 1] \n", "[0 0 4 2 3], 2\n", ")" ] }, "execution_count": 163, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M2=matrix(Zmod(5),5,[coef((x^(5*i)-x^i)%Q2,5) for i in range(5)]).transpose(); M2, M2.rank()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Rang $2$, donc on cherche 3 facteurs." ] }, { "cell_type": "code", "execution_count": 164, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[\n", "(1, 0, 0, 0, 0),\n", "(0, 1, 0, 1, 1),\n", "(0, 0, 1, 2, 4)\n", "]" ] }, "execution_count": 164, "metadata": {}, "output_type": "execute_result" } ], "source": [ "K2=M2.right_kernel(); B=K2.basis(); B" ] }, { "cell_type": "code", "execution_count": 167, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4*x^4 + 2*x^3 + x^2" ] }, "execution_count": 167, "metadata": {}, "output_type": "execute_result" } ], "source": [ "y2=B[2]; Z2=R(list(y2)); Z2" ] }, { "cell_type": "code", "execution_count": 168, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 1, x + 2, x^4 + 3*x^3 + 4*x^2 + 3, 1]" ] }, "execution_count": 168, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ll=[gcd(Q2,Z2-i) for i in Zmod(5)]; ll" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Là: on n'a trouvé que 2 facteurs. X+2 est visiblement irréductible, mais le second facteur de degré 4 ne l'est pas et il faut recommencer..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Après quelques lignes de calculs, on trouve $Q2=(x + 1) (x + 2)^2 (x^3 + 2*x^2 + 2*x + 3)$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On automatise tout ça..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def sfc(q): # Renvoie la partie sans facteur carré de P\n", " u=gcd(q,q.derivative());\n", " return(u, q//u)" ] }, { "cell_type": "code", "execution_count": 199, "metadata": {}, "outputs": [], "source": [ "def fact_sfc(p,P): #fonction qui factorise un polynôme sans facteur carré\n", " R. = PolynomialRing(IntegerModRing(p));\n", " q=R(P); \n", " d=q.degree(); \n", " M=matrix(Zmod(p),d,[coef((x^(p*i)-x^i)%q,d) for i in range(d)]).transpose();\n", " K=M.right_kernel();\n", " if K.dimension()==1:\n", " return [P];\n", " else:\n", " l=[];\n", " z=R(list(K.basis()[1]));\n", " for i in Zmod(p):\n", " g=gcd(q,z-i);\n", " if g<>1:\n", " \n", " l=l+fact_sfc(p,g);\n", " return l;\n", " " ] }, { "cell_type": "code", "execution_count": 201, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[x^2 + 3, x^3 + 3*x + 3, x + 4, x + 1]" ] }, "execution_count": 201, "metadata": {}, "output_type": "execute_result" } ], "source": [ "fact_sfc(5,Q2*x^2 +x+1)" ] }, { "cell_type": "code", "execution_count": 202, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(x + 1) * (x + 4) * (x^2 + 3) * (x^3 + 3*x + 3)" ] }, "execution_count": 202, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factor(Q2* x^2+x+1)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Sous-corps" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice : définir en Sage un corps $K$ à $5^4$ éléments.**\n", "\n", "**A partir de quel polynôme irréductible est-il construit?**\n", "\n", "**Déterminer un sous-corps $K_1$ à $5^2$ éléments de $K$:**\n", "- **faire la liste des éléments de $K_1$**,\n", "- **trouver un générateur $z$ de $K_1$ comme algèbre**\n", "- **déterminer le polynôme minimal d'un générateur $y$ de $K$ sur $K_1$.**\n", "*(Pour cela, on pourra déterminer a priori le degré $d$ de ce polynôme, et utiliser une $\\mathbf F_p$-base de $K$ de la forme $y^iz^j$ pour trouver une relation linéaire adéquate.)*" ] }, { "cell_type": "code", "execution_count": 242, "metadata": {}, "outputs": [], "source": [ "K.=GF(5^4);" ] }, { "cell_type": "code", "execution_count": 243, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^4 + 4*x^2 + 4*x + 2" ] }, "execution_count": 243, "metadata": {}, "output_type": "execute_result" } ], "source": [ "K.modulus()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "L'unique sous-corps à $5^2$ éléments de K est constitué des racines de $X^{5^2}-X$." ] }, { "cell_type": "code", "execution_count": 247, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0,\n", " y^3 + y^2 + y + 3,\n", " y^3 + y^2 + y + 1,\n", " 4*y^3 + 4*y^2 + 4*y,\n", " 2*y^3 + 2*y^2 + 2*y + 3,\n", " 4*y^3 + 4*y^2 + 4*y + 3,\n", " 2,\n", " 2*y^3 + 2*y^2 + 2*y + 1,\n", " 2*y^3 + 2*y^2 + 2*y + 2,\n", " 3*y^3 + 3*y^2 + 3*y,\n", " 4*y^3 + 4*y^2 + 4*y + 1,\n", " 3*y^3 + 3*y^2 + 3*y + 1,\n", " 4,\n", " 4*y^3 + 4*y^2 + 4*y + 2,\n", " 4*y^3 + 4*y^2 + 4*y + 4,\n", " y^3 + y^2 + y,\n", " 3*y^3 + 3*y^2 + 3*y + 2,\n", " y^3 + y^2 + y + 2,\n", " 3,\n", " 3*y^3 + 3*y^2 + 3*y + 4,\n", " 3*y^3 + 3*y^2 + 3*y + 3,\n", " 2*y^3 + 2*y^2 + 2*y,\n", " y^3 + y^2 + y + 4,\n", " 2*y^3 + 2*y^2 + 2*y + 4,\n", " 1]" ] }, "execution_count": 247, "metadata": {}, "output_type": "execute_result" } ], "source": [ "l=[u for u in K if u^(5^2)==u]; l" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "K1 contient comme attendu les constantes. Comme il est de dimension 2 sur Z/5Z, tout élément non constant l'engendre comme algèbre. Vérifions le:" ] }, { "cell_type": "code", "execution_count": 263, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "y^3 + y^2 + y + 3" ] }, "execution_count": 263, "metadata": {}, "output_type": "execute_result" } ], "source": [ "z=l[1]; z" ] }, { "cell_type": "code", "execution_count": 264, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0,\n", " 1,\n", " 2,\n", " 3,\n", " 4,\n", " y^3 + y^2 + y + 3,\n", " y^3 + y^2 + y + 4,\n", " y^3 + y^2 + y,\n", " y^3 + y^2 + y + 1,\n", " y^3 + y^2 + y + 2,\n", " 2*y^3 + 2*y^2 + 2*y + 1,\n", " 2*y^3 + 2*y^2 + 2*y + 2,\n", " 2*y^3 + 2*y^2 + 2*y + 3,\n", " 2*y^3 + 2*y^2 + 2*y + 4,\n", " 2*y^3 + 2*y^2 + 2*y,\n", " 3*y^3 + 3*y^2 + 3*y + 4,\n", " 3*y^3 + 3*y^2 + 3*y,\n", " 3*y^3 + 3*y^2 + 3*y + 1,\n", " 3*y^3 + 3*y^2 + 3*y + 2,\n", " 3*y^3 + 3*y^2 + 3*y + 3,\n", " 4*y^3 + 4*y^2 + 4*y + 2,\n", " 4*y^3 + 4*y^2 + 4*y + 3,\n", " 4*y^3 + 4*y^2 + 4*y + 4,\n", " 4*y^3 + 4*y^2 + 4*y,\n", " 4*y^3 + 4*y^2 + 4*y + 1]" ] }, "execution_count": 264, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[i*z+j for i in Zmod(5) for j in Zmod(5)]" ] }, { "cell_type": "code", "execution_count": 235, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(None,\n", " [0,\n", " 1,\n", " 2,\n", " 3,\n", " 4,\n", " y^3 + y^2 + y,\n", " y^3 + y^2 + y + 1,\n", " y^3 + y^2 + y + 2,\n", " y^3 + y^2 + y + 3,\n", " y^3 + y^2 + y + 4,\n", " 2*y^3 + 2*y^2 + 2*y,\n", " 2*y^3 + 2*y^2 + 2*y + 1,\n", " 2*y^3 + 2*y^2 + 2*y + 2,\n", " 2*y^3 + 2*y^2 + 2*y + 3,\n", " 2*y^3 + 2*y^2 + 2*y + 4,\n", " 3*y^3 + 3*y^2 + 3*y,\n", " 3*y^3 + 3*y^2 + 3*y + 1,\n", " 3*y^3 + 3*y^2 + 3*y + 2,\n", " 3*y^3 + 3*y^2 + 3*y + 3,\n", " 3*y^3 + 3*y^2 + 3*y + 4,\n", " 4*y^3 + 4*y^2 + 4*y,\n", " 4*y^3 + 4*y^2 + 4*y + 1,\n", " 4*y^3 + 4*y^2 + 4*y + 2,\n", " 4*y^3 + 4*y^2 + 4*y + 3,\n", " 4*y^3 + 4*y^2 + 4*y + 4])" ] }, "execution_count": 235, "metadata": {}, "output_type": "execute_result" } ], "source": [ "l.sort(), l" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Compte tenu des dimensions, y a un polynôme minimal de degré $2$ sur K1. On cherche donc une CL non triviale nulle entre 1, z, y, yz et z^2." ] }, { "cell_type": "code", "execution_count": 265, "metadata": {}, "outputs": [], "source": [ "M=Matrix(Zmod(5), 5,[[1,0,0,0],pol(z),pol(y), pol(y*z), pol(y^2)]).transpose()" ] }, { "cell_type": "code", "execution_count": 266, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[\n", "(0, 1, 3, 4, 1)\n", "]" ] }, "execution_count": 266, "metadata": {}, "output_type": "execute_result" } ], "source": [ "k=M.right_kernel().basis(); k" ] }, { "cell_type": "code", "execution_count": 267, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 267, "metadata": {}, "output_type": "execute_result" } ], "source": [ "y^2+(4*z+3)*y+z" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le polynôme $X^2+(4z+3)X+z$ est donc le polynôme minimal de y sur $K_1$." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 8.9", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.15" } }, "nbformat": 4, "nbformat_minor": 1 }