{
 "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": "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": [
    "#### 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": [
    "#### 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": [
    "#### Exercice 5\n",
    "\n",
    "1. Calculer $42^{666}\\mod 43$. \n",
    "2. Sachant que $p=2^{107}-1$ est premier, calculer $2^{(2^{108})}\\mod p$.\n",
    "3. Prouver que $2^{70}+3^{70}$ est divisible par 13."
   ]
  }
 ],
 "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
}