Pourquoi les nombres premiers sont-ils si intéressants et stupéfiants ?

Réponse publiée sur Quora

La réponse de User-9799112320160419571 est tout à fait correcte, je voudrais juste y ajouter un élément que j’ai découvert au début de cette année seulement [1] :

Les propriétés étonnantes des nombres premiers pourraient ne pas provenir d’eux-mêmes, mais de la notion de Crible mathématique qui les produit.

Il existe en effet d’autres suites de nombres entiers comme les Nombres chanceux qui ont des propriétés très similaires, comme expliqué dans cet article:

Verna Gardiner, R. Lazarus, N. Metropolis and S. Ulam “On Certain Sequences of Integers Defined by Sieves” Mathematics Magazine Vol. 29, No. 3 (Jan. – Feb., 1956), pp. 117-122 DOI 10.2307/3029719 , zbMATH 0071.27002

En passant, l’utilisation des nombres premiers en cryptographie (voir [2] pour une initiation) repose sur le fait qu’il est très rapide de déterminer si un grand nombre est premier ou non[3] , mais très lent de le factoriser s’il ne l’est pas, ce qui revient à déterminer à quel moment le crible élimine ce nombre (il y a des algos plus rapides que le crible “naïf”, mais il faut quand même faire beaucoup d’opérations).

Notes de bas de page

[1] 2019 passée au crible - Pourquoi Comment Combien

[2] Alice et Bob et les clés asymétriques - Pourquoi Comment Combien

[3] Comment trouver des nombres premiers - Pourquoi Comment Combien