Nombre premier

L'esprit ludique et l'émulation ont amené des mathématiciens à définir des seuils de gigantisme pour les nombres premiers, exprimés en nombre de chiffres en base dix. Parmi ces records, battus ou à battre, on notera en particulier :

• les nombres premiers titanesques (titanic primes), au-delà de mille chiffres,
• les nombres premiers gigantesques (gigantic primes), au-delà de dix mille chiffres,
• les méga-nombres premiers (megaprimes), au-delà d'un million de chiffres.

En 2021, plus de mille méga-nombres premiers étaient connus[6]. Le premier à être découvert fut, en 1999, le nombre de Mersenne 2^6 972 593 − 1 avec ses 2 098 960 chiffres[7] - [8], grâce aux efforts du projet collaboratif de calcul distribué Great Internet Mersenne Prime Search (GIMPS).

L'Electronic Frontier Foundation offre des prix de calcul coopératif pour encourager les internautes à contribuer à la résolution de problèmes scientifiques par le calcul distribué. Le GIMPS a ainsi reçu 100 000 dollars pour sa découverte en 2008 du premier nombre premier d'au moins dix millions de chiffres décimaux. L'EFF offre encore 150 000 et 250 000 dollars respectivement pour la découverte du premier nombre premier de cent millions et un milliard de chiffres décimaux[9].

Le record du plus grand nombre premier connu a presque toujours été trouvé parmi les nombres de Mersenne, comme le dernier en date, M_82589933 = 2^82 589 933 – 1, un nombre découvert le 7 décembre 2018, ayant 24 862 048 chiffres décimaux.

Découvrir un nombre premier plus grand que tous ceux déjà connus n'implique pas de connaître tous les nombres premiers intermédiaires.

Plus généralement, la recherche de tous les nombres premiers inférieurs à un nombre donné (premier ou non) constitue un défi mathématique spécifique.

Date	Seuil s	Quantité π(s)(*)	Vérificateurs	Méthode
Antiquité	1 000	168	Ératosthène, Euclide[10]	Essais par division[10]
1746[10]	100 000	9 592	?
1797[10]	400 000	33 860
1811[10]	1 000 000	78 498
1863[10]	100 000 000	5 761 455	Jakob Philipp Kulik (de)[10] - [11]
2010[12]	276 = 75 557 863 725 914 323 419 136	1 462 626 667 154 509 638 735	Jens Franke et al.[12]	Évaluation directe de ${\displaystyle \pi (s)}$[12]
	277 = 151 115 727 451 828 646 838 272	2 886 507 381 056 867 953 916
	1024 ≈ 1 000 000 000 000 000 000 000 000	18 435 599 767 349 200 867 866

