Comment un ordinateur trouve-t-il en une fraction de seconde un nombre premier de 300 chiffres ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

RSA demande deux nombres premiers d'environ 300 chiffres, et chaque connexion sécurisée en génère parfois. J'avais appris qu'il est très long de factoriser un grand nombre ; je pensais donc qu'il serait aussi très long de vérifier qu'un nombre est premier. Ce n'est pas le cas, et j'ai voulu comprendre pourquoi, en mêlant logarithme, loi géométrique et algorithmique.

L'enjeu et les notions du programme

Estimer une fréquence par le logarithme, puis calculer le nombre moyen d'essais avec une loi géométrique.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Pour créer une clé RSA, il faut deux grands nombres premiers secrets. Problématique : les nombres premiers sont-ils assez nombreux pour qu'on en trouve vite, et comment reconnaître un nombre premier sans le factoriser ?

2. 2. Mathématiques : combien de premiers, combien d'essais

   4 min

   Le théorème des nombres premiers (admis) dit qu'au voisinage de $N$N, la proportion de nombres premiers est environ $\frac{1}{\ln N}$1/(ln N). Pour $N=2^{1024}$N=2¹⁰²⁴ (environ 309 chiffres), $\ln N=1024\ln 2\approx 710$ln N=1024ln2≈710. Un nombre sur 710 est premier ; comme on ne tire que des impairs, la proportion double : environ un sur 355.

   Si l'on tire des impairs au hasard, indépendamment, le rang du premier nombre premier suit une loi géométrique de paramètre $p\approx \frac{1}{355}$p≈1/355. Son espérance est $\frac{1}{p}\approx 355$1/p≈355 essais. La probabilité d'échouer 1 000 fois de suite est ${\left(1-\frac{1}{355}\right)}^{1000}\approx e^{-2,8}\approx 0,06$(1-1/355)¹⁰⁰⁰≈ e^(-2,8)≈0,06.

   Il y a beaucoup de nombres premiers de cette taille : environ $\frac{2^{1024}}{710}$2¹⁰²⁴/710, un nombre à plus de 300 chiffres. Deux personnes n'ont pratiquement aucune chance de tirer le même.

3. 3. NSI : tester sans factoriser

   3 min

   Tester un nombre de 309 chiffres en essayant les diviseurs jusqu'à sa racine carrée demanderait environ $10^{154}$10¹⁵⁴ divisions. Les tests probabilistes (Fermat, Miller-Rabin) calculent plutôt une puissance par exponentiation rapide : si $a^{N-1}$a^(N-1) ne laisse pas le reste 1 modulo $N$N, alors $N$N n'est sûrement pas premier.

   Un nombre qui passe le test pour un $a$a peut encore être composé, mais pour Miller-Rabin la probabilité d'erreur est au plus $\frac{1}{4}$1/4 par essai : après 40 essais, elle est inférieure à $4^{-40}\approx 10^{-24}$4⁻⁴⁰≈10⁻²⁴. On accepte ce risque minuscule en échange d'un test très rapide.

4. 4. Conclusion

   1,5 min

   Trouver un grand nombre premier est rapide : ils sont assez fréquents (un impair sur 355 vers $2^{1024}$2¹⁰²⁴), et on les reconnaît par un test probabiliste sans les factoriser. Vérifier qu'un nombre est premier est facile, le factoriser est difficile : c'est cet écart qui rend RSA possible.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Croire que tester la primalité exige de factoriser.
• Utiliser log₁₀ au lieu de ln dans la densité.
• Oublier que le test probabiliste a une petite probabilité d'erreur.

Revoir les notions

• Fonction logarithme népérien (Terminale spé maths) →
• Variables aléatoires (lois) (Terminale spé maths) →

Autres questions : cryptographie et sécurité

• Comment peut-on chiffrer un message avec une clé que tout le monde connaît ?
• Deux personnes peuvent-elles fabriquer un secret commun en ne s'échangeant que des messages publics ?
• Pourquoi une clé de 128 bits est-elle considérée comme incassable par force brute ?
• Combien de fichiers faut-il pour que deux d'entre eux aient la même empreinte numérique ?

Toutes les questions maths-nsi →