{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8196abf1",
   "metadata": {},
   "source": [
    "# TP0: Introduction à SageMath\n",
    "\n",
    "\n",
    "## 0: Accéder à la documentation de SageMath\n",
    "\n",
    "Pour obtenir de l'aide sur une méthode dans SageMath, vous pouvez utiliser la fonction ? :\n",
    "\n",
    "1. Par exemple, la commande « divisors? » affichera la documentation de la fonction « divisors ».\n",
    "\n",
    "2. La fonction help() peut également être utilisée (pour obtenir un affichage différent) avec comme argument la fonction à documenter : help(divisors).\n",
    "\n",
    "Vous pouvez également consulter la documentation et les exemples directement sur : https://doc.sagemath.org/html/en/ (recommandé).\n",
    "\n",
    "Quelques exercices proviennent de ressources pédagogiques extérieures : [Guilhem Castagnos](https://www.math.u-bordeaux.fr/~gcastagn/) et [Annamaria Iezzi](https://aiezzi.it/)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "fc4ba2ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "divisors?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "8b7b1c87",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on function divisors in module sage.arith.misc:\n",
      "\n",
      "divisors(n)\n",
      "    Return the list of all divisors (up to units) of this element\n",
      "    of a unique factorization domain.\n",
      "    \n",
      "    For an integer, the list of all positive integer divisors\n",
      "    of this integer, sorted in increasing order, is returned.\n",
      "    \n",
      "    INPUT:\n",
      "    \n",
      "    -  ``n`` - the element\n",
      "    \n",
      "    EXAMPLES:\n",
      "    \n",
      "    Divisors of integers::\n",
      "    \n",
      "        sage: divisors(-3)\n",
      "        [1, 3]\n",
      "        sage: divisors(6)\n",
      "        [1, 2, 3, 6]\n",
      "        sage: divisors(28)\n",
      "        [1, 2, 4, 7, 14, 28]\n",
      "        sage: divisors(2^5)\n",
      "        [1, 2, 4, 8, 16, 32]\n",
      "        sage: divisors(100)\n",
      "        [1, 2, 4, 5, 10, 20, 25, 50, 100]\n",
      "        sage: divisors(1)\n",
      "        [1]\n",
      "        sage: divisors(0)\n",
      "        Traceback (most recent call last):\n",
      "        ...\n",
      "        ValueError: n must be nonzero\n",
      "        sage: divisors(2^3 * 3^2 * 17)\n",
      "        [1, 2, 3, 4, 6, 8, 9, 12, 17, 18, 24, 34, 36, 51, 68, 72,\n",
      "        102, 136, 153, 204, 306, 408, 612, 1224]\n",
      "    \n",
      "    This function works whenever one has unique factorization::\n",
      "    \n",
      "        sage: K.<a> = QuadraticField(7)\n",
      "        sage: divisors(K.ideal(7))\n",
      "        [Fractional ideal (1), Fractional ideal (-a), Fractional ideal (7)]\n",
      "        sage: divisors(K.ideal(3))\n",
      "        [Fractional ideal (1), Fractional ideal (3),\n",
      "        Fractional ideal (-a + 2), Fractional ideal (-a - 2)]\n",
      "        sage: divisors(K.ideal(35))\n",
      "        [Fractional ideal (1), Fractional ideal (5), Fractional ideal (-a),\n",
      "        Fractional ideal (7), Fractional ideal (-5*a), Fractional ideal (35)]\n",
      "    \n",
      "    TESTS::\n",
      "    \n",
      "        sage: divisors(int(300))\n",
      "        [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 25, 30, 50, 60, 75, 100, 150, 300]\n",
      "        sage: import numpy\n",
      "        sage: divisors(numpy.int8(100))\n",
      "        [1, 2, 4, 5, 10, 20, 25, 50, 100]\n",
      "        sage: import gmpy2\n",
      "        sage: divisors(gmpy2.mpz(100))\n",
      "        [1, 2, 4, 5, 10, 20, 25, 50, 100]\n",
      "        sage: divisors([])\n",
      "        Traceback (most recent call last):\n",
      "        ...\n",
      "        TypeError: unable to factor []\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(divisors)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b34ed1d8",
   "metadata": {},
   "source": [
    "## 1: Opérations de base, tests et affectations\n",
    "Expérimenter les commandes de bases et comprendre leur utilité"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "3e00b5e3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "5f4040ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "x=8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "727ab759",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(x)\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "b5b74111",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "texte 8 encore du texte\n"
     ]
    }
   ],
   "source": [
    "print(\"texte\",x,\"encore du texte\") "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "9a222a7f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "6531fbb2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x == 8 and x != 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "b7787ac7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2**3 \n",
    "2^3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "b8e02028",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Integer Ring"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parent(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "46dccb26",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<class 'sage.rings.integer.Integer'>"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b0b393b",
   "metadata": {},
   "source": [
    "Les différences entre `parent`et `type` sont importantes dans la gestion des structures par SageMath (voir https://doc.sagemath.org/html/en/tutorial/tour_coercion.html) et leur égalité ne signifie pas nécessairement qu'il s'agit d'éléments identiques. Cette différence se traduit notamment par leur définition et leur affectation dans le cadre de structures algébriques, comme nous le verrons dans la section 3. Anneaux, corps finis et polynômes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "3e3def26",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10/3"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "10/3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "ae1e57af",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "10//3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "d97a2b04",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "10%3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4af2b505",
   "metadata": {},
   "source": [
    "Dans quel structures appartiennent chacuns des résultats des 3 résultats précédents ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "37040729",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pour 10/3 =  10/3 #####\n"
     ]
    }
   ],
   "source": [
    "print(\"Pour 10/3 = \",10/3, \"#####\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "0f769b3d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pour 10//3: 3 #####\n"
     ]
    }
   ],
   "source": [
    "print(\"Pour 10//3:\", 10//3, \"#####\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "a6f62cd9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pour 10%3: 3 #####\n"
     ]
    }
   ],
   "source": [
    "print(\"Pour 10%3:\", 10//3, \"#####\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "653e57f9",
   "metadata": {},
   "source": [
    "# 2 Listes\n",
    "Expérimenter les commandes de bases et comprendre leur utilité."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "31c99da1",
   "metadata": {},
   "outputs": [],
   "source": [
    "S=[1,2,3,4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "dd6bb2ca",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "8de27611",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "a452c7d3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S[0:3]\n",
    "S[1:]\n",
    "S[:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "c8a83ad4",
   "metadata": {},
   "outputs": [],
   "source": [
    "T1 = copy(S)\n",
    "T2 = S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "b11989d5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 3, 4]"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S[0] = 2\n",
    "S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "2583298c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "T1 == T2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "a8ee39ac",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "T3 = range(1,5)\n",
    "S == T3 "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e691a830",
   "metadata": {},
   "source": [
    "A l'aide de la documentation de `range`, construire les \"ranges\":\n",
    "1. $[1,2,..,9,10]$\n",
    "2. $[2,4,6,8,10,..,120]$\n",
    "3. $[33,29,..,5,1]$\n",
    "\n",
    "A l'aide de la documentation de `list`, construire les mêmes \"listes\" ci-dessus:\n",
    "\n",
    "Avec une boucle `for`imbriquée, construire la liste contenant les 10 premiers carrés non nuls."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7ca13bea",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "0d618ddb",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Quelques méthodes:\n",
    "S.append(2) \n",
    "S.sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "5f54f850",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 2, 3, 4, [1, 2], 1, 2]"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S.append([1,2])\n",
    "S.extend([1,2])\n",
    "S"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "490dfbf2",
   "metadata": {},
   "source": [
    "Nous n'utiliserons ici que les listes mais il existe d'autres classes de collections comme par exemple les ensembles `set` ou encore les dictionnaires `dict`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c47c9b71",
   "metadata": {},
   "source": [
    "## 3.  Anneau, Corps Finis et Polynômes\n",
    "\n",
    "### 3.1. Anneaux"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0f75e1c",
   "metadata": {},
   "source": [
    "Distinguer les 3 \"ensembles\" de nombres suivants, à quoi correspondent-ils ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "e193f2a7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Real Field with 53 bits of precision"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ZZ\n",
    "QQ\n",
    "RR"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43937e5a",
   "metadata": {},
   "source": [
    "SageMath permet surtout de manipuler des éléments appartenant à des ensembles et structures algébriques différentes que simplement les entiers, rationnels et réels. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "f88eab36",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Z11 = IntegerModRing(11)\n",
    "Z11.list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "5fd616a4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 5, 7, 9, 11, 13, 15]"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Z16 = IntegerModRing(16)\n",
    "Z16.list_of_elements_of_multiplicative_group()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "a63b3e72",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "euler_phi(16)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "5cd0f5c0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13 = 2 mod 11, et d'ordre  10 dans Z/11Z\n",
      "13 = 13 mod 16, et d'ordre  4 dans Z/16Z\n"
     ]
    }
   ],
   "source": [
    "z1 = Z11(13)\n",
    "z2 = Z16(13) \n",
    "\n",
    "print(\"13 =\",z1, \"mod 11, et d'ordre \",z1.multiplicative_order(), \"dans Z/11Z\")\n",
    "print(\"13 =\",z2, \"mod 16, et d'ordre \",z2.multiplicative_order(), \"dans Z/16Z\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f46aec2",
   "metadata": {},
   "source": [
    "Voici un exemple de différence entre `parent` et `type`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "27917046",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parent(z1) == parent(z2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "db430f45",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(z1) == type(z2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e0213ce",
   "metadata": {},
   "source": [
    "### 3.2. Corps Finis\n",
    "\n",
    "Tout corps fini $\\mathbb{F}_p = \\mathbb{Z}/p\\mathbb{Z}$ pour tout nombre premier $p$. On peut également instancier tout corps fini directement graĉe à $\\texttt{GF}(n)$, pour tout entier $n = p^k$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "f4d17372",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F11 = GF(11)\n",
    "F11.list()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d9fc062",
   "metadata": {},
   "source": [
    "Malgré que les objets soient théoriquement les mêmes, les classes définissant les 2 objets sont différentes et induisent des fonctions et méthodes différentes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "b798d0d7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<class 'sage.rings.finite_rings.integer_mod_ring.IntegerModRing_generic_with_category'>"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F11 == Z11\n",
    "type(F11)\n",
    "type(Z11)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93924deb",
   "metadata": {},
   "source": [
    "Dans le cas de $\\mathbb{F}_{p^k}$, on voit la liste des éléments comme des polynômes en $x$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "id": "0356263f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, x, x + 1, 1]"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F4.<x> = GF(4)\n",
    "F4.list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "97b56a5f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^2 + x + 1"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F4.modulus()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8cfa918",
   "metadata": {},
   "source": [
    "Nous introduirons la structure de polynôme dans la section qui suit. Mais il est possible de choisir le polynôme générateur, unitaire et irréductible dans $\\texttt{GF}(p)[X]$, de degré $k$, utilisé afin d'instancier $\\texttt{GF}(p^k)$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "id": "03766ba3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PR.<y> = PolynomialRing(GF(5))\n",
    "f = y^2 + 2\n",
    "assert f.is_irreducible()\n",
    "F25.<x> = GF(25,modulus=f)\n",
    "F25.modulus() != GF(25).modulus()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "021d6348",
   "metadata": {},
   "source": [
    "### 3.3. Polynômes \n",
    "Expérimenter les commandes de bases et comprendre leur utilité."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "id": "1ddec411",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Il existe plusieurs instantiations possibles d'anneaux de polynômes.\n",
    "K.<x> = PolynomialRing(QQ)\n",
    "K2.<x> = QQ[]\n",
    "K3 = QQ['x']\n",
    "K4 = PolynomialRing(QQ,'x')\n",
    "K == K2 == K3 == K4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "aaedf696",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p1 = x^3 + 2*x - 2\n",
    "p2 = K([-2,2,0,1]) \n",
    "p1 == p2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "id": "c24a2348",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0.770916997059248, 1),\n",
       " (-0.385458498529624 - 1.56388451052696*I, 1),\n",
       " (-0.385458498529624 + 1.56388451052696*I, 1)]"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Quelques méthodes: \n",
    "p1.degree()\n",
    "p1.is_irreducible()\n",
    "factor(p1)\n",
    "p1.roots()\n",
    "p1.roots(ring=CC)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2306ea1b",
   "metadata": {},
   "source": [
    "Quelle est la différence entre les deux prochaines méthodes ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "id": "770bed35",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p1(2)\n",
    "p1[2]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e14892d8",
   "metadata": {},
   "source": [
    "### 3.4. Idéaux et quotients"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "e37f6f9e",
   "metadata": {},
   "outputs": [],
   "source": [
    "ZZ.ideal(2)\n",
    "Z6 = IntegerModRing(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "id": "e92c2133",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "I23 = Z6.ideal(ZZ(2),ZZ(3))\n",
    "I23 != ZZ.ideal(2,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0ff6144",
   "metadata": {},
   "source": [
    "Le cas des anneaux de polynômes :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "id": "55041156",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Univariate Quotient Polynomial Ring in x over Rational Field with modulus x^3 + 2*x - 2"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "K5.<x> = PolynomialQuotientRing(K,p1)\n",
    "K5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "1a1802c1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "I = K.ideal(p1)\n",
    "K.quotient(I) == K5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "da53d6aa",
   "metadata": {},
   "source": [
    "## 4. Vecteurs et Matrices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "id": "51b13c4a",
   "metadata": {},
   "outputs": [],
   "source": [
    "I3 = identity_matrix(3,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "id": "07878871",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[ 1  2  1]\n",
       "[ 2  1  2]\n",
       "[ 3 -3  3]"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v = vector([6,0,6])\n",
    "z = zero_vector(3)\n",
    "Z = zero_matrix(4,3)\n",
    "M = Matrix([[1,2,1],[2,1,2],[3,-3,3]])\n",
    "M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "id": "adff2c22",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Quelques méthodes: \n",
    "M.det()\n",
    "M.T\n",
    "y1 = kernel(M)\n",
    "y2 = kernel(M.T)\n",
    "M.nrows()\n",
    "M.ncols()\n",
    "M[0,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "fa287503",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "M.solve_left(v) * M == v\n",
    "M * M.solve_right(z) == z"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71a7a562",
   "metadata": {},
   "source": [
    "On peut également définir des vecteurs/matrices pour tout type de structures algébriques. Soit en instanciant la structure tout entière, soit en la spécifiant lors de l'affectation. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "id": "60346283",
   "metadata": {},
   "outputs": [],
   "source": [
    "F4.<x> = GF(4)\n",
    "MS = MatrixSpace(F4,3)\n",
    "M = MS([1,1+x,x] for i in range(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "id": "d8187b5a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[    x     x x + 1]\n",
       "[x + 1 x + 1 x + 1]\n",
       "[    1     1     1]"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MS.random_element()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "id": "43920a1e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "assert MS(0) == zero_matrix(F4,3,3)\n",
    "assert MS(1) == identity_matrix(F4,3,3)\n",
    "True"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48620cb2",
   "metadata": {},
   "source": [
    "## 5. Exercices d'entrainement\n",
    "\n",
    "**Exercice 1:**\n",
    "   1. Quelle fonction renvoie le pgcd, le reste et le quotient de la division euclidienne. Tester la pour $4092$ et $1017$.\n",
    "   2. Que fait la fonction $\\texttt{xgcd}$ ? Utilisez-la sur des entiers, puis des polynômes. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "03c0886c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a9459222",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "8a95b9cb",
   "metadata": {},
   "source": [
    "**Exercice 2.** On rappelle que les inversibles de $\\mathbb{Z}/n\\mathbb{Z}$ sont les entiers premiers avec $n$.\n",
    "1. Écrire une fonction `inverse(n)` qui calcule $\\left(\\mathbb Z/n\\mathbb Z\\right)^{\\times}$ pour un entier positif non nul $n$ en entrée.\n",
    "2. En observant simplement la taille de $\\left(\\mathbb Z/391\\mathbb Z\\right)^{\\times}$, 391 est-il premier ? Pourquoi ?\n",
    "3. Rechercher l'ordre multiplicatif de $12$ modulo $391$, d'abord par une boucle, puis par l'anneau $\\left(\\mathbb Z/391\\mathbb Z\\right)^{\\times}$.\n",
    "4. Construire deux listes L1 et L2, telle que L2[i] est l'inverse de L1[i] dans $\\left(\\mathbb Z/391\\mathbb Z\\right)^{\\times}$.\n",
    "5. Combien y'a-t'il d'éléments de $\\mathbb Z/391\\mathbb Z$ qui sont leurs propres inverses ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "26635940",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0035b30b",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "97f66616",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "52b485ce",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "303fd6e0",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "3dd3e21e",
   "metadata": {},
   "source": [
    "**Exercice 3.**\n",
    "\n",
    "1. Calculer tous les idéaux $I$ de $\\mathbb Z/391\\mathbb Z$ engendrés par un élément, et l'anneau quotient $R = (\\mathbb Z/391\\mathbb Z)/I$. \n",
    "2. Expliquer mathématiquement la structure de $R$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c105648e",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b73618bd",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "6d7fa5d7",
   "metadata": {},
   "source": [
    "**Exercice 4.**\n",
    "\n",
    "1. Créer le corps fini à 8 éléments, donner en une base puis lister ces éléments en fonction de la base.\n",
    "2. Vérifier l'identité $(x+y)^2 = x^2 + y^2$ dans $\\mathbb{F}_8$ et puis prouvez-la.\n",
    "3. Quel est le polynôme minimal utilisé pour sa construction ? Prouvez qu'il est irréductible (avec la fonction Sage puis par le calcul)?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9325c744",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "313ae4a0",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ecac89ce",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "64cb4c32",
   "metadata": {},
   "source": [
    "## 6. Utiliser SageMath pour manipuler des réseaux euclidiens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "id": "df4507ee",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Free module of degree 2 and rank 2 over Integer Ring\n",
       "User basis matrix:\n",
       "[3 0]\n",
       "[2 1]"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sage.modules.free_module_integer import IntegerLattice\n",
    "\n",
    "#exemple\n",
    "IntegerLattice([[3,0], [2,1]],False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "569acc5f",
   "metadata": {},
   "source": [
    "Considérer l'option **False** en second paramètre afin d'avoir l'entrée attendue. Chaque élément sera une combinaison linéaire des lignes indiquées.\n",
    "\n",
    "**Exercice 1**\n",
    "1. Ecrire la fonction $\\texttt{gauss(u,v)}$ ressortant une base réduite par Lagrange-Gauss en dimension 2. Tester pour une matrice aléatoire de dimension 2 avec `random_matrix`.\n",
    "2. Soit $p$ un nombre premier tel que $p ≡ 1 \\mod 4$ On rappelle que dans ce cas $-1$ est un carré\n",
    "modulo $p$, on note alors $s$ un tel entier i.e. $s^2 ≡ −1 \\mod p$. On considère le réseau $\\mathcal{L}$ de $\\mathbb{R}^2$ de base\n",
    "$\\begin{bmatrix}1 & 0 \\\\ s & p\\end{bmatrix}$ i.e. $\\ell \\in \\mathcal{L} \\Leftrightarrow \\exists x_1,x_2 \\text{ tel que } \\ell = x_1 \\begin{bmatrix}1 \\\\ s\\end{bmatrix} + x_2\\begin{bmatrix}0 \\\\ p\\end{bmatrix}$\n",
    "\n",
    "On sait qu’il existe un vecteur $u \\in \\mathcal{L}$ tel que $\\|u\\| \\leq \\frac{3}{4}\\sqrt{\\textsf{det}(\\mathcal{L})}$. \n",
    "En déduire et implémenter un algorithme polynomial $\\texttt{decomposition_somme_carree(u,v)}$ prenant en entrée un nombre $p$ et retournant deux entiers $a$ et $b$ tels\n",
    "que $a^2 + b^2 = p$.\n",
    "\n",
    "3. Décomposer $1237940039285380274899124357$ en somme de deux carrés."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "64c66a0b",
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "incomplete input (2461587392.py, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"/tmp/ipykernel_723980/2461587392.py\"\u001b[0;36m, line \u001b[0;32m1\u001b[0m\n\u001b[0;31m    def gauss(M):\u001b[0m\n\u001b[0m                 ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m incomplete input\n"
     ]
    }
   ],
   "source": [
    "def gauss(M):\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "id": "985fc3b7",
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "incomplete input (635584775.py, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"/tmp/ipykernel_723980/635584775.py\"\u001b[0;36m, line \u001b[0;32m1\u001b[0m\n\u001b[0;31m    def decomposition_somme_carree(p):\u001b[0m\n\u001b[0m                                      ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m incomplete input\n"
     ]
    }
   ],
   "source": [
    "def decomposition_somme_carree(p):\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "944757af",
   "metadata": {},
   "source": [
    "**Exercice 2**\n",
    "1. Générer des réseaux aléatoires à l'aide de la fonction `random_matrix`. À partir de la dimension 10, puis de dimensions de plus en plus grandes.\n",
    "2. Essayer de résoudre le problème du vecteur le plus court dans vos réseaux en utilisant la fonction `.shortest_vector(algorithm=\"pari\")` sur un objet de type `IntegerLattice`.  À partir de quelle dimension le problème devient-il trop long à résoudre ?\n",
    "3. Générer de nouveaux réseaux de mêmes dimensions, mais cette fois avec la fonction `gen_lattice` issue de la bibliothèque `sage.crypto`.\n",
    "4. Essayer de résoudre le problème du plus court vecteur dans vos réseaux. À partir de quelle dimension le problème devient-il trop long à résoudre ? Expliquer les différences avec la résolution effectuée lors de la question 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "998f6a63",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e5ebb3d3",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.5",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}