Notes :
^(*) π(s) est la quantité totale de nombres premiers situés sous le seuil s (c'est-à-dire dans l'intervalle d'entiers ${\displaystyle [\![0,s]\!]}$). La connaissance de π(s) par un calcul algorithmique n'implique pas nécessairement que chacun des nombres premiers soit immédiatement identifiable. La décomposition en facteurs permet au contraire d'identifier les nombres premiers individuellement, mais elle est impraticable pour des nombres supérieurs à 10⁴⁰ ; au-delà de cette valeur, on dispose de tests de primalité rapides.

On appelle parfois nombre premier « de Pythagore » tout nombre premier de la forme 4n + 1, où n est un entier naturel. Par exemple, le nombre premier 5 est de Pythagore. Un nombre premier impair est de Pythagore si et seulement s'il est somme de deux carrés.

Marin Mersenne.

Les nombres premiers de la forme : ${\displaystyle M_{p}=2^{p}-1}$ où p est alors nécessairement aussi premier, sont appelés nombres premiers de Mersenne. Les grands nombres premiers sont souvent recherchés sous cette forme car il existe un test efficace, le test de primalité de Lucas-Lehmer, pour déterminer si un tel nombre est premier ou non.

Entre 2008 et 2012, le plus grand nombre premier connu était M_43 112 609 = 2^43 112 609 – 1, qui comporte 12 978 189 chiffres en écriture décimale. Il s'agit (chronologiquement) du 45^e nombre premier de Mersenne connu et sa découverte a été annoncée le 23 août 2008 par le GIMPS. Un 46^e nombre premier de Mersenne, 2^37 156 667 – 1, inférieur au précédent, a été découvert deux semaines plus tard ; le 12 avril 2009 était découvert, par le même projet GIMPS, un 47^e nombre premier de Mersenne, 2^42 643 801 – 1, lui aussi inférieur au premier cité.

Ce record a été battu (toujours par le GIMPS) par la preuve de la primalité de M_57 885 161 = 2^57 885 161 – 1 (en janvier 2013) puis à nouveau, le 7 janvier 2016, par celle de M_74 207 281, le 3 janvier 2018, par celle de M_77 232 917, et enfin, le 7 décembre 2018, par celle de M_82 589 933.

Pierre de Fermat.

Les nombres de la forme : ${\displaystyle F_{n}=2^{2^{n}}+1}$ sont appelés les nombres de Fermat. Fermat avait conjecturé que tous ces nombres étaient premiers[15]. Cependant, les seuls nombres de Fermat premiers connus sont

${\displaystyle F_{0}=3}$, ${\displaystyle F_{1}=5}$, ${\displaystyle F_{2}=17}$, ${\displaystyle F_{3}=257}$ et ${\displaystyle F_{4}=65\,537}$.

Le nombre de Fermat F₅ est seulement semi-premier. Il est divisible par 641.

Il s'agit du premier contre-exemple à cette conjecture de Fermat, découvert par Euler[16] en 1732. Tous les autres nombres de Fermat calculés depuis sont composés, au point que l'objectif s'est transformé en la recherche effrénée d'un autre nombre de Fermat premier.

Deux nombres premiers sont dits jumeaux s'ils ne diffèrent que de 2. Les trois plus petits couples de nombres premiers jumeaux sont (3, 5), (5, 7) et (11, 13). Le plus grand connu est 2 996 863 034 895 × 2^21 290 000 ± 1 ; les deux nombres possèdent 388 342 chiffres (septembre 2016).

Il est conjecturé qu'il existe une infinité de nombres premiers jumeaux.

Un nombre premier G est un nombre premier de Sophie Germain si 2G + 1 est aussi un nombre premier, appelé nombre premier sûr.

Les dix premiers nombres premiers de Sophie Germain sont 2, 3, 5, 11, 23, 29, 41, 53, 83, 89.

Il est conjecturé qu'il existe une infinité de nombres premiers de Sophie Germain.

Un nombre premier brésilien p est un nombre premier qui est répunit avec un nombre premier impair de 1 dans une base b ; la réciproque est fausse comme le montrent 57 = 111₇ = 3 × 19 ou encore 121 = 11111₃ = 11 x 11.

Le plus petit nombre premier brésilien est 7 = 111₂ ; 43 = 111₆ et 127 = 1111111₂ sont d'autres exemples.

La suite des nombres premiers brésiliens commence par 7, 13, 31, 43, 73, 127, 157, 211, 241, 307, 421, 463 , etc. (suite A085104 de l'OEIS).

Seuls deux nombres premiers brésiliens sont connus pour être brésiliens dans deux bases différentes, ce sont les deux nombres de la conjecture de Goormaghtigh: 31 = 11111₂ = 111₅ et 8191 = 1111111111111₂ = 111₉₀.

On conjecture qu'il existe une infinité de nombres premiers brésiliens, mais, alors que la série des inverses des nombres premiers est divergente, la série des inverses des nombres premiers brésiliens est convergente vers un nombre, appelé « constante des nombres premiers brésiliens », légèrement supérieure à 0,33 et qui est étudiée dans la séquence  A306759.

Tout nombre premier de Mersenne supérieur ou égal à 7 est brésilien par définition. Par exemple, ${\displaystyle M_{5}=2^{5}-1=31=11111_{2}}$.

Par contre, tout nombre de Fermat ${\displaystyle F_{n}=2^{2^{n}}+1}$ premier est non brésilien[17].

Les plus petits nombres des couples de nombres premiers jumeaux qui sont brésiliens sont plutôt rares (ils figurent dans la suite  A306849), et plus généralement, les nombres premiers brésiliens sont relativement rares ; ainsi, sur les premiers 10¹² entiers naturels, il existe 37 607 912 018 nombres premiers dont seulement 88 285 sont des premiers brésiliens.

Les premiers algorithmes pour décider si un nombre est premier (appelés tests de primalité) consistent à essayer de le diviser par tous les nombres qui n'excèdent pas sa racine carrée : s'il est divisible par l'un d'entre eux, il est composé, et sinon, il est premier. Cependant, l'algorithme dérivant de cette formulation peut être rendu plus efficace : il suggère beaucoup de divisions inutiles, par exemple, si un nombre n'est pas divisible par 2, il est inutile de tester s'il est divisible par 4. En fait, il suffit de tester sa divisibilité par tous les nombres premiers n'excédant pas sa racine carrée.

Le crible d'Ératosthène est une méthode, reposant sur cette idée, qui fournit la liste des nombres premiers inférieurs à une valeur fixée n (n = 120 dans l'animation ci-contre) :

• on forme la liste des entiers de 2 à n ;
• on retient comme « nombre premier » le premier nombre de la liste non encore barré (le premier dans ce cas est 2) ;
• on barre tous les entiers multiples du nombre retenu à l'étape précédente, en commençant par son carré (puisque 2 × i, 3 × i, … , (i – 1) × i ont déjà été barrés en tant que multiples de 2, 3, ...) ;
• on répète les deux dernières opérations (c'est-à-dire : on retient le prochain nombre non barré et on barre ses multiples) ;
• dès qu'on en est à chercher les multiples des nombres excédant la racine carrée de n, on termine l'algorithme.

Ainsi les nombres premiers inférieurs à n sont les nombres qui restent non barrés à la fin du processus. Cet algorithme est de complexité algorithmique exponentielle.

Le crible d'Ératosthène fournit donc plus d'information que la seule primalité de n. Si seule cette information est souhaitée, une variante parfois plus efficace consiste à ne tester la divisibilité de n que par des petits nombres premiers dans une liste fixée au préalable (par exemple 2, 3 et 5), puis par tous les nombres entiers inférieurs à la racine carrée de n qui ne sont divisibles par aucun des petits nombres premiers choisis ; cela amène à tester la divisibilité par des nombres non premiers (par exemple 49 si les petits premiers sont 2, 3 et 5 et que n excède 2500), mais un choix d'un nombre suffisant de petits nombres premiers doit permettre de contrôler le nombre de tests inutiles effectués[18].

Le crible d'Ératosthène : nombres premiers inférieurs à 120.

Une variante du crible d'Ératosthène est le crible de Sundaram qui consiste à former les produits de nombres impairs. Les nombres qui ne sont pas atteints par cette méthode sont les nombres premiers impairs, c'est-à-dire tous les nombres premiers sauf 2. Par ailleurs, à partir du crible d'Ératosthène, la factorisation de l'entier n peut facilement être trouvée. D'autres méthodes plus générales concernant ce problème plus difficile que simplement déterminer la primalité sont aussi appelées méthodes de crible, la plus efficace étant actuellement le crible général des corps de nombres[19].

Les algorithmes présentés précédemment ont une complexité trop importante pour pouvoir être menés à terme, même avec les ordinateurs les plus puissants, quand n devient grand.

Une autre classe d'algorithme consiste à tester l'entier n pour une famille de propriétés vérifiées par les nombres premiers : si une propriété de cette famille n'est pas vérifiée pour n, alors il est composé ; en revanche, le fait qu'une des propriétés de la famille soit vérifiée pour n ne suffit pas à assurer la primalité. Toutefois, si cette famille est telle qu'un nombre composé ne vérifie pas au moins la moitié des propriétés en jeu, alors l'utilisateur peut estimer qu'un nombre n qui vérifie k propriétés de la famille est premier avec une probabilité supérieure à 1 – 2^–k : il est déclaré probablement premier à partir d'une valeur de k à choisir par l'utilisateur ; un nombre déclaré probablement premier, mais qui n'est pas premier est appelé nombre pseudo-premier. Un test basé sur ce principe est appelé test probabiliste de primalité. De tels tests reposent souvent sur le petit théorème de Fermat, amenant au test de primalité de Fermat, et à ses raffinements : le test de primalité de Solovay-Strassen et celui de Miller-Rabin, qui sont des améliorations, car ils admettent moins de nombres pseudo-premiers[20] - [21].

L'algorithme AKS mis au point en 2002 permet de déterminer (avec certitude) si un nombre donné N est premier en utilisant un temps de calcul polynomial.

Euclide a démontré dans ses Éléments (proposition 20 du Livre IX) que les nombres premiers sont en plus grande quantité que toute quantité proposée de nombres premiers. Autrement dit, il existe une infinité de nombres premiers. La démonstration d'Euclide repose sur la constatation qu'une famille finie p₁,...,p_n de nombres premiers étant donnée, tout nombre premier divisant le produit des éléments de cette famille augmenté de 1 est en dehors de cette famille (et un tel diviseur existe, ce qui est aussi prouvé par Euclide)[25].

D'autres démonstrations de l'infinité des nombres premiers ont été données. La preuve d'Euler[26] utilise l'identité :

${\displaystyle \sum _{n=1}^{\infty }\ {\frac {1}{n}}\ =\ \prod _{p\in {\mathcal {P}}}\ {\frac {1}{1-{\frac {1}{p}}}}}$.

Dans la formule précédente, le terme de gauche est la somme de la série harmonique, qui est divergente. Par conséquent, le produit de droite doit contenir une infinité de facteurs.

Furstenberg fournit une preuve utilisant une argumentation topologique[27].

Le premier résultat sur le comportement des nombres premiers à l’infini est dû à Euler :

Comme la série des inverses de tous les entiers est également divergente, cela indique intuitivement que, si les nombres premiers se raréfient à l’infini, ils ne se raréfient pas très vite[28].

Par ailleurs, le résultat sur l'infinité des nombres premiers amène à se demander combien il y a de nombres premiers jusqu’à un nombre donné et à étudier la fonction correspondante. Pour cela, on désigne, pour tout nombre premier ${\displaystyle p,}$ son rang dans la suite croissante des nombres premiers, comme indiqué dans le tableau suivant pour les 25 nombres premiers inférieurs à 100 :

Les 25 nombres premiers inférieurs à 100	${\displaystyle p}$ :		2,	3,	5,	7,	11,	13,	17,	19,	23,	29,	31,	37,	41,	43,	47,	53,	59,	61,	67,	71,	73,	79,	83,	89,	97.
Rang	${\displaystyle \pi (p)}$ :		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Pour ${\displaystyle x}$ une variable réelle, ${\displaystyle \pi (x)}$ est définie comme le nombre de nombres premiers ${\displaystyle \leq x.}$ Cette fonction réelle à valeurs entières est appelée fonction de compte des nombres premiers. C’est une fonction en escalier, constante entre deux nombres premiers successifs : ${\displaystyle \pi (x)}$ est égal à ${\displaystyle \pi (q)}$, ${\displaystyle q}$ étant le plus grand nombre premier ${\displaystyle \leq x.}$

Restreinte au domaine de définition ${\displaystyle \mathbb {P} }$, la fonction ${\displaystyle \pi }$ a une fonction réciproque, généralement notée ${\displaystyle p_{n}}$, qui représente le n-^ième nombre premier, par exemple ${\displaystyle p_{16}=53}$.

La fonction ${\displaystyle \pi (x)}$ est croissante et tend vers l’infini[25]. C’est une conséquence triviale du théorème de l’infinité des nombres premiers (voir section précédente).

Le premier résultat important sur ${\displaystyle \pi (x)}$ est obtenu par Legendre :

Vers la fin du XVIII^e siècle, Legendre (1797) et Gauss (1792) conjecturent que la fonction de compte des nombres premiers ${\displaystyle \pi (x)}$ est équivalente à la fonction ${\displaystyle {\frac {x}{\ln(x)}}}$ quand ${\displaystyle x}$ tend vers l'infini. Dit autrement, la proportion de nombres premiers parmi les nombres inférieurs à ${\displaystyle x,}$ c’est-à-dire ${\displaystyle {\frac {\pi (x)}{x}},}$ tend vers 0 à la vitesse de ${\displaystyle {\frac {1}{\ln x}}}$.

On peut apprécier la pertinence de cette conjecture en examinant le tableau des valeurs de ${\displaystyle {\frac {\pi (x)}{x}}}$ et de ${\displaystyle {\frac {\pi (x)}{\frac {x}{\ln(x)}}}}$ pour les valeurs de ${\displaystyle x}$ égales aux premières puissances entières de 10 :

${\displaystyle m}$	${\displaystyle \pi (m)}$	${\displaystyle {\frac {\pi (m)}{m}}}$	${\displaystyle {\frac {\pi (m)}{\frac {m}{\ln(m)}}}}$
10	4	0,400	0,921
100	25	0,250	1,151
1 000	168	0,168	1,161
10 000	1 229	0,123	1,132
100 000	9 592	0,096	1,104
…	…	…	…
${\displaystyle \rightarrow \,\infty }$	${\displaystyle \rightarrow \,\infty }$ (Euclide)	${\displaystyle \rightarrow }$ 0 (Legendre)	${\displaystyle \rightarrow }$ 1 (conjecture)

Il faudra tout le XIX^e siècle pour que la conjecture soit démontrée (voir section suivante).

Une première avancée vers la démonstration de la conjecture de Legendre-Gauss [29] est obtenue par Tchebychev à partir de 1848 :

Théorème de Tchebychev — Il existe deux constantes C et D telles qu'on ait l'encadrement, pour x assez grand :

${\displaystyle \mathrm {C} \leq {\frac {\pi (x)}{\frac {x}{\ln x}}}\leq \mathrm {D} ,}$ (inégalités de Tchebychev),

la conjecture de Legendre-Gauss consistant à affirmer la validité de l’énoncé pour n’importe quel ${\displaystyle \mathrm {C} <1}$ et n’importe quel ${\displaystyle \mathrm {D} >1.}$

Il démontre également le théorème suivant sur la raréfaction des nombres premiers :

Théorème de Tchebychev — Si ${\displaystyle {\frac {\pi (x)}{\frac {x}{\ln x}}}}$ a une limite quand ${\displaystyle x\rightarrow \infty ,}$ cette limite vaut 1.

Comme conséquence des inégalités ci-dessus, Tchebychev peut aussi démontrer le postulat de Bertrand selon lequel dans tout intervalle d'entiers naturels, entre un entier et son double existe au moins un nombre premier[30].

Une nouvelle avancée est due à Riemann dans un article célèbre en 1859 : il étend le domaine de définition de la fonction ${\displaystyle \zeta (s)}$ au plan complexe privé du nombre ${\displaystyle s=1}$ ; il formule sa célèbre hypothèse, selon laquelle les zéros de ${\displaystyle \zeta (s)}$ situés dans la bande ${\displaystyle 0\,\,<\operatorname {Re} (s)\,<\,1}$ ont pour partie réelle ${\displaystyle {\frac {1}{2}}\,;}$ son approche constitue une impulsion décisive au développement de la théorie analytique des nombres, source de nombreuses avancées en théorie des nombres.

À la fin du siècle, la conjecture de Legendre et Gauss est démontrée indépendamment par Jacques Hadamard et Charles-Jean de La Vallée Poussin[31], et porte depuis lors le nom de théorème des nombres premiers. La démonstration s’appuie sur l’observation qu’il suffit de s’assurer que la fonction ${\displaystyle \zeta }$ ne s'annule pas dans le demi-plan de partie réelle ${\displaystyle \geq 1}$ et de trouver un domaine qui englobe ce demi-plan dans lequel c’est le cas.

Les démonstrations utilisent des outils puissants d'analyse complexe pour démontrer un énoncé d'arithmétique et d'analyse réelle. Une stratégie pour ces démonstrations est l'étude de la fonction zêta de Riemann sur un domaine du plan complexe plus grand qu'un simple voisinage de z=1 : il est nécessaire de la contrôler, c'est-à-dire de majorer son module, au voisinage de la droite verticale des nombres de partie réelle égale à 1[32]. La puissance des outils d'analyse complexe utilisés pour résoudre le théorème des nombres premiers conduit à un développement important d'une branche entière des mathématiques, la théorie analytique des nombres, dans laquelle l'étude de la fonction zêta de Riemann devient un thème central. En particulier l'hypothèse de Riemann, encore non démontrée, sur la localisation de ses zéros, aurait des conséquences fortes sur le comportement de la fonction de compte des nombres premiers.

Sur la base des résultats de Riemann (article de 1859), on peut déduire l'estimation :

où ${\displaystyle {\rm {li}}(x)=\int _{0}^{x}{\frac {\mathrm {d} t}{\ln(t)}}}$ (Riemann note cette fonction ${\displaystyle {\rm {Li}}(x)}$) et où ${\displaystyle f=O(g)}$ signifie qu’il existe une constante ${\displaystyle \mathrm {C} >0}$ telle que ${\displaystyle |f(x)|\leq \mathrm {C} g(x)}$ pour tout ${\displaystyle x}$ assez grand.

Les résultats sur la fonction de compte des nombres premiers permettent d'obtenir des résultats sur le n-ième nombre premier. Par exemple, comme conséquences directes des théorèmes de Tchebychev, Ishikawa établit en 1934 des propriétés de la fonction n-ième nombre premier, désignée par ${\displaystyle p_{n}}$ :

${\displaystyle p_{n}+p_{n+1}>p_{n+2},\qquad p_{n}p_{m}>p_{n+m}.}$

Ou encore, d'après un résultat de Felgner de 1990[33] :

${\displaystyle 0,91\ n\ \ln(n)\ <\ p_{n}\ <\ 1,7\ n\ \ln(n).}$

Des démonstrations élémentaires du théorème des nombres premiers sont trouvées. Par élémentaires, il faut entendre qu’elles ne recourent pas à l'analyse complexe. C’est le cas notamment d’Erdős et de Selberg[31].

En 1838, en reprenant l’étude d’Euler, au moyen d'un outil appelé caractère de Dirichlet, et en utilisant à la place de la fonction zêta de Riemann des fonctions analogues appelées fonction L de Dirichlet, Dirichlet est capable d'adapter la démonstration au cas des nombres premiers dans des progressions arithmétiques : si a et b sont premiers entre eux, alors il existe une infinité de nombres premiers de la forme aq+b. Utilisant les techniques de Hadamard, La Vallée Poussin démontre ensuite une version quantitative du théorème; les nombres premiers sont équirépartis entre les différentes progressions arithmétiques de raison a (c'est-à-dire avec a fixé, et b variant parmi les divers restes inversibles dans la division euclidienne par a)[34] - [35] : le nombre de nombres premiers inférieurs ou égaux à x, dans la suite aq +b, est donc équivalent à x/(ln(x)φ(a)), où φ est l'indicatrice d'Euler. Bien que cela montre qu'il y a, par exemple, « autant » de nombres premiers de la forme 3n +1 que de la forme 3n+2, les seconds semblent expérimentalement moins nombreux ; c'est le biais de Tchevychev, dont une démonstration rigoureuse dans tous les cas n'est pas encore connu en 2020.

Le théorème de Green-Tao, démontré en 2004 par Ben Joseph Green et Terence Tao, généralise notamment le théorème de Dirichlet en assurant que pour tout entier k, il existe une infinité de suites de k nombres premiers en progression arithmétique, c'est-à-dire de la forme :

${\displaystyle a,\,a+b,\,a+2b,\,\dots ,\,a+(k-1)b}$.

Le théorème de Green-Tao est en fait bien plus fort que cet énoncé seul : par exemple, il établit qu'une telle progression arithmétique existe, avec des entiers tous plus petits que :

${\displaystyle 2^{2^{2^{2^{2^{2^{2^{100k}}}}}}}}$

(expérimentalement, cette borne semble plutôt devoir être de l'ordre de k!). Il assure également que pour tout entier k et tout réel ${\displaystyle \delta }$ strictement positif, pour tout x suffisamment grand, si P est un ensemble de nombres premiers inférieurs à x contenant au moins ${\displaystyle \delta \pi (x)}$ éléments, alors P contient au moins une progression arithmétique de nombres premiers comptant k termes.

De nombreux résultats et conjectures sur la répartition des nombres premiers sont contenus dans la conjecture générale suivante. Soit f₁,...,f_k des polynômes non constants, irréductibles et vérifiant la propriété que pour tout nombre premier p il y ait au moins un entier n parmi 0, ..., p – 1 tel que p ne divise pas le produit des f_i(n). On note ${\displaystyle \omega (p)}$ le complémentaire à p du nombre de tels entiers. Un tel ensemble de polynômes est dit admissible ; on cherche à connaître la proportion d'entiers en lesquels les polynômes prennent simultanément des valeurs premières, et se limiter à des ensembles de polynômes admissibles permet d'éviter des cas triviaux comme f₁(t)=t, et f₂(t)=t+1. Il est alors conjecturé que le nombre d'entiers n plus petits qu'un réel x tels que les valeurs f₁(n),...,f_k(n) sont simultanément premières, est, pour x assez grand, de l'ordre de :

${\displaystyle \left(\prod _{p}{\frac {1-{\frac {\omega (p)}{p}}}{\left(1-{\frac {1}{p}}\right)^{k}}}\right){\frac {x}{\log |f_{1}(x)|\dots \log |f_{k}(x)|}}}$.

Le théorème des nombres premiers correspond au cas k = 1 et f_t = t, le théorème de Dirichlet à k = 1 et f_t = at + b, et pour k = 2, f₁(t) = t et f₂(t) = t + 2, on obtient une version quantitative (et donc plus générale) de la conjecture des nombres premiers jumeaux.

Jusque dans les années 1970, les systèmes de chiffrement connus étaient basés sur le principe de la cryptographie symétrique, où une même clé (secrète) est utilisée pour chiffrer et déchiffrer un message. En 1978, Ronald Rivest, Adi Shamir et Leonard Adleman décrivent le premier système public de cryptographie asymétrique (nommé d'après leurs initiales RSA), basé sur les propriétés des nombres premiers et de la factorisation. Dans un tel système, deux clés sont utilisées : l'une sert à chiffrer, l'autre à déchiffrer. La clé permettant de chiffrer est accompagnée d'un grand nombre entier, le produit de deux grands nombres premiers gardés secrets (de l'ordre de 200 chiffres). Pour calculer la clé de déchiffrement, la seule méthode connue nécessite de connaître les deux facteurs premiers. La sécurité du système est basée sur le fait qu'il est facile de trouver deux grands nombres premiers (en utilisant des tests de primalité) et de les multiplier entre eux, mais qu'il serait difficile pour un attaquant de retrouver ces deux nombres. Ce système permet également de créer des signatures numériques, et a révolutionné le monde de la cryptographie.

• [Cohen 1993] (en) Henri Cohen, A Course in Computational Algebraic Number Theory, 1993 [détail des éditions] — Référence moderne sur les méthodes effectives en théorie des nombres.
• [Ellison et Mendès France 1975] William John Ellison et Michel Mendès France, Les Nombres premiers, 1975 [détail de l’édition] — Livre très clair, comme introduction à la théorie analytique des nombres.
• [Gouvêa 1997] (en) Fernando Q. Gouvêa, P-adic Numbers : An Introduction, 1997 [détail de l’édition] — Introduction aux nombres p-adiques à la portée d'un large public, tournée vers des objectifs analytiques.
• [Hardy et Wright 2007] G. H. Hardy et E. M. Wright (trad. de l'anglais par François Sauvageot, préf. Catherine Goldstein), Introduction à la théorie des nombres [« An Introduction to the Theory of Numbers »] [détail de l’édition] — Un grand classique d'introduction à la théorie des nombres, qui couvre les sujets de base (congruences), introduit les méthodes algébriques par l'exemple (entiers de Gauss, de Kronecker), et donne une démonstration du théorème des nombres premiers.
• [Naudin et Quitté 1992] Patrice Naudin et Claude Quitté, Algorithmique algébrique, 1992 [détail de l’édition]
• [Ribenboim 1996] (en) Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996, 3^e éd. (lire en ligne)

• Inégalité de Bonse
• Primalité dans un anneau
• Problème de Lehmer

• Pierre Colmez, Éléments d'analyse et d'algèbre (et de théorie des nombres), Éditions de l'École Polytechnique, 2009
• Jean-Paul Delahaye, Merveilleux nombres premiers : Voyage au cœur de l'arithmétique, 2000 [détail de l’édition]
• Michel Demazure, Cours d'algèbre. Primalité, divisibilité, codes, Cassini, 1997. — Ce livre contient de nombreux algorithmes écrits en Caml Light.
• Michel Demazure, Cours d'algèbre. Primalité, divisibilité, codes, Cassini, 2008. — Version étendue (en particulier sur les codes correcteurs) de la première édition, la plupart des algorithmes ont été réécrits en Ruby.
• Plusieurs ouvrages avec le même titre, mais des contenus très différents, ont paru dans la collection Que sais-je ? :
  • Émile Borel, Les Nombres Premiers, PUF, coll. « Que sais-je ? » (n^o 571), 1953 ;
  • Jean Itard, Les Nombres Premiers, PUF, coll. « Que sais-je ? » (n^o 571), 1969.
  • Gérald Tenenbaum et Michel Mendès France, Les Nombres Premiers, PUF, coll. « Que sais-je ? » (n^o 571), 2000 (1^re éd. 1997), 127 p. (ISBN 2-13-048399-2).
  • Gérald Tenenbaum et Michel Mendès France, Les Nombres premiers, entre l'ordre et le chaos, Paris, Dunod, 2014, 2^e éd., 170 p. (ISBN 978-2-10-070656-3) — Version étendue et mise à jour du précédent, avec par exemple des références au théorème de Green-Tao, ou aux résultats de Zhang Yitang.

• Pierre Colmez, Les nombres premiers
• (en) Page d'Andrew Granville
• (en) The prime numbers : suite A000040 de l'OEIS
• Une grande liste des nombres premiers (jusqu'à 1 000 000 000)
• « Les nombres premiers », sur www.math93.com
• Test de primalité