{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# M1 Cryptographie - Arithmétique modulaire\n",
    "\n",
    "## Arithmétique élémentaire\n",
    "\n",
    "L'arithmétique est l'étude des nombres entiers\n",
    "$${\\mathbb N}=\\{0,1,2,3,4,\\ldots\\}$$\n",
    "$${\\mathbb Z}=\\{\\ldots,-3,-2,-1,0,1,2,3,\\ldots\\}$$\n",
    "\n",
    "### Division euclidienne\n",
    "\n",
    "La propriété fondamentale est la <i>division euclidienne</i> : Étant donnés deux entiers $a\\in{\\mathbb Z}$ et $b>0$,\n",
    "il existe un unique couple d'entiers $(q,r)$ (quotient et reste) tel que\n",
    "$$a =bq+r\\quad {\\rm avec}\\ 0\\le r<b.$$\n",
    "\n",
    "Lorsque le reste $r$ est nul, on dit que $b$ divise $a$ ou que $a$ est multiple de $b$, et on écrit $b|a$.\n",
    "\n",
    "Un entier $>1$ qui n'a pas de diviseurs non-triviaux, c'est à dire autres que 1 et lui-même est dit <i>premier</i>.\n",
    "Par exemple, $2,3,5,7,11,13,17,19,23$ sont premiers.\n",
    "\n",
    "Le p.g.c.d. de deux entiers $a$ et $b$ est le plus grand entier positif qui divise à la fois $a$ et $b$.\n",
    "On le note $d=a\\wedge b$. Par exemple $(-12)\\wedge 18=6$.\n",
    "\n",
    "Le plus petit entier positif divisible à la fois par $a$ et $b$ est appelé p.p.c.m. de $a$ et $b$. On le note\n",
    "$m=a\\vee b$. On a\n",
    "$$a\\vee b=\\frac{ab}{a\\wedge b}$$\n",
    "\n",
    "### Algorithme d'Euclide\n",
    "\n",
    "Pour calculer $a\\wedge b$, (avec $a\\ge b$) on écrit la division euclidienne $a=bq+r$. Alors $r=a-bq$ est divisible par tout entier divisant à la fois $a$ et $b$ donc par le p.g.c.d. de $a$ et $b$, et tout entier divisant $r$ et $b$ divise aussi $a$. Donc,\n",
    "$$a\\wedge b = b\\wedge r$$\n",
    "Comme $r<b$, $(b,r)<(a,b)$ et on itère le procédé jusqu'à arriver à un reste nul. Alors, $d\\wedge 0=d$ et on a fini.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Pour a=27, b=5, q=5, r=2\n",
      "Pour a=-27, b=5, q=-6, r=3\n"
     ]
    }
   ],
   "source": [
    "# division euclidienne : q=a//b, r=a%b\n",
    "print(\"Pour a=27, b=5, q=%d, r=%d\" % (27//5, 27%5))\n",
    "print(\"Pour a=-27, b=5, q=%d, r=%d\" % (-27//5, -27%5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# pgcd récursif\n",
    "def gcd(a,b):\n",
    "    if b==0: return a\n",
    "    return gcd(b,a%b)\n",
    "\n",
    "gcd(192,36)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gcd(36,192)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gcd(-36,192)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-12"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gcd(192,-36)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On voit qu'il faut faire attention aux signes. On évitera aussi la récursivité, car on va travailler sur des entiers très longs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcd(a,b):\n",
    "    a,b = abs(a), abs(b) # valeur absolue\n",
    "    r = a%b\n",
    "    while r:\n",
    "        a,b=b,r\n",
    "        r = a%b\n",
    "    return b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithme d'Euclide étendu et théorème de Bézout\n",
    "\n",
    "Dans la version itérative, on calcule donc une suite de quotients et de restes qu'il est commode de numéroter ainsi.\n",
    "On pose $a_{-1}=a$, $a_0=b$, $q_0=q$, $a_1=r$, et les itérations calculent\n",
    "$$a_{-1}=a_0q_0+a_1$$\n",
    "$$a_0=a_1q_1+a_2$$\n",
    "$$\\cdots=\\cdots$$\n",
    "$$a_{k-1}=a_kq_k+a_{k+1}$$\n",
    "et si le premier reste nul est $a_{k+1}$, alors le p.g.c.d. est $d=a_k$.\n",
    "\n",
    "\n",
    "Ceci implique qu'à chaque étape, on peut calculer des entiers $u_i,v_i$ tels que $a_i=u_ia+v_ib$\n",
    "En effet, au départ, $a_{-1}=1a+0b$, $a_0=0a+1b$,\n",
    "et par récurrence, comme $a_{i-2}=a_{i-1}q_{i-1}+a_i$, on peut écrire\n",
    "$$a_i = (u_{i-2}a+v_{i-2}b) - q_{i-1}(u_{i-1}a+v_{i-1}b) = (u_{i-2}-q_{i-1}u_{i-1})a+(v_{i-2}-q_{i-1}v_{i-1})b$$\n",
    "de sorte que\n",
    "$$u_i = u_{i-2}-q_{i-1}u_{i-1}$$\n",
    "$$v_i = v_{i-2}-q_{i-1}v_{i-1}$$\n",
    "Les deux suites $u_i$ et $v_i$ vérifient la même récurrence d'ordre 2, avec des conditions initiales\n",
    "différentes\n",
    "$${u_{-1}\\choose v_{-1}}={1\\choose 0}$$\n",
    "$${u_0\\choose v_0}={0\\choose 1}$$\n",
    "\n",
    "Si le p.g.c.d. est $a_k$, on aura donc $d=u_ka+v_kb$.\n",
    "\n",
    "Cette propriété, connue sous le nom de <i>théorème de Bézout</i>, sera très importante dans la suite :\n",
    "\n",
    "\n",
    "Si $a\\wedge b=d$, il existe deux entiers $u$ et $v$ tels que $d=ua+vb$, et l'agorithme ci-dessus, appelé algorithme d'Euclide étendu, permet de les calculer.\n",
    "\n",
    "Voir [ici](https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide_%C3%A9tendu) pour des explications complémentaires.\n",
    "\n",
    "On programmera cet algorithme en TD. Voilà à quoi devrait ressembler le résultat (le fichier ent3.py sera fourni au TD suivant). \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ent3 import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, 11, -2)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xgcd(36,196)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "11*36-2*196"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1,\n",
       " -1061502077236761040693843138577467731212359,\n",
       " 40543452640335019725341131413597818079611555515093)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xgcd(1234567891011121314151617181455221577849202122232425,32323255555555555555555514793232323232323232)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Congruences \n",
    "\n",
    "On dit que $a$ est congru à $b$ modulo $n$ si $a$ et $b$ ont même reste dans la division par $n$, ou encore\n",
    "si $a-b$ est divisible par $n$. \n",
    "\n",
    "On écrit $a\\equiv b \\mod n$ ou $a\\equiv b [n]$.\n",
    "\n",
    "En python, le test est `a%n == b%n`.\n",
    "\n",
    "La congruence modulo $n$ est une relation d'équivalence. On peut manipuler les congruences comme des égalités (d'où la notation),\n",
    "car $a\\equiv b [n]$ et $a'\\equiv b' [n]$ entraîne $a+a'\\equiv b+b' [n]$, $aa'\\equiv bb' [n]$, etc.\n",
    "\n",
    "D'où l'idée d'introduire des symboles $\\bar a$ ($a\\in{\\mathbb Z}$) qui vérifient \n",
    "$$\\bar a =  \\bar b\\ \\Leftrightarrow \\ a\\equiv b [n]$$\n",
    "\n",
    "L'addition et  la multiplication modulo $n$ possèdent clairement les mêmes propriétés d'associativité et de ditributivité que leurs versions usuelles. On dit que l'ensemble \n",
    "$${\\mathbb Z}/n{\\mathbb Z}=\\{\\bar 0,\\bar 1, \\ldots,\\overline{n-1}\\},$$\n",
    "muni de ces opérations, est un <i>anneau commutatif unitaire</i>.\n",
    "\n",
    "\n",
    "Voici la table d'addition modulo 12, familière grâce aux horloges à cadran. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " + |  0   1   2   3   4   5   6   7   8   9  10  11  \n",
      "---------------------------------------------------\n",
      " 0 |  0   1   2   3   4   5   6   7   8   9  10  11  \n",
      " 1 |  1   2   3   4   5   6   7   8   9  10  11   0  \n",
      " 2 |  2   3   4   5   6   7   8   9  10  11   0   1  \n",
      " 3 |  3   4   5   6   7   8   9  10  11   0   1   2  \n",
      " 4 |  4   5   6   7   8   9  10  11   0   1   2   3  \n",
      " 5 |  5   6   7   8   9  10  11   0   1   2   3   4  \n",
      " 6 |  6   7   8   9  10  11   0   1   2   3   4   5  \n",
      " 7 |  7   8   9  10  11   0   1   2   3   4   5   6  \n",
      " 8 |  8   9  10  11   0   1   2   3   4   5   6   7  \n",
      " 9 |  9  10  11   0   1   2   3   4   5   6   7   8  \n",
      "10 | 10  11   0   1   2   3   4   5   6   7   8   9  \n",
      "11 | 11   0   1   2   3   4   5   6   7   8   9  10  \n"
     ]
    }
   ],
   "source": [
    "def tabadd(n):\n",
    "    print(' + |', end=' ')\n",
    "    for y in range(n): \n",
    "        print (\"%2d \"% (y % n),end=' ') \n",
    "    print()\n",
    "    print('-'*(4*n+3))\n",
    "    for x in range(n): \n",
    "        print('%2d |'%x, end= ' ')\n",
    "        for y in range(n): \n",
    "            print (\"%2d \"% ((x+y) % n),end=' ') \n",
    "        print()\n",
    "\n",
    "tabadd(12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La table de multiplication est peut-être moins familière. Elle possède quelques propriétés étranges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * |  1   2   3   4   5   6   7   8   9  10  11  \n",
      "-----------------------------------------------\n",
      " 1 |  1   2   3   4   5   6   7   8   9  10  11  \n",
      " 2 |  2   4   6   8  10   0   2   4   6   8  10  \n",
      " 3 |  3   6   9   0   3   6   9   0   3   6   9  \n",
      " 4 |  4   8   0   4   8   0   4   8   0   4   8  \n",
      " 5 |  5  10   3   8   1   6  11   4   9   2   7  \n",
      " 6 |  6   0   6   0   6   0   6   0   6   0   6  \n",
      " 7 |  7   2   9   4  11   6   1   8   3  10   5  \n",
      " 8 |  8   4   0   8   4   0   8   4   0   8   4  \n",
      " 9 |  9   6   3   0   9   6   3   0   9   6   3  \n",
      "10 | 10   8   6   4   2   0  10   8   6   4   2  \n",
      "11 | 11  10   9   8   7   6   5   4   3   2   1  \n"
     ]
    }
   ],
   "source": [
    "def tabmul(n):\n",
    "    print(' * |', end=' ')\n",
    "    for y in range(1,n): \n",
    "        print (\"%2d \"% (y % n),end=' ') \n",
    "    print()\n",
    "    print('-'*(4*n-1))\n",
    "    for x in range(1,n): \n",
    "        print('%2d |'%x, end= ' ')\n",
    "        for y in range(1,n): \n",
    "            print (\"%2d \"% ((x*y) % n),end=' ') \n",
    "        print()\n",
    "\n",
    "tabmul(12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On constate qu'à la différence de la table d'addition, toutes les lignes ou colonnes ne sont pas des permutations les unes des autres.\n",
    "Dans la table d'addition, chaque ligne contient l'élément neutre 0, $({\\mathbb Z}/n{\\mathbb Z},+)$ est un groupe.\n",
    "\n",
    "Par contre, modulo 12, certains éléments n'ont pas d'inverse, et sont des <i>diviseurs de zéro</i>. Par exemple, 2 n'a pas d'inverse,\n",
    "et $\\bar 2\\times \\bar 6 = \\bar 0$.\n",
    "\n",
    "En fait, un diviseur de 0 ne peut jamais être inversible : si on suppose  $ab=0$ et $a'a=1$, alors $a'ab=(a'a)b=(1)b=b$ par associativité, et d'un autre côté, $a'ab = a'(ab)=a'0=0$. Donc $b=0$, et $a$ n'est pas un diviseur de 0.\n",
    "\n",
    "Un *corps*  est un anneau dans lequel tout élément non nul est inversible. Par exemple, ${\\mathbb R}$ est un corps, mais\n",
    "${\\mathbb Z}$ n'en est pas un, car par exemple, 2 n'est pas inversible ($\\frac12$ n'est pas un entier).\n",
    "\n",
    "Un anneau unitaire *fini* sans diviseurs de 0 est toujours un corps : si $a_1=1,\\ldots, a_n$ sont ses éléments non nuls,\n",
    "multiplions les tous par l'un d'entre eux $a_i$. Alors, les $n$ éléments $a_1a_i,\\ldots,a_na_i$ sont tous différents,\n",
    "car si on avait $a_ja_i=a_ka_i$, on aurait aussi $(a_j-a_k)a_i=0$ et donc des divseurs de zéro. Donc, l'un de ces éléments\n",
    "est égal à 1, et $a_i$ possède donc un inverse.\n",
    "\n",
    "Dans ${\\mathbb Z}/n{\\mathbb Z}$, un élément $\\bar a$ est inversible si et seulement si $a\\wedge n=1$. En effet, si $a$\n",
    "et $n$ ont un diviseur commun non trivial $d$, $a=da'$, $n=dn'$, alors $\\bar a\\bar n'=\\bar 0$, bien que $\\bar a$ et $\\bar n'$\n",
    "soient non nuls.\n",
    "\n",
    "Inversement, si $a$ est premier avec $n$, $d=a\\wedge n=1$, et le théorème de Bézout nous fournit $u$ et $v$\n",
    "tels que $1=au+vn$. Donc, dans ${\\mathbb Z}/n{\\mathbb Z}$, $\\bar 1 = \\bar a\\bar u$, et $\\bar a$ est inversible.\n",
    "\n",
    "\n",
    "Le théorème de Bézout fournit donc aussi un algorithme pour calculer les inverses.\n",
    "                                                                                   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inversemod(x,n):\n",
    "    d,u,v = xgcd(x,n)\n",
    "    if d!=1: raise Exception('Element non inversible')\n",
    "    return u if u>0 else n+u "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inversemod(5,12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "ename": "Exception",
     "evalue": "Element non inversible",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mException\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-15-f9834a2a3e89>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0minversemod\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m6\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0;36m12\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-13-3dc2abdd22cb>\u001b[0m in \u001b[0;36minversemod\u001b[0;34m(x, n)\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0minversemod\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m     \u001b[0md\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mu\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mv\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mxgcd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mn\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m     \u001b[0;32mif\u001b[0m \u001b[0md\u001b[0m\u001b[0;34m!=\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;32mraise\u001b[0m \u001b[0mException\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'Element non inversible'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      4\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0mu\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mu\u001b[0m\u001b[0;34m>\u001b[0m\u001b[0;36m0\u001b[0m \u001b[0;32melse\u001b[0m \u001b[0mn\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0mu\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mException\u001b[0m: Element non inversible"
     ]
    }
   ],
   "source": [
    "inversemod(6,12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# On va devoir calculer modulo de grands nombres premiers\n",
    "p = 2**607-1\n",
    "p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "259035297826189280415440051525284294167284042053840121196708556415234119194656404825855151356039585978472335030731928284768581540278171300838917470147014356610272525914613709093739190"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inversemod(111111111111111111111111111111111111,p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(_*111111111111111111111111111111111111)%p"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On vient donc de démontrer :\n",
    "\n",
    "**\"Lorsque $p$ est un nombre premier, ${\\mathbb Z}/p{\\mathbb Z}$ est un corps.\"**\n",
    "\n",
    "Cette propriété est fondamentale. Tout ce qu'on apprend en premier cycle sur les polynômes ou les matrices reste vrai pourvu que les coefficients soient pris  dans un *corps*. L'existence de corps finis tels que les  ${\\mathbb Z}/p{\\mathbb Z}$ permet d'utiliser ces notions en cryptographie ou pour la construction de codes correcteurs d'erreurs.\n",
    "\n",
    "## Le (petit) théorème de Fermat\n",
    "\n",
    "Il est donc important d'étudier les nombres premiers, et en particulier d'être capable de les reconnaître. L'observation suivante \n",
    "sera fondamentale pour la suite.\n",
    "\n",
    "Rappelons la formule du binôme de Newton\n",
    "$$(x+y)^n = \\sum_{k=0}^n{n\\choose k}x^{n-k}y^k,\\quad {n\\choose k}=\\frac{n!}{k!(n-k)!}=\\frac{n(n-1)\\cdots(n-k+1)}{1\\cdot 2\\cdots k}$$\n",
    "\n",
    "\n",
    "Regardons le triangle de Pascal modulo divers entiers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0   1 \n",
      " 1   1   1 \n",
      " 2   1   0   1 \n",
      " 3   1   1   1   1 \n",
      " 4   1   0   0   0   1 \n",
      " 5   1   1   0   0   1   1 \n",
      " 6   1   0   1   0   1   0   1 \n",
      " 7   1   1   1   1   1   1   1   1 \n",
      " 8   1   0   0   0   0   0   0   0   1 \n",
      " 9   1   1   0   0   0   0   0   0   1   1 \n",
      "10   1   0   1   0   0   0   0   0   1   0   1 \n",
      "11   1   1   1   1   0   0   0   0   1   1   1   1 \n",
      "12   1   0   0   0   1   0   0   0   1   0   0   0   1 \n",
      "13   1   1   0   0   1   1   0   0   1   1   0   0   1   1 \n",
      "14   1   0   1   0   1   0   1   0   1   0   1   0   1   0   1 \n",
      "15   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1 \n"
     ]
    }
   ],
   "source": [
    "def binomial(n,k):\n",
    "    if n<k: return 0\n",
    "    if k==0: return 1\n",
    "    return binomial(n-1,k-1)+binomial(n-1,k)\n",
    "\n",
    "\n",
    "def triangle(n,r):\n",
    "    for m in range(n+1):\n",
    "        print (\"%2d\" % m, end = ' ')\n",
    "        for k in range(m+1): \n",
    "            print (\"%3d\" % (binomial(m,k) % r),end = ' ')\n",
    "        print()\n",
    "\n",
    "# Modulo 2        \n",
    "triangle(15,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0   1 \n",
      " 1   1   1 \n",
      " 2   1   2   1 \n",
      " 3   1   0   0   1 \n",
      " 4   1   1   0   1   1 \n",
      " 5   1   2   1   1   2   1 \n",
      " 6   1   0   0   2   0   0   1 \n",
      " 7   1   1   0   2   2   0   1   1 \n",
      " 8   1   2   1   2   1   2   1   2   1 \n",
      " 9   1   0   0   0   0   0   0   0   0   1 \n",
      "10   1   1   0   0   0   0   0   0   0   1   1 \n",
      "11   1   2   1   0   0   0   0   0   0   1   2   1 \n",
      "12   1   0   0   1   0   0   0   0   0   1   0   0   1 \n",
      "13   1   1   0   1   1   0   0   0   0   1   1   0   1   1 \n",
      "14   1   2   1   1   2   1   0   0   0   1   2   1   1   2   1 \n",
      "15   1   0   0   2   0   0   1   0   0   1   0   0   2   0   0   1 \n"
     ]
    }
   ],
   "source": [
    "# Modulo 3\n",
    "triangle(15,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0   1 \n",
      " 1   1   1 \n",
      " 2   1   2   1 \n",
      " 3   1   3   3   1 \n",
      " 4   1   0   2   0   1 \n",
      " 5   1   1   2   2   1   1 \n",
      " 6   1   2   3   0   3   2   1 \n",
      " 7   1   3   1   3   3   1   3   1 \n",
      " 8   1   0   0   0   2   0   0   0   1 \n",
      " 9   1   1   0   0   2   2   0   0   1   1 \n",
      "10   1   2   1   0   2   0   2   0   1   2   1 \n",
      "11   1   3   3   1   2   2   2   2   1   3   3   1 \n",
      "12   1   0   2   0   3   0   0   0   3   0   2   0   1 \n",
      "13   1   1   2   2   3   3   0   0   3   3   2   2   1   1 \n",
      "14   1   2   3   0   1   2   3   0   3   2   1   0   3   2   1 \n",
      "15   1   3   1   3   1   3   1   3   3   1   3   1   3   1   3   1 \n"
     ]
    }
   ],
   "source": [
    "# Modulo 4\n",
    "triangle(15,4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0   1 \n",
      " 1   1   1 \n",
      " 2   1   2   1 \n",
      " 3   1   3   3   1 \n",
      " 4   1   4   1   4   1 \n",
      " 5   1   0   0   0   0   1 \n",
      " 6   1   1   0   0   0   1   1 \n",
      " 7   1   2   1   0   0   1   2   1 \n",
      " 8   1   3   3   1   0   1   3   3   1 \n",
      " 9   1   4   1   4   1   1   4   1   4   1 \n",
      "10   1   0   0   0   0   2   0   0   0   0   1 \n",
      "11   1   1   0   0   0   2   2   0   0   0   1   1 \n",
      "12   1   2   1   0   0   2   4   2   0   0   1   2   1 \n",
      "13   1   3   3   1   0   2   1   1   2   0   1   3   3   1 \n",
      "14   1   4   1   4   1   2   3   2   3   2   1   4   1   4   1 \n",
      "15   1   0   0   0   0   3   0   0   0   0   3   0   0   0   0   1 \n"
     ]
    }
   ],
   "source": [
    "# Modulo 5\n",
    "triangle(15,5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On observe que lorsque $n$ est premier, apparemment, tous les ${n\\choose k}$ sont divisbles par $n$, sauf le premier et le dernier\n",
    "qui valent toujours 1. De fait, la formule avec les factorielles montre que ce nombre, qui est un entier, est le résultat de\n",
    "la simplification d'une fraction dont le numérateur est divisible par $n$, mais pas le dénominateur si on suppose que $n$ est premier. Donc le résultat \n",
    "est divisible par $n$.\n",
    "\n",
    "Pour $p$ premier, la formule du binôme dans ${\\mathbb Z}/p{\\mathbb Z}$ devient ainsi\n",
    "$$(\\bar x + \\bar y)^p = \\bar x^p + \\bar y^p.$$\n",
    "On peut itérer : $(\\bar x + \\bar y+ \\bar z)^p = \\bar x^p + (\\bar y+\\bar z)^p$, etc., de sorte qu'en écrivant un entier\n",
    "quelconque $a=1+1+\\cdots+1$ ($a$ fois), on a\n",
    "$$\\bar a^p = (\\bar 1 +\\bar 1 + \\cdots + \\bar 1)^p =   \\bar 1^p + \\bar 1^p + \\cdots+\\bar 1^p = \\bar 1 +\\bar 1 + \\cdots + \\bar 1=\\bar a$$\n",
    "\n",
    "Ainsi, tout élément de ${\\mathbb Z}/p{\\mathbb Z}$ vérifie\n",
    "$$\\bar a^p=\\bar a$$\n",
    "et s'il est inversible,\n",
    "$$\\bar a^{p-1}=\\bar 1.$$\n",
    "\n",
    "Cet énoncé constitue le *petit théorème de Fermat*, qu'on énonce habituellement avec des congruences :\n",
    "\n",
    "\"Si $p$ est premier, tout entier $a$ vérifie $a^p\\equiv a\\mod p$, et si de plus $a$ est premier avec $p$, alors $a^{p-1}\\equiv 1\\mod p$.\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Par exemple, 2^607-1 est premier\n",
    "p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# On écrira une fonction powermod(a,m,p) qui calcule a**m % p\n",
    "powermod(42,p-1,p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "583992399055640987986069965529637289586333248927815671114136642291107221402710705472756839848623539171666215625420084135768154204336056063776340648924443416096255318318113913610607896607565283327"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Celui ci n'est pas premier\n",
    "n = 2**647-1\n",
    "n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "21428223903520356654322755377445578958208675410619789103596222568646209820633205931060590298644292314996507952112174748503760913459299420318597663375422240564022629209691880886344754719021729800"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Ce calcule le prouve\n",
    "powermod(3,n-1,n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exponentiation modulaire\n",
    "\n",
    "La fonction `powermod` calcule efficacement $a^m\\mod n$ par le procédé suivant (voir [ici](https://fr.wikipedia.org/wiki/Exponentiation_modulaire)). On écrit (en pensée) l'exposant $m$ en binaire $m=b_k\\cdots b_1b_0$. Les bits $b_i$ sont calculés\n",
    "au fur est à mesure. Au départ, le résultat intermédiare\n",
    "`res` est 1. On calcule $b_0=m\\mod 2$. Si $b_0=1$ on multiplie `res` par $a$ modulo $n$. On divise $m$ par 2, on remplace\n",
    "$a$ par $a^2\\mod n$, et on recommence. Ceci calcule\n",
    "$$\\bar a^m = (\\bar a)^{b_0}(\\bar a^2)^{b_1})(\\bar a^{(2^2)})^{b_2}\\cdots (\\bar a^{(2^k)})^{b_k}$$\n",
    "en remarquant que $(x^{(2^i)})^2 = x^{(2^{i+1})}$ (programme de maths de 4ème ...).\n",
    "\n",
    "\n",
    "On calcule les bits $b_i$ au fur et à mesure. Au départ, $b_0 = m\\, {\\rm mod}\\, 2$ est `m % 2` ou `m & 1`. Si c'est 1,\n",
    "on multiplie le resultat `res` par $a$, sinon on ne fait rien. Puis on remplace $a$ par $a^2\\,{\\rm mod}\\,n$\n",
    "et $m$ par `m//2` ou `m>>1` et on recommence.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def powermod(a,m,n):\n",
    "    res = 1\n",
    "    while m:\n",
    "        if m & 1: res = (res*a) %n\n",
    "        m >>= 1\n",
    "        a = (a*a) %n\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "powermod(3,33333,11)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2221376488713205668017410030004"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "powermod(5,666,2**101-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2221376488713205668017410030004"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pow(5,666,2**101-1) # la fonction standard de Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tests de primalité\n",
    "\n",
    "Le théorème de Fermat permet de prouver qu'un nombre $n$ *n'est pas* premier en exhibant un $a$ tel que $a^{n-1}\\not\\equiv 1\\mod n$.\n",
    "C'est le *test de Fermat*.\n",
    "On peut montrer que chaque fois qu'on obtient 1, la probabilité que $n$ ne soit pas premier est *presque* divisée par 4.\n",
    "Malheureusement, il existe des nombres non premiers (les [nombres de Carmichael](https://fr.wikipedia.org/wiki/Nombre_de_Carmichael)) qui passent tous les tests de Fermat avec $a\\wedge n=1$. Ils sont très rares, mais suffisent à faire capoter l'entreprise.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le *test de Miller-Rabin* permet de remédier à ce problème. C'est une petite modification du calcul de $a^{n-1}\\mod n$\n",
    "dans laquelle on rajoute un test.\n",
    "\n",
    "L'idée est que dans un corps, l'équation $x^2-1=0$ ne peut pas avoir plus de deux solutions. Dans les entiers modulo\n",
    "$n$, on a toujours $\\bar 1$ et $-\\bar 1$, et $x^2-\\bar 1=(x-\\bar 1)(x+\\bar 1)$. Si on en trouve une autre \n",
    "$\\bar b$, alors $(\\bar b-\\bar 1)(b+\\bar 1)=\\bar b^2-\\bar 1=\\bar 0$, donc\n",
    "on a des diviseurs de 0 et $n$ n'est pas premier.\n",
    "\n",
    "Pour cela, on écrit $n-1=2^km$ avec $m$ impair, et on commence par calculer \n",
    "$b=a^m \\mod n$. Si $b=1$, on renvoie True (probablement premier). \n",
    "Sinon, on calcule les $b^{(2^i)}\\mod n$ et la première fois que le résultat vaut 1, \n",
    "on teste si la valeur précédente était $\\equiv -1\\mod n$. \n",
    "Si ce n'est pas le cas, on renvoie False (composé). Si on arrive à $b^{(2^k)}$ \n",
    "sans avoir rencontré de racine carrée non triviale de 1, on renvoie True.\n",
    "\n",
    "Par exemple, 561 est un nombre de Carmichael. Si on calcule $2^{560}\\,{\\rm mod}\\, 561$, on trouve 1.\n",
    "Mais si on décompose le calcul en écrivant\n",
    "$$560 =2^4\\cdot 35,\\ 2^{560} = (2^{35})^{2^4}$$\n",
    "et en calculant d'abord $b=2^{35}\\,{\\rm mod}\\, 561 = 263$, puis $b^2,b^4,b^8,b^{16}=2^{560}$,\n",
    "on peut observer que $b^4=67$ et $(b^4)^2=1$. On a donc trouvé une racine carrée de 1 modulo 561 autre que $\\pm 1$.\n",
    "Donc 561 n'est pas premier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(2, 4), (5, 1), (7, 1)]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(560)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "263"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b = powermod(2,5*7,561);b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "263 166 67 1 1 "
     ]
    }
   ],
   "source": [
    "# 2**9 = 512\n",
    "for i in range(5): print(powermod(b,2**i,561), end=' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "powermod(67,2,561)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1 1 1 1 1 1 1 1 1 "
     ]
    }
   ],
   "source": [
    "# en voilà un assez grand\n",
    "c = 1590231231043178376951698401\n",
    "for a in range(2,12): print (powermod(3,c-1,c), end= ' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(17, 1), (19, 1), (23, 1), (29, 1), (31, 1), (37, 1), (41, 1), (43, 1), (61, 1), (67, 1), (71, 1), (73, 1), (79, 1), (97, 1), (113, 1), (199, 1)]\n"
     ]
    }
   ],
   "source": [
    "print (factor(c))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "miller_rabin(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Le théorème des restes chinois\n",
    "\n",
    "Il permet de résoudre les système de conguences\n",
    "\n",
    "$$\n",
    "\\left\\{ \\begin{matrix} x &\\equiv& x_1& [m_1] \\\\\n",
    "       x &\\equiv& x_2& [m_2]\\\\ \n",
    "       \\vdots & \\cdots &\\vdots \n",
    "       \\\\ x&\\equiv &x_n&[m_n]\\end{matrix}\\right.$$\n",
    "\n",
    "\n",
    "\n",
    "lorsque les modules $m_i$ sont deux à deux premiers entre eux.\n",
    "\n",
    "Pour chaque $i$, il est facile de trouver $a_i$ qui vérifie $a_i\\equiv 0\\ [m_j]$ pour tous les $j\\not=i$. Il suffit\n",
    "de prendre $a_i=\\prod_{j\\not=i}m_j$. Ce nombre est premier avec $m_i$, donc inversible modulo $m_i$. Calculons\n",
    "les coefficients de Bézout tels que $1=u_ia_i+v_im_i$. Alors, $y_i=u_ia_i$ vérifie $y_i\\equiv 1 \\ [m_i]$ et\n",
    "$y_i\\equiv 0\\ [m_j]$ pour $j\\not=i$, ce qui entraîne que\n",
    "$$X := y_1x_1+y_2x_2+\\cdots y_nx_n$$\n",
    "est solution du système. Il y en a d'autres : en ajoutant le produit $m=m_1m_2\\cdots m_n$ à une solution, on obtient une autre solution,\n",
    "et deux solutions quelconques $x',x''$ diffèrent forcément d'un multiple de de $m$, puisque leur différence est divisible\n",
    "par tous les $m_i$.\n",
    "\n",
    "La plus petite solution positive du système est donc\n",
    "$$x = y_1x_1+y_2x_2+\\cdots y_nx_n \\mod m.$$\n",
    "\n",
    "\n",
    "*Exemple* Le problème des pirates (posé au CAPES de Maths)\n",
    "\n",
    ">    Une bande de 17 pirates possède un trésor constitué de pièces d'or d'égale valeur. Ils projettent de se les partager également, et de donner le reste au cuisinier chinois. Celui-ci recevrait alors 3 pièces. Mais les pirates se querellent, et six d'entre eux sont tués. Un nouveau partage donnerait au cuisinier 4 pièces. Dans un naufrage ultérieur, seuls le trésor, six pirates et le cuisinier sont sauvés, et le partage donnerait alors 5 pièces d'or à ce \n",
    "dernier.\n",
    "Quelle est la fortune minimale que peut espérer le cuisinier s'il décide d'empoisonner le reste des pirates ? \n",
    "\n",
    "\n",
    "On doit donc résoudre\n",
    "$$\n",
    "\\left\\{ \\begin{matrix} x &\\equiv& 3& [17] \\\\\n",
    "x &\\equiv& 4& [11] \\\\\n",
    "x &\\equiv& 5& [6] \\\\\n",
    "\\end{matrix}\\right.\n",
    "$$\n",
    "On cherche $a_1$ qui vérifie $a_1\\equiv 0$ mod $11,6$. On prend $a_1=6\\times 11=66$, et on calcule son inverse modulo 17.\n",
    "Comme $66=4\\times 17-2\\equiv -2$ et $2\\times 9=18\\equiv 1$, on a (de tête) $(-2)(-9)\\equiv 1$, l'inverse cherché est\n",
    "$-9\\equiv 8$. On a donc que $y_1=8\\times 66 = 528$ est congru à 1 modulo 17 et à 0 modulo 11 et 6.\n",
    "\n",
    "On prend ensuite $a_2=17\\times 6 = 102$ qui est congru à 3 modulo 11. Son inverse est donc 4, et $y_2=4\\times 102=408$.\n",
    "\n",
    "Finalement, $a_3=17\\times 11= 187$ est congru à 1 modulo 6 donc $y_3=187$.\n",
    "\n",
    "La plus petite solution positive sera\n",
    "$$x = 3\\times 528 + 4\\times 408+5\\times 187 \\mod 17\\times 11\\times 6 = 4151 \\mod 1122 = 785.$$\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "Voir [ici](https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_des_restes_chinois).\n",
    "\n",
    "Par exemple, avec $(x_1,x_2,x_3,x_4)=(1,2,3,4)$ et $(m_1,m2,m_3,m4)=(1,13,17,19)$, on trouve $x= 41823$ :\n",
    "```python\n",
    "solve_chinese([1,2,3,4], [11,13,17,19])\n",
    "41823\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quelques résultats de théorie des groupes\n",
    "\n",
    "On connaît déjà quelques exemples de groupes finis : les $({\\mathbb Z}/n{\\mathbb Z})^\\times$, les éléments inversibles de\n",
    "${\\mathbb Z}/n{\\mathbb Z}$, forment un groupe dont le nombre d'éléments est noté $\\varphi(n)$ (indicateur d'Euler).\n",
    "\n",
    "Le $\\times$ en exposant signifie *groupe multiplicatif*, il est formé des éléments inversibles.\n",
    "\n",
    "Par exemple,\n",
    "$$({\\mathbb Z}/12{\\mathbb Z})^\\times=\\{1,5,7,11\\}.$$\n",
    "\n",
    "### Le théorème de Lagrange\n",
    "\n",
    "On appelle *ordre* d'un élément $g$ d'un groupe fini $G$ (noté multiplicativement, d'élement neutre 1), le plus petit entier positif $m$ tel que $g^m=1$.\n",
    "\n",
    "Il existe : puisque $G$ est fini, la suite $g^k$ des puissances de $g$ contient forcément deux éléments égaux, et si $g^k=g^l$, ($k<l$), alors $g^{l-k}=1$.\n",
    "\n",
    "On appelle *ordre* du groupe $G$ son nombre d'éléments.\n",
    "\n",
    "Ce choix judicieux des définitions permet d'énoncer élégamment le *théorème de Lagrange* :\n",
    "\n",
    ">*Dans un groupe fini, l'ordre de tout élément est un diviseur de l'ordre du groupe.*\n",
    "\n",
    "En effet, prenons un élément $h$ de $G$, d'ordre $m$ dans un groupe d'ordre $n$. Alors, ou bien $m=n$, et c'est fini, ou bien $m<n$. Dans ce cas,\n",
    "on peut trouver un élément $g_1$ qui n'est pas dans l'ensemble $H$ des puissances de $h$. \n",
    "L'ensemble $g_1H=\\{g_1,g_1h,\\ldots,g_1h^{m-1}\\}$ a lui aussi $m$ éléments distincts, dont aucun n'est dans $H$ :\n",
    "si on avait $g_1h^i = h^j$ alors, $g_1=h^{j-i}$ serait dans $H$. Si on ne peut pas trouver $g_2$ qui ne soit ni dans\n",
    "$H$, ni dans $g_1H$, alors, l'ordre $n$ de $G$ est $n=2m$, et on a fini. Sinon, on recommence avec $g_2$, et ainsi de\n",
    "suite, jusqu'à obtenir $G$ comme réunion disjointe d'ensembles $H,g_1H,\\ldots,g_{k-1}H$ ayant tous $m$ éléments,\n",
    "et alors, $n=km$.\n",
    "\n",
    "Voir aussi [ici](https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Lagrange_sur_les_groupes).\n",
    "\n",
    "#### Fermat\n",
    "Si $G=({\\mathbb Z}/p{\\mathbb Z})^\\times$ avec $p$ premier, $n=p-1$, et donc tout élément vérifie $\\bar a^{p-1}=\\bar 1$.\n",
    "\n",
    "#### Euler\n",
    "Si $G=({\\mathbb Z}/n{\\mathbb Z})^\\times$, d'ordre $\\varphi(n)$, tout élément vérifie $\\bar a^{\\varphi(n)}=\\bar 1$.\n",
    "\n",
    "Autrement dit, tout entier $a$ premier avec $n$ vérifie $a^{\\varphi(n)}\\equiv 1\\,[n]$.\n",
    "#### Calcul de $\\varphi(n)$\n",
    "\n",
    "Si $n=p_1^{m_1}\\cdots p_r^{m_r}$ est la décomposition de $n$ en facteurs premiers, le théorème des restes chinois montre que\n",
    "$${\\mathbb Z}/n{\\mathbb Z} \\simeq {\\mathbb Z}/p_1^{m_1}{\\mathbb Z}\\times\\cdots\\times {\\mathbb Z}/p_r^{m_r}{\\mathbb Z}$$\n",
    "les opérations s'effectuant composante à composante sur les $r$-uples. Donc, un élément sera inversible si et seulement si ses résidus modulo tous les $p_i^{m_i}$ le sont.\n",
    "\n",
    "Il suffit donc de savoir calculer $\\varphi(p^m)$. Les éléments *non inversibles* de ${\\mathbb Z}/p^m{\\mathbb Z}$\n",
    "sont les entiers $0\\le a<p^m$ qui sont divisibles par $p$, c'est à dire $0,p,2p,3p,\\ldots,(p^{m-1}-1)p$. Il y en a donc\n",
    "$p^{m-1}$, et $\\varphi(p^m)=p^m-p^{m-1}$.\n",
    "\n",
    "Le produit de ces nombres peut s'écrire\n",
    "$$\\varphi(n)=n\\prod_{p|n}\\left(1-\\frac1p\\right)$$\n",
    "(produit sur les diviseurs premiers de $n$).\n",
    "\n",
    "On peut exprimer cette formule grace à la *fonction de Möbius* $\\mu$\n",
    "$$\\mu(n) =\n",
    "\\begin{cases}\n",
    "1 & \\text{si $n=0$}\\\\\n",
    "(-1)^r&\\text{si $n=p_1\\cdots p_r$ est produit de $r$ nombres premiers distincts}\\\\\n",
    "0 & \\text{sinon}\n",
    "\\end{cases}\n",
    "$$\n",
    "\n",
    "En développant le produit, on a\n",
    "$$\\varphi(n)=\\sum_{d|n}\\mu(d)\\frac nd.$$\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "Remarquons que $\\varphi(n)$ est aussi le nombre d'élements d'ordre (additif) $n$ dans ${\\mathbb Z}/n{\\mathbb Z}$. En effet, $kx\\equiv 0\\mod n\\Rightarrow n|k$ si et seulement si $x\\wedge n =1$. Pour un diviseur $d$ de $n$, $\\varphi(d)$ est donc le nombre d'éléments d'ordre $d$ dans ${\\mathbb Z}/n{\\mathbb Z}$, et on a\n",
    "$$n = \\sum_{d|n}\\varphi(d).$$\n",
    "\n",
    "\n",
    "\n",
    "L'équivalence des deux expressions est un cas particulier de la [formule d'inversion de Möbius](https://fr.wikipedia.org/wiki/Fonction_de_M%C3%B6bius), qui relie deux fonctions $f$ et $g$ sur les entiers positifs \n",
    "\n",
    "$$ g(n)= \\sum_{d|n}f(d)\\quad \\Leftrightarrow \\quad  f(n)=\\sum_{d|n}\\mu(d)g\\left(\\frac{n}{d}\\right).$$\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}