J'écris cette fiche en me basant sur cette source.

Dans le cadre de RSA, on veut une clé $N = p_1 \times p_2$ avec $p_1$ et $p_2$ premiers. Pour un niveau de sécurité donné, c'est le nombre de bits de $N$ que l'on veut fixer. On demande par exemple $n = 1024$ bits pour $N$.

Cela signifie que $N$ est dans l'intervalle $[2^{n-1}\,;\,2^n[$.

Pour garantir que $N$ sera dans cet intervalle, on choisit $p_1$ et $p_2$ dans $\left[\sqrt{2}\cdot 2^{\frac{n}{2}-1}\,;\,2^{\frac{n}{2}}\right[$

Par exemple, pour $n = 1024$, on cherche $p_1$ et $p_2$ dans $\left[\sqrt{2}\cdot 2^{511}\,;\,2^{512}\right[$ et on sait qu'on peut en trouver jusque $10^{151}$ donc il y a le choix !

Demandons nous maintenant comment on choisit $p_1$ – idem pour $p_2$.

Voici la procédure :

• on choisit $p$ à la taille voulue, au hasard
  On peut choisir $p$ dans $\left[\sqrt{2}\cdot 2^{n-1}\,;\,2^n\right[$
• on s'assure que $p$ n'est pas divisible par les plus petits nombres premiers. On peut en essayer quelques centaines, voire quelques milliers. On peut facilement garder en mémoire quelques milliers de nombres premiers.
  Si on trouve un diviseur, on essaie un autre $p$.
• on lance des tests de Rabin - Miller.
  Si au moins un de ces tests échoue, on recommence au début.
  Si tous les tests passent, on peut utiliser $p$, on est quasiment certain qu'il est premier.

Des détails sur la page Wikipedia.

C'est une approche probabiliste : trouver un très grand $p$ dont on est certain qu'il est premier demande trop de temps de calcul. On se contente d'être raisonnablement certain que $p$ est premier.

Si $p$ réussit un passage de test Rabin - Miller, la probabilité qu'il soit premier est de 75 %. Autrement dit, le risque qu'il ne soit pas premier est $\frac{1}{4}$.

Si $p$ passe $k$ passage de test, alors la probabilité qu'il ne soit pas premier est de $\frac{1}{4^k}$. Dans les applications commerciales, on se contente de diminuer ce risque à $\frac{1}{2^{128}}$. Il suffit donc de réussir $k = 64$ passages de tests.

On note $a \equiv b [c]$ ou $a \overset{c}{\equiv} b$ si $a \mod c = b$.

Soit $p$ un nombre premier. Le petit théorème de Fermat nous dit que pour $2 \leqslant a < p$, on a $a^{p-1} = 1 [p]$.

On sait aussi que si $X^2 \overset{p}{\equiv} 1$ alors $X \overset{p}{\equiv} 1$ ou $X \overset{p}{\equiv} -1 \overset{p}{\equiv} p - 1$.

L'idée est donc de chercher les racines carrés modulo des $p-1$ et de vérifier que le résultat est toujours $1$ ou $-1$.

Pour cela on détermine $d$ et $s$ tels que $p - 1 = d \times 2^s$, avec $d$ impair. Ainsi, pour un nombre $a$ comme précédemment, $a^{d\times 2^{s-1}}$ est la racine de $a^{d \times 2^s} = a^{p-1}$ et donc $a^{d\times 2^{s-1}} \overset{p}{\equiv} 1 \text{ ou } -1$. Et si c'est $1$ alors on peut poursuivre avec la racine suivante, c'est à dire $a^{d\times 2^{s-2}}$. Et ainsi de suite jusque $a^{d}$.

Donc, soit tous les $a^{d\times 2^{s-i}}$ sont égaux à 1 modulo $p$, soit il y en a qui est égal à $-1$ modulo $p$, c'est à dire à $p-1$.

Tout cela nous permet d'énoncer la propriété suivante.

Pour $p$ donné, dont on veut savoir s'il est premier,

• on cherche $d$ impair et $s$ tels que $p - 1 = d \times 2^s$.
• Un passage de test consiste à :
  • choisir au hasard un nombre $a$ entier dans $[2 ; p[$
  • si $a^{d} \mod p = 1$, on peut arrêter, ce passage de test est validé
  • pour $i$ allant de $0$ à $s-1$, si on trouve $a^{d\times 2^i} \mod p = p - 1$, le test réussit également, pas besoin d'aller plus loin
  • sinon le test échoue, $p$ n'est pas premier.
• Tant que les tests réussissent, on peut recommencer avec un autre $a$ choisit au hasard. On détermine le nombre de tests à faire pour atteindre la probabilité voulue.

• Pour le choix de $p$ au hasard, random.randrange fait l'affaire,
• vous devez constituer une base de quelques milliers de nombres premiers,
• pour le calcul de $a^b \mod p$, vous pouvez utiliser une fonction native de Python : pow(a, b, p).