Probleme – Fabriquer un nombre premier

1. Le test. Il repose sur le petit théorème de Fermat : si $n$ est premier et $1\le a<n$, alors $a^{n-1}\equiv 1(\mathrm{mod}n)$. On teste la contraposée sur $k$ témoins tirés au hasard.

(* Exponentiation modulaire rapide. Precondition : m >= 1, e >= 0.
   Complexite : Theta(log e) multiplications. *)
let rec puiss_mod b e m =
  if e = 0 then 1
  else let r = puiss_mod b (e / 2) m in
       let r2 = r * r mod m in
       if e mod 2 = 0 then r2 else r2 * b mod m

(* Test de primalite de Fermat a k temoins.
   Sortie : false => n est composé A COUP SUR ; true => n est PROBABLEMENT premier.
   Complexite : Theta(k log n). *)
let fermat n k =
  if n < 4 then n = 2 || n = 3
  else if n mod 2 = 0 then false
  else begin
    let probable = ref true in
    for _ = 1 to k do
      let a = 2 + Random.int (n - 3) in
      if puiss_mod a (n - 1) n <> 1 then probable := false
    done;
    !probable
  end

L'erreur est unilatérale : un « faux » est une certitude, un « vrai » est une probabilité. C'est ce qui rend le test exploitable — on ne rejettera jamais un premier.

Mesure sur tous les entiers de $4$ à $100000$, qui contiennent $9590$ nombres premiers :

Aucun faux négatif, jamais : c'est le théorème. Et les faux positifs s'effondrent avec $k$.

2. Les nombres de Carmichael. Un composé $n$ est dit de Carmichael si $a^{n-1}\equiv 1(\mathrm{mod}n)$ pour tout $a$ premier avec $n$. Les plus petits sont $561=3\times 11\times 17$, $1105$ et $1729$. Sur eux, le test ne peut réussir qu'en tombant sur un $a$ partageant un facteur avec $n$ — et la proportion de tels témoins peut être faible. Mesure du taux de témoins « menteurs », c'est-à-dire pour lesquels le test conclut à tort :

Sur $1729$, trois témoins sur quatre mentent : $10$ témoins laissent encore $5,6\%$ d'erreur, et il n'y a aucun $k$ qui rende l'erreur arbitrairement petite indépendamment de $n$ — la proportion de menteurs tend vers $1$ pour des nombres de Carmichael à beaucoup de facteurs.

C'est pourquoi la cryptographie n'emploie pas Fermat mais Miller-Rabin, qui affine le test en exploitant les racines carrées de $1$ modulo $n$, et pour lequel on démontre qu'au plus un quart des témoins mentent, quel que soit le composé. La probabilité d'erreur tombe alors sous $4^{-k}$, sans exception. Miller-Rabin est hors programme ; le fait que Fermat ait un défaut structurel, lui, se mesure.

3. La génération. C'est le schéma Las Vegas pur : tirer, tester, recommencer.

(* Un nombre premier de b bits, avec probabilite d'erreur < 2^-k environ.
   Precondition : b >= 3. TOUJOURS un nombre qui passe le test ;
   le nombre de tirages est aleatoire, d'esperance environ ln(2^b)/2. *)
let premier_de b k =
  let bas = 1 lsl (b - 1) and haut = 1 lsl b in
  let rec tirer essais =
    let x = bas + Random.int (haut - bas) in
    let x = if x mod 2 = 0 then x + 1 else x in     (* on ne tire que des impairs *)
    if x < haut && fermat x k then (x, essais)
    else tirer (essais + 1)
  in
  tirer 1

Terminaison : elle n'est pas garantie au sens strict — c'est la définition même d'un Las Vegas. Elle est presque sûre : chaque tirage réussit avec une probabilité $p>0$ fixe, donc la probabilité de ne jamais réussir est $\lim (1-p{)}^k=0$. Le nombre de tirages suit une loi géométrique d'espérance $1/p$.

Le calcul de $p$. Le théorème des nombres premiers donne $\pi (x)\sim x/\ln x$ : la densité des premiers autour de $2^b$ vaut environ $1/\ln (2^b)=1/(b\ln 2)$. En ne tirant que des impairs, on double cette densité, d'où

$$\mathbb{E}[\text{tirages}]\approx \frac{b\ln 2}{2}.$$

Mesure sur $3000$ générations :

4. À $2048$ bits, la formule donne $2048\times \ln 2/2\approx 710$ tirages, ce qui est le chiffre annoncé par le chapitre. Chaque tirage coûte $k$ exponentiations modulaires sur $2048$ bits ; l'ensemble prend une fraction de seconde sur une machine ordinaire. C'est ainsi que sont fabriquées les clés RSA.

Et l'on mesure ce que le hasard apporte ici. Aucun procédé déterministe connu ne construit un premier de $2048$ bits : on ne sait pas écrire de formule, et énumérer les impairs à partir d'un point donné n'offre aucune garantie de temps. Le hasard n'est pas un pis-aller ; c'est le seul procédé connu, et il est efficace. L'aléa sert ici à construire, pas à accélérer — c'est la distinction que le chapitre place au cœur de Las Vegas.