{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "569c4f8e",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "# TP2 – Théorème chinois & algorithme de Miller-Rabin"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9be34657",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "## 1. Théorème chinois"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7447ebf4",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "1. Le théorème chinois, et l'algorithme `RestesChinois`, utilisent des PGCD et des inversions modulaires. Trouver la méthode qui, étant donnée deux entiers $a$ et $N$, calcule l'inverse de $a$ modulo $N$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "a2456e05",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "e6b858a6",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "2. Écrire une fonction `RestesChinois` qui prend en entrée deux listes ($a_1$, …, $a_k$ et $n_1$, …, $n_k$) et renvoie l'unique entier $z < \\prod_i n_i$ qui vérifie $z≡_{n_i} a_i$ pour tout $i$. *Votre fonction doit vérifier que les entrées sont correctes, c'est-à-dire que les deux listes ont la même longueur, et que les $n_i$ sont premiers deux à deux.* "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "3efef757",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "1969d402",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "3. SageMath fournit des fonctions qui permettent d'écrire facilement du code mathématique. En particulier, lire la documentation de la fonction `prod` et écrire une nouvelle version de `ResteChinois` qui l'utilise. On peut aussi utiliser la fonction `sum` de la même façon."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "7aeda84a",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "c21dd025",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "4. Le théorème chinois permet de définir une bijection entre $\\{0,…,n_1-1\\}×\\dotsb×\\{0,…,n_k-1\\}$ et $\\{0,…,N-1\\}$ où $N = \\prod_{i=1}^k n_i$. Quel sens de la bijection est fourni par `RestesChinois` ? Écrire la fonction réciproque, et tester que les deux fonctions sont bien réciproques l'une de l'autre."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "33f1f25e",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "8af1dfdb",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "## 2. Algorithme de Miller-Rabin\n",
    "\n",
    "L'algorithme de Miller-Rabin permet de tester si un nombre entier est premier. Le principe de base est le test de     Fermat, basé sur le petit théorème de Fermat : si $p$ est premier, alors $a^{p-1} ≡_p 1$ pour $0 < a < p$. Pour que   le test fonctionne il faut vérifier que si $N$ n'est pas premier, alors $a^{N-1}$ n'est pas toujours congru à $1$     modulo $N$. Un tel entier $a$ est appelé un *témoin* du fait que $a$ n'est pas premier.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "13831ef9",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Question 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5536c5d9",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "Pour les tests, on a besoin de générer des nombres premiers aléatoires, ainsi que des nombres composés (non premiers) aléatoires.\n",
    "\n",
    "**1.** Trouver la fonction SageMath qui renvoie un premier aléatoire $≤ N$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "5fffa551",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "a9f6b1c1",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "**2.** Il n'existe pas de fonction prédéfinie qui renvoie un entier composé. Écrire une fonction `random_composite(N)` qui prend en entrée $N$ et renvoie un nombre composé entre $2$ et $N-1$. *Pour cela, tirer des entiers aléatoires et vérifier s'ils sont premiers avec la méthode `is_prime`.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "2beff408",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "9e36b639",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Question 1\n",
    "**1.i.** Trouver la méthode des entiers qui permet de calculer $a^b\\bmod c$, étant donnés des entiers $a$, $b$ et $c$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "0061da88",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "2d19ff00",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "**1.ii.** Écrire une fonction `NombreTemoins(N)` qui compte le nombre d'entiers $a$ entre $1$ et $N-1$ tels que $a^{N-1}\\not≡_N1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "1eb79c5f",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "5a78b681",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "**1.iii.** Utiliser la fonction pour estimer la proportion de témoins, d'une part pour les nombres premiers et d'autre part pour les nombres composés. Conseils :\n",
    "* Tester sur des nombres jusqu'à 4 ou 5 chiffres décimaux.\n",
    "* Pour chaque catégorie, tirer quelques centaines de nombres et stocker dans un tableau `P` la proportion de témoins pour chacun d'entre eux ; à la fin, on peut afficher `max(P)` et `min(P)`, ainsi que la moyenne avec `sum(P)/len(P)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "8fa3462d",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "79a7b6a5",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "e6c84688",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "**1.iv.** Estimer la proportion pour les premiers nombres de Carmichael, dont la liste est fournie ci-dessous. *Les nombres de Carmichael sont des nombres composés.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "317f306d",
   "metadata": {
    "tags": [
     "sujet"
    ]
   },
   "outputs": [],
   "source": [
    "C = [561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973,75361,101101,115921,126217,162401,172081,188461,252601,278545,294409,314821,334153,340561,399001,410041,449065,488881,512461]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "0f359e2e",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "f47d64d4",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Question 2\n",
    "Le test de Fermat découle des remarques sur le petit théorème de Fermat : pour tester si un nombre $N$ est premier, on tire un entier $a$ entre $2$ et $N-1$ et on vérifie si $a^{N-1}≡_N1$. Si c'est le cas, on affirme que $N$ est premier, sinon qu'il est composé. C'est un test probabiliste, qui peut parfois se tromper."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ecc44cb",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "**2.i.** Écrire une fonction `TestFermat(N)` qui implante le test de Fermat."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "93b32f07",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "4317268a",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "**2.ii.** Tester le test de Fermat avec différents nombres : des nombres premiers, des nombres composés, et les nombres de Carmichael. Estimer empiriquement la probabilité que le test échoue, en fonction des types de nombres. Conseil :\n",
    "* De même que pour la proportion de témoin, on calcule une liste de probabilité et on affiche le maximum, le minimum et la moyenne de la liste.\n",
    "* Le test de Fermat est probabiliste : pour chaque entier testé, on peut répéter 100 fois le test, et déterminer la proportion de fois qu'il a répondu `True`.\n",
    "* Étant donné la vitesse de calcul, on peut aisément tester 10 000 entiers jusqu'à 5 chiffres."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "178cd0ba",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "ff1c1450",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "9104e41b",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "b88dd3ea",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Question 3\n",
    "Le test de Fermat échoue très souvent sur les nombres de Carmichael. L'algorithme de Miller-Rabin est un raffinement du test de Fermat, qui fonctionne pour tous les nombres.\n",
    "\n",
    "On considère $N$ impair. On écrit $N-1 = 2^v⋅m$ avec $m$ impair. L'idée est de calculer la suite $(b_i)_{0\\le i\\le v}$ où $b_i = a^{2^i⋅m}\\bmod N$. \n",
    "* Si $N$ est premier, $b_v = 1$ d'après le petit théorème de Fermat. Et comme $N$ est premier, les seules *racines carrées* de $1$ sont $1$ et $N-1$. Donc soit $b_0 = \\dotsb = b_v = 1$, soit il existe $i < v$ tel que $b_i = N-1$.\n",
    "* Ce qu'on souhaite vérifier, c'est que si $N$ n'est pas premier, alors avec bonne probabilité, la suite $(b_i)$ n'a pas la forme décrite pour les nombres premiers. En particulier, cela signifie que soit $b_v ≠ 1$, soit on *passe directement* d'un $b_i ≠1,N-1$ à $b_{i+1} = 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb4e85e1",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "**3.1.** Écrire une fonction `decompose(N)` qui renvoie $v$ et $m$, $m$ impair, tels que $N-1 = 2^v⋅m$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "426a157a",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "299c9d3f",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "**3.2.** Écrire une fonction `SuiteB(N)` qui tire aléatoirement un entier $a$ entre $2$ et $N-1$, et renvoie la liste $[b_0, …, b_v]$ comme définie ci-dessus."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "5e92b38a",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "7055fda2",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "**3.3.** Écrire une fonction `testSuiteB(N)` qui calcule une suite de $b_i$ en appelant `suiteB(N)`, et qui renvoie `True` si elle vérifie les conditions énoncées dans le cas de $N$ premier, et `False` sinon."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "84b50bf1",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "efc9b16e",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "**3.4** Vérifier que pour un nombre premier, la suite calculée vérifie toujours les conditions énoncées. Vérifier que pour des nombres composés, dont les nombres de Carmichael, la suite calculée ne vérifie les conditions des nombres premiers que très rarement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "7dd19d73",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "8222d8d1",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "a2be08fe",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "33ef61e7",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "### Question 4\n",
    "L'algorithme de Miller-Rabin est quasiment écrit : il s'agit de tirer aléatoirement plusieurs valeurs $a$ aléatoirement, de calculer à chaque fois la suite $(b_i)$ et de vérifier si elle vérifie les conditions des nombres premiers. Si toutes les suites $(b_i)$ vérifient les conditions, l'algorithme répond `True` (le nombre est premier) sinon il répond `False`.\n",
    "\n",
    "**4.1** Écrire une fonction `MillerRabin(N,k)` qui implante cet algorithme, où le paramètre $k$ désigne le nombre de valeurs $a$ choisies aléatoirement. Par rapport à la question précédente, on fait attention aux points suivants pour l'efficacité :\n",
    "- quand on tire $a$ aléatoirement, il peut arriver que le PGCD de $a$ et $N$ soit $≠1$ : on sait alors que $N$ n'est pas premier, et on répond directement `False` ;\n",
    "- dès qu'on a trouvé un $a$ pour lequel la suite $(b_i)$ ne vérifie pas les conditions, on peut directement répondre `False`, inutile de tirer de nouveaux $a$ ;\n",
    "- de la même façon, il n'est pas forcément nécessaire de calculer toute la suite $(b_i)$, on peut se rendre compte parfois assez vite si elle respecte, ou non, les conditions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "a1e9c606",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "8b382911",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "**4.2.** Tester la fonction sur différents nombres (premiers, composés, Carmichael), avec différentes valeurs de $k$ (entre $1$ et $10$ par exemple). Essayer de répondre aux questions suivantes :\n",
    "* Arrive-t-il à la fonction de se tromper quand $N$ est premier ? et quand $N$ est composé ? et quand il est de type Carmichaël ?\n",
    "* Dans les cas où il arrive que la fonction se trompe, avec quelle probabilité (empirique) cela arrive-t-il ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "18badb5d",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "d1b4c4df",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "bf5850fb",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "id": "db4e8455",
   "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
}