{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "134f0962",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "# Examen MAO Calcul Formel 8 juin 2026"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "09d7d623",
   "metadata": {},
   "source": [
    "## Exercice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a9b8c61f",
   "metadata": {},
   "outputs": [],
   "source": [
    "QXY.<X,Y>=PolynomialRing(QQ)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "002b9cee",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2) * (X - 1) * X^5\n"
     ]
    }
   ],
   "source": [
    "P=X^2+Y^2-1\n",
    "Q=X^3+X^2*Y+Y^2-1\n",
    "R=P.resultant(Q,Y)\n",
    "print(R.factor())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a62117e9",
   "metadata": {},
   "source": [
    "## Problème"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3fec85b2",
   "metadata": {},
   "source": [
    "Question 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "42de980b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def T_NU(N,U):\n",
    "    j=1\n",
    "    UU=N*U\n",
    "    while UU!=U:\n",
    "        j+=1\n",
    "        UU=N*UU\n",
    "    return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "a48b8eee",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15 480\n"
     ]
    }
   ],
   "source": [
    "p=31\n",
    "d=3\n",
    "F31=GF(31)\n",
    "N=matrix(F31,[[2,5,7],[3,1,17],[1,4,12]])\n",
    "U1=vector(F31,[1,19,30])\n",
    "U2=vector(F31,[2,1,17])\n",
    "print(T_NU(N,U1),T_NU(N,U2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "281299c9",
   "metadata": {},
   "source": [
    "Question 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "c351160b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_generateur(K,g,L):\n",
    "    q=K.cardinality()\n",
    "    for p in L:\n",
    "        if g^((q-1)//p)==K(1):\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a74e20e6",
   "metadata": {},
   "source": [
    "Question 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d96fb2df",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False False True\n"
     ]
    }
   ],
   "source": [
    "q=17^2\n",
    "G289.<a>=GF(q,modulus=[1,1,1])\n",
    "L=factor(q-1)[0][:]\n",
    "g1=a+5\n",
    "g2=3*a\n",
    "g3=15*a+11\n",
    "print(est_generateur(G289,g1,L),est_generateur(G289,g2,L),est_generateur(G289,g3,L))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fdb4615f",
   "metadata": {},
   "source": [
    "Question 11"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "6c72bda7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def calcul_generateur(K,L):\n",
    "    g=K.random_element()\n",
    "    while g==K(0) or not(est_generateur(K,g,L)):\n",
    "        g=K.random_element()\n",
    "    return g"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66b42473",
   "metadata": {},
   "source": [
    "Question 12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "26b0eb81",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2*a + 1"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q=3^2\n",
    "G9.<a>=GF(q,modulus=[1,0,1])\n",
    "L=factor(q-1)[0][:]\n",
    "calcul_generateur(G9,L)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93f2457c",
   "metadata": {},
   "source": [
    "Question 23"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "179d1047",
   "metadata": {},
   "outputs": [],
   "source": [
    "def N_pasdordremaximal(Gp,q):\n",
    "    while True:\n",
    "        q0=Gp.random_element()\n",
    "        q1=Gp.random_element()\n",
    "        N=matrix(Gp,[[0,-q0],[1,-q1]])\n",
    "        K.<Y>=PolynomialRing(Gp)\n",
    "        Q=Y^2+q1*Y+q0\n",
    "        if Q.is_irreducible() and N.multiplicative_order()!=q-1:\n",
    "            return list(Q)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "id": "39fab78b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 2, 1]"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p=11\n",
    "q=p^2\n",
    "Gp=GF(p)\n",
    "N_pasdordremaximal(Gp,q)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c0ade1a",
   "metadata": {},
   "source": [
    "Question 25"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "1b3fa49a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def liste_A(Gp,GpY,q):\n",
    "    L=[]\n",
    "    for q0 in Gp:\n",
    "        for q1 in Gp:\n",
    "            for q2 in Gp:\n",
    "                N=matrix(Gp,[[0,0,-q0],[1,0,-q1],[0,1,-q2]])\n",
    "                Q=GpY([q0,q1,q2,1])\n",
    "                if Q.is_irreducible() and N.multiplicative_order()==q-1:\n",
    "                    L.append(Q)\n",
    "    return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "id": "d835a4cb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "36 True Y^108 + Y^105 + 6*Y^99 + 6*Y^96 + Y^90 + Y^87 + 6*Y^81 + 6*Y^78 + Y^72 + Y^69 + 6*Y^63 + 6*Y^60 + Y^54 + 6*Y^48 + 6*Y^45 + Y^39 + Y^36 + 6*Y^30 + 6*Y^27 + Y^21 + Y^18 + 6*Y^12 + 6*Y^9 + Y^3 + 1\n"
     ]
    }
   ],
   "source": [
    "p=7\n",
    "q=p^3\n",
    "Gp=GF(p)\n",
    "GpY.<Y>=PolynomialRing(Gp)\n",
    "L_A=liste_A(Gp,GpY,q)\n",
    "P_L_A=prod(P for P in L_A)\n",
    "print(len(L_A),P_L_A==GpY(list(cyclotomic_polynomial(p^3-1))),P_L_A)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.3",
   "language": "sage",
   "name": "SageMath-10.3"
  },
  "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.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}