{
 "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<ipython-input-3-32f7bd0dc849>\u001b[0m in \u001b[0;36m<module>\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.<X> = 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": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3*X + 5"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(3*X^5+5)%(5*X^2+5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Normalement, vous devriez pouvoir les recoder en quelques lignes et minutes..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pgcd(P,Q):\n",
    "    return 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": [],
   "source": [
    "P=2*X^2+3*X+1"
   ]
  },
  {
   "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",
    "    return 0"
   ]
  },
  {
   "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": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Finite Field in z3 of size 2^3"
      ]
     },
     "execution_count": 13,
     "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": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^3 + x + 1"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R2.modulus()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "z3"
      ]
     },
     "execution_count": 15,
     "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": "code",
   "execution_count": 16,
   "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": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Finite Field in y of size 13^4"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R3.<y>=GF(13^4,modulus=x^4 + 3*x^2 + 12*x + 1); R3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^4 + 3*x^2 + 12*x + 1"
      ]
     },
     "execution_count": 18,
     "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": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "28561"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R3.cardinality()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8*y^3 + 12*y^2 + 9*y + 9"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z=R3.multiplicative_generator(); z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^4 + 12*x^3 + x + 11"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z.minimal_polynomial()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "595"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y.multiplicative_order()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[9, 9, 12, 8]"
      ]
     },
     "execution_count": 23,
     "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": [
    "**Codez vos propres fonctions** `ordre` **et** `generateur` **pour R3.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ordre(a):\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generateur():\n",
    "    return 0"
   ]
  },
  {
   "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": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0 1 2]\n",
       "[3 4 5]\n",
       "[6 7 8]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M=Matrix(A,3,3,[i for i in range(9)]); M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M.rank()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "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": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V=M.right_kernel(); V"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 11, 1)"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "V.gens()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Univariate Polynomial Ring in X over Ring of integers modulo 7"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "R1.<X>=PolynomialRing(Zmod(7)); R1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "P=X^6 + X^4 + 5*X^3 + 4*X^2 + 6*X + 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "X^6 + X^4 + 5*X^3 + 4*X^2 + 6*X + 3"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(P)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Qu'en déduit-on sur $P$?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "K1.<X>=PolynomialRing(GF(7^6));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "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": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(K1(P))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Était-ce prévisible?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "K2.<X>=PolynomialRing(GF(7^3));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "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": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(K2(P))"
   ]
  },
  {
   "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": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sous-corps"
   ]
  },
  {
   "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 $x$ 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 $x^iz^j$ pour trouver une relation linéaire adéquate.)*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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
}