{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# M1 Cryptographie\n",
    "## Mise à niveau en arithmétique\n",
    "\n",
    "### Exercices à résoudre sur papier, n'utiliser l'ordinateur que comme calculette\n",
    "\n",
    "\n",
    "#### Exercice 1\n",
    "$\\def\\ZZ{{\\mathbb Z}}$\n",
    "1. Calculer la table de multiplication de $\\ZZ/9\\ZZ$. On note $G_9$ le groupe de ses éléments inversibles.\n",
    "2. Donner la liste des éléments de $G_9$ et la valeur de $\\varphi(9)$. Comparer avec la formule du cours pour $\\varphi(n)$.\n",
    "3. Vérifier que 2 est d'ordre $\\varphi(9)$. Quel est l'ordre de 4 ? Et celui de 8 ?\n",
    "4. Pour chaque élément de $G_9$ indiquer son inverse.\n",
    "5. Le groupe $G_9$ est-il cyclique ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * |  1   2   3   4   5   6   7   8  \n",
      "-----------------------------------\n",
      " 1 |  1   2   3   4   5   6   7   8  \n",
      " 2 |  2   4   6   8   1   3   5   7  \n",
      " 3 |  3   6   0   3   6   0   3   6  \n",
      " 4 |  4   8   3   7   2   6   1   5  \n",
      " 5 |  5   1   6   2   7   3   8   4  \n",
      " 6 |  6   3   0   6   3   0   6   3  \n",
      " 7 |  7   5   3   1   8   6   4   2  \n",
      " 8 |  8   7   6   5   4   3   2   1  \n"
     ]
    }
   ],
   "source": [
    "# 1.\n",
    "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(9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Les éléments inversibles sont ceux qui n'ont pas de diviseur commun avec 9, c'est à dire 1,2,4,5,7,8.\n",
    "Il y en a 6, donc *par définition* $\\varphi(9)=6$.\n",
    "\n",
    "La formule du cours donne\n",
    "$$\\varphi(9)=9\\left(1-\\frac13\\right)=9\\times\\frac23=6$$\n",
    "ou encore\n",
    "$$\\varphi(9)=\\mu(9)1+\\mu(3)3+\\mu(1)9=0-3+9=6.$$\n",
    "\n",
    "3. $2^1=1$, $2^2=4$, $2^3=8$, $2^4=16\\equiv 7$, $2^5=2\\times 7=14\\equiv 5$, $2^6=2\\times 5=10\\equiv 1$.\n",
    "Donc 2 est d'ordre 6.\n",
    "\n",
    "Pour $4$, on a $4^2=7$, $4^3=7\\times 4=28=1$ donc 4 est d'ordre 3.\n",
    "\n",
    "Pour $8$, $8^2=64=63+1=1$, il est d'ordre 2.\n",
    "\n",
    "2,3 et 6 sont bien des diviseurs de 6, comme prédit par le théorème de Lagrange.\n",
    "\n",
    "4. $1=1\\times 1= 2\\times 5=4\\times 7=8\\times 8$.\n",
    "\n",
    "5. 2 est d'ordre 6, donc le groupe $G_9$ est cyclique."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercice 2\n",
    "\n",
    "Calculer le pgcd $d$ de $a=561$ et $b=476$ par l'algorithme d'Euclide étendu, et trouver $u$ et $v$ tels que $d=au+bv$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le tableau des divisions itérées style CM2 donne"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "      | 1   | 5  | 1  | 1  | 2\n",
    "----------------------------------------------------------------\n",
    "  561 | 476 | 85 | 51 | 34 | 17\n",
    "-----------------------------------------------------------------\n",
    "   85 |  51 | 34 | 17 |  0 |\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le dernier reste non nul est 17, qui est donc le pgcd.\n",
    "\n",
    "On remonte le calcul : $17=51-34$, $34=85-51$, $85=561-476=a-b$, $51=476-5\\times 85=b-5(a-b)=-5a+6b$,\n",
    "$34=(a-b)-(-5a+6b)=6a-7b$, $17=51-34=-5a+6b-(6a-7b)=-11a+13b$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercice 3\n",
    "\n",
    "On va utiliser le système RSA avec $p=11$,  $q=13$.\n",
    "\n",
    "1. Calculer $n=pq$, et écrire $p,q,n$ en binaire. \n",
    "2. En conclure qu'on peut utiliser ce système pour chiffrer les caractères ASCII (codes de 0 à 127)\n",
    "3. Calculer $\\varphi(n)$. \n",
    "4. Peut-on utiliser l'exposant public $e=3$ ? Pourquoi ?\n",
    "5. On choisit $e=17$. Calculer l'exposant privé $d$.\n",
    "6. Si on prenait $e=11$, quel serait l'exposant privé ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. $n=11\\times 13=143$. $11=\\overline{1011}$, $13=\\overline{1101}$, $143 =\\overline{10001111}$.\n",
    "\n",
    "2. On a bien $127<143$.\n",
    "\n",
    "3. $\\varphi(n)=(p-1)(q-1)=120$.\n",
    "\n",
    "4. 3 n'est pas inversible modulo 120, donc on ne peut pas.\n",
    "\n",
    "5. L'exposant privé $d$ est l'inverse de $e$ modulo 120. On a $17\\times 7=119\\equiv -1\\mod 120$ donc l'inverse\n",
    "est $-7=113$.\n",
    "\n",
    "6. Si on prenait $e=11$, comme $11\\times 11=121\\equiv 1\\mod 120$, l'exposant privé serait aussi égal à 11."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercice 4\n",
    "\n",
    "Résoudre\n",
    "$$\\left\\{\\begin{matrix}x\\equiv 2\\ [3]\\\\ x\\equiv 3\\ [5]\\\\ x\\equiv 2 \\ [7]\\end{matrix}\\right.$$\n",
    "\n",
    "ensuite, regarder [là](https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_des_restes_chinois)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On a $5\\times 7=35\\equiv 0 \\mod 5$  et 7 par définition, et $35\\equiv 2\\mod 3$, donc si on multiplie 35 par l'inverse de 2 modulo 3, qui est 2, on trouve 70 qui vaut bien 1 modulo 3 et 0 modulo 5 et 7.\n",
    "\n",
    "Ensuite, $3\\times 7=21\\equiv 1\\mod 5$ donc il n'y a rien d'autre à faire.\n",
    "\n",
    "De même, $3\\times 5=15\\equiv 1\\mod 7$, donc là non plus.\n",
    "\n",
    "Une solution est donc $2\\times 70+3\\times 21+2\\times 15 = 233$. La plus petite solution positive s'obtient\n",
    "en réduisant ce nombre modulo $3\\times 5\\times 7=105$, ce qui donne $x=23$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercice 5\n",
    "\n",
    "1. Calculer $42^{666}\\mod 43$. \n",
    "\n",
    "$42\\equiv -1\\mod 43$ donc $42^{666}\\mod 43=1$.\n",
    "\n",
    "2. Sachant que $p=2^{107}-1$ est premier, calculer $2^{(2^{108})}\\mod p$.\n",
    "\n",
    "D'après Fermat, $2^{(2^{107})-2}\\equiv 1\\mod p$, donc $2^{(2^{107})}\\equiv 2^2=4\\mod p$, \n",
    "et $2^{2^{108}}=\\left(2^{(2^{107})}\\right)^2\\equiv 4^2=16\\mod p$.\n",
    "\n",
    "3. Prouver que $2^{70}+3^{70}$ est divisible par 13.\n",
    "\n",
    "Il faut montrer que $2^{70}+3^{70}\\equiv 0\\ [13]$, donc calculer $2^{70}$ et $3^{70}$ modulo 13.\n",
    "Comme 13 est premier, tout entier non divisible par 13 vérifie $a^{12}\\equiv 1\\ [13]$.\n",
    "\n",
    "\n",
    "On a $70\\equiv 10 \\mod 12$ donc $2^{70}+3^{70}\\equiv 2^{10}+3^{10} \\mod 13$.\n",
    "On a $2^5=32\\equiv 6$ donc $2^{10}\\equiv 36 \\equiv 10\\mod 13$\n",
    "et $3^3=27\\equiv 1 \\mod 13$ donc $3^{10}\\equiv 3$. Maintenant, $10+3=13$ ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}