{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8af1dfdb",
   "metadata": {
    "deletable": false,
    "editable": false,
    "run_control": {
     "frozen": true
    }
   },
   "source": [
    "# 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": "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",
    "* Chercher comment générer (avec SageMath) des nombres premiers aléatoires ; de même générer des nombres composés aléatoires en rejetant ceux qui sont premiers (avec la méthode `is_prime`).\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 Carmichaël, dont la liste est fournie ci-dessous. *Les nombres de Carmichaël sont des nombres composés.*\n",
    "\n",
    "```\n",
    "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]\n",
    "```"
   ]
  },
  {
   "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 Carmichaël. 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 Carmichaël. 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 Carmichaël, 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, Carmichaël), 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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}