Ceci est une traduction automatique dont le texte original est en anglais. Consulter l'original
Les nombres premiers se raréfient à un rythme que l'on peut nommer
Au voisinage d'un nombre de 1024 bits, un nombre impair sur 355 est premier. Ce n'est pas une faible probabilité, et c'est la seule raison pour laquelle la cryptographie à clé publique est possible.
Il y a 25 nombres premiers inférieurs à 100, 168 inférieurs à 1000 et 78 498 inférieurs à un million. Les décomptes diminuent, mais ils ne s'arrêtent jamais, et le rythme auquel ils se raréfient est l'un des faits les plus utiles des mathématiques.
Un sur ln n
Au voisinage d'un nombre n, environ un nombre sur ln n est premier. En dessous de 100, cela prédit 100 / ln 100 = 21,7 nombres premiers, et Prime Sieve affiche exactement cela à côté du décompte réel de 25, ainsi que l'erreur de 13,1 %.
L'estimation est ici grossière et s'améliore. À un million, N / ln N donne 72 382 contre les 78 498 réels, soit une erreur de 7,8 %. L'erreur relative diminue à mesure que N grandit, ce qui constitue le contenu réel du théorème des nombres premiers.
La meilleure estimation qui paraît moins bonne
L'outil affiche une seconde approximation, Li(N), le logarithme intégral. Pour N = 100, elle donne 29,1 et s'avère pire que l'estimation grossière : une erreur de 16,3 % contre 13,1 %.
Quiconque ne lirait que cette ligne conclurait que la formule la plus élaborée ne vaut pas la peine d'être utilisée. Modifiez N, et le classement s'inverse pour ne plus jamais revenir en arrière :
- N = 100 : N/lnN erreur de 13,1 %, Li de 16,3 %
- N = 1000 : N/lnN erreur de 13,8 %, Li de 5,1 %
- N = 10⁶ : N/lnN erreur de 7,8 %, Li de 0,16 %
Li n'est pas tant un affinement de N / ln N que sa version authentique. La formule grossière applique la densité en n à l'ensemble de l'intervalle de 0 à n, alors que la densité au voisinage de 2 est très différente de la densité au voisinage d'un million. Li intègre 1/ln t sur tout l'intervalle au lieu de la supposer constante, et le résultat est une erreur d'une partie sur six cents là où le raccourci se trompe encore de 8 %.
Une seule évaluation d'une approximation ne dit rien sur sa qualité. Il faut observer son comportement lorsque la valeur d'entrée augmente.
Pourquoi ils ne s'épuisent jamais
Parce que 1/ln n décroît lentement. Sa somme diverge, ainsi les nombres premiers se raréfient, mais pas au point d'être en nombre fini.
La démonstration d'Euclide est plus directe et plus ancienne. Prenez une liste finie quelconque de nombres premiers, multipliez-les entre eux, ajoutez un. Le résultat donne un reste de 1 lorsqu'il est divisé par n'importe quel nombre premier de la liste ; ses facteurs premiers sont donc tous absents de votre liste. Aucune liste finie ne peut être complète.
Les deux autres indications de l'outil montrent tout ce qui reste ouvert. Il compte 8 paires de jumeaux en dessous de 100 et indique un écart maximal de 8. La question de savoir si les paires de jumeaux se poursuivent à l'infini n'est pas prouvée, tout comme la conjecture selon laquelle un nombre premier se trouve toujours entre deux carrés consécutifs.
Le nombre qui dimensionne une clé
Générer une clé RSA consiste à trouver de grands nombres premiers, et la méthode consiste à choisir au hasard un nombre impair de la taille souhaitée et à le tester.
Le temps que cela prend relève exactement de la question de la densité. Un nombre de 1024 bits est proche de 2¹⁰²⁴, et ln(2¹⁰²⁴) = 1024 × ln 2 = 710. Ainsi, environ un nombre sur 710 dans ce voisinage est premier, et comme vous ne testez que des candidats impairs, un sur 355.
Trois cent cinquante-cinq essais, chacun étant un test rapide de primalité probabiliste. C'est pourquoi la génération de clés prend un instant plutôt qu'une ère géologique, et tout ce calendrier découle d'un logarithme. Augmentez l'exposant et le coût croît de manière linéaire avec la longueur en bits, c'est pourquoi les clés de 2048 bits et 4096 bits restent pratiquement réalisables.
Si les nombres premiers s'étaient raréfiés ne serait-ce qu'un peu plus vite, par exemple en 1/n, la recherche serait sans espoir et Internet reposerait sur autre chose.
Personne ne prouve les nombres premiers qu'il utilise
Un détail rend les 355 essais peu coûteux : le test n'établit pas la primalité.
Miller-Rabin choisit un témoin aléatoire et pose une question à laquelle chaque nombre premier répond d'une seule et même manière. Un nombre composé peut répondre comme un nombre premier, mais au maximum un quart des témoins possibles le lui permettront, de sorte que chaque tour indépendant réduit le risque d'être trompé d'au moins un facteur quatre. Quarante tours laissent un pire cas inférieur à 4⁻⁴⁰, ce qui équivaut environ à 10⁻²⁴.
C'est bien en dessous de la probabilité d'une erreur mémoire non détectée dans la machine qui effectue le calcul. Les clés qui protègent le trafic mondial reposent sur des nombres qui sont presque certainement premiers, et le doute résiduel est plus faible que celui lié au matériel.