Nombre premier

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Un nombre premier est un entier naturel strictement supérieur à 1, n'admettant que deux entiers naturels diviseurs distincts : 1 et lui-même. Ceci constitue la définition même (et unique) des nombres premiers.

Voici la liste des nombres premiers inférieurs à 100 :

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

Pour obtenir cette liste, il suffit d'observer une table de multiplication de Pythagore, à partir de 2 jusqu'à 10. Tous les nombres qui n'apparaissent pas sont les nombres premiers. Par opposition, les autres sont dits "composés" (sous-entendu composé par un produit d'au moins de deux nombres premiers). Un nombre composé est donc factorisable en un produit de puissances de facteurs de nombres premiers de façon unique, à l'ordre près. Par exemple $12 = 2^2 \times 3$ est composé, tout comme 21 = 3×7 ou 7×3, mais 11 est premier car la seule factorisation possible est 1×11 = 11. ⁸

Sommaire

1 Vocabulaire autour des nombres premiers
2 Infinité des nombres premiers
3 Calcul des nombres premiers
- 3.1 Algorithmes
  - 3.1.1 L'Algorithme d'Ératosthène
- 3.2 Les formules menant aux nombres premiers
  - 3.2.1 Formes polynômiales
    - 3.2.1.1 Formules explicites
    - 3.2.1.2 Formules implicites
  - 3.2.2 Autres formulations
4 Propriétés
5 Curiosités
6 Questions ouvertes
7 Applications
8 Généralisations des nombres premiers
9 Références
- 9.1 Citations
10 Voir aussi

[modifier] Vocabulaire autour des nombres premiers

On parle de primalité d'un nombre ou de test de primalité lorsqu'on recherche le caractère premier ou non du nombre.

L'ensemble des nombres premiers est noté $\mathbb{P}$ .

On note le n-ième nombre premier par $p_n\,$ dont la première valeur vaut $p_1 = 2\,$ .

On note $\pi(m)\,$ la fonction comptant le nombre de nombres premiers inférieurs ou égaux à m. Par exemple on a : $\pi(6)=3\,$ , $\pi(7)=4\,$ , etc.

Voir l’article fonction de compte des nombres premiers.

[modifier] Infinité des nombres premiers

Les nombres premiers sont étudiés depuis l'Antiquité. 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.

[modifier] Démonstration d'Euclide

Considérons une famille finie $p 1, p 2,... p n$ de nombres premiers, et montrons qu'on peut former un nombre premier n'appartenant pas à cette famille. Posons P le produit de tous ces nombres premiers et formons le nombre N = P + 1. Lorsqu'on divise N par chaque nombre premier $p i$ , le reste vaut 1.

N est soit premier lui-même, soit composé. S'il est composé, n'étant divisible par aucun des nombres premiers de la famille $p 1, p 2,... p n$ , il est alors le produit de nombres premiers qui ne font pas partie de cette famille.

Une autre façon de procéder est de prendre la factorielle du plus grand nombre considéré et de lui ajouter 1. Ainsi 2x3x4x5 +1 = 121, qui n'est pas un nombre premier (puisque c'est 11 au carré), mais qui n'est divisible par aucun nombre inférieur ou égal à 5, ce qui était le but recherché.

En conclusion, quelle que soit la quantité finie de nombres premiers considérée, il en existe un autre. Cela constitue la définition même de ce qu'est une infinité.

[modifier] Quelques types particuliers de nombres premiers

Il ne faut pas espérer en déduire pour autant que tout nombre de la forme N!+1 (factorielle n plus 1) est premier, et le contre-exemple est vite trouvé. Pour N=4, on a N! = 24 et le nombre 25, loin d'être premier, est le carré de 5. Mais il n'est en effet divisible par aucun nombre inférieur à 5. Un nombre premier est dit factoriel s'il est de la forme n! ± 1. Le plus grand nombre premier factoriel connu est 34790! - 1 [Marchal, Carmody, Kuosa, 2002]. Les premiers nombres premiers factoriels sont:

n! - 1 est premier pour n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166,…

n! + 1 est premier pour n = 1, 2, 3, 11, 13, 27, 37, 41, 73, 77, 116, 154…

Il ne faut pas non plus espérer pouvoir construire un nouveau nombre premier P en effectuant le produit de tous les nombres premiers inférieurs à une certaine borne q (primorielle) puis en lui ajoutant 1, c'est à dire P = 2 x 3 x 5 x … x q + 1, en effet ce procédé ne marche pas par exemple pour : 2 x 3 x 5 x 7 x 11 x 13 + 1 = 30 031 = 59 x 509. Un nombre premier p est dit primoriel s'il est de la forme p = Π(n) ± 1 pour un certain nombre n, où Π(n) représente le produit 2 · 3 · 5 · 7 · 11 · … de tous les nombres premiers inférieurs à n. Le plus grand nombre premier primoriel connu est Π(392113) + 1, trouvé par Daniel Heuer en 2001.

On ignore s'il existe une infinité de nombres premiers factoriels ou primoriels.

La démonstration d'Euclide introduit naturellement la suite dite d'Euclide-Mullin, définie de la façon suivante : $u 1 = 2$ et $u n + 1$ est le plus petit nombre premier diviseur de $u_1u_2\cdots u_n+1$ . Les premiers termes de cette suite sont :

2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, …

On ne connaît que les 43 premiers termes de cette suite et on ignore si tous les nombres premiers y apparaissent. Shanks a conjecturé en 1991 que tel était le cas.

Les nombres premiers de la forme $F_n = 2^{2^n} + 1$ sont appelés les nombres premiers de Fermat. À l'heure actuelle, F₀, F₁, F₂, F₃ et F₄ sont les seuls nombres de Fermat premiers connus.

[modifier] Autres démonstrations

D'autres mathématiciens ont donné leur propre démonstration sur l'infinité des nombres premiers. Celle de Kummer est comparable à celle d'Euclide, mais en considérant le produit des nombres premiers, diminué de 1. La preuve d'Euler utilise le fait que $\prod_{p\;{\rm premier}} {1 \over 1 - {1 \over p}} = \sum_1^{\infty} {1 \over n}$ qui est une série divergente. Le produit doit donc comporter une infinité de facteurs. Furstenberg fournit une preuve utilisant une argumentation topologique.

Bien que l'ensemble des nombres premiers soit infini, nous pourrions nous poser la question : combien y a-t-il de nombres premiers en dessous de 100 000 ?, ou quelle est la probabilité pour qu'un nombre entier aléatoire de 100 chiffres soit premier ? Des questions comme celles-ci trouvent une réponse grâce au théorème des nombres premiers.

[modifier] Le plus grand nombre premier connu

Le plus grand nombre premier connu est 2^{32 582 657}-1, il comporte 9 808 358 chiffres. Il s'agit du 44^e nombre premier de Mersenne connu (M_32 582 657) annoncé le 4 septembre 2006 grâce aux efforts d'une collaboration qui porte le nom de GIMPS.

Le record précédent était 2^{30 402 457}-1, et est aussi un nombre premier de Mersenne découvert par GIMPS le 15 décembre 2005. Tous les plus grands nombres premiers connus sont des nombres premiers de Mersenne car il existe un test de primalité particulièrement rapide adapté aux nombres de cette forme, le test de primalité de Lucas-Lehmer.

Quelques-uns des plus grands nombres premiers n'ayant pas de forme particulière (c'est-à-dire ne pouvant s'écrire à l'aide d'une formule simple comme les nombres premiers de Mersenne) ont été trouvés en prenant un morceau de données binaires pseudo-aléatoires, et en les convertissant en un nombre n, en multipliant par 256^k où k est un certain entier strictement positif, et en cherchant des nombres premiers éventuels dans l'intervalle [256^kn + 1, 256^k(n + 1) - 1].

En fait, pour lancer un coup publicitaire contre l'acte de copyright de Digital Millennium et les autres implémentations du traité de copyright WIPO, quelques personnes ont appliqué cette méthode à différentes formes variées du code DeCSS, en créant l'ensemble des nombres premiers illégaux.

De tels nombres, lorsqu'ils sont convertis en binaire et exécutés comme un programme informatique, enfreignent la loi en vigueur dans une ou plusieurs juridictions des États-Unis d'Amérique.

[modifier] Calcul des nombres premiers

[modifier] Algorithmes

Pour déterminer si un nombre est premier, on utilise des tests de primalité.

Certains tests de primalité sont probabilistes et choisissent un nombre aléatoire appelé « témoin » et vérifient quelque formule impliquant le témoin et le nombre potentiellement premier N. Après plusieurs itérations, ils déclarent N être « sans aucun doute composé » ou « probablement premier ». Ces examens ne sont pas parfaits. Pour un test donné, il peut y avoir plusieurs nombres composés qui seront déclarés « probablement premiers » indépendamment du témoin choisi. De tels nombres sont appelés pseudo-premiers pour ce test. Vous trouverez ici une description du test de primalité de Fermat.

L'algorithme AKS découvert en 2002 permet de déterminer si un nombre donné N est premier en utilisant un temps de calcul polynomial.

[modifier] L'Algorithme d'Ératosthène

Calcul de nombres premiers de 1 à 1 000 par la méthode du crible d'Ératosthène.

Pour rechercher une liste de tous les nombres premiers inférieurs à une limite n pas trop grande, le crible d'Ératosthène est une méthode simple et efficace : on part de la liste des entiers de 2 à n. On prend le premier nombre non barré de cette liste, 2 (à ce stade aucun nombre n'est barré), et on barre tous les entiers multiples de 2. On répète l'opération en considérant chaque fois le prochain nombre non barré et en barrant ses multiples. Les nombres qui restent non barrés à la fin du processus sont les nombres premiers inférieurs à n. (On peut en fait arrêter le processus dès que les nombres non barrés encore à considérer sont supérieurs à la racine carrée de n, car leurs multiples auront déjà été barrés.)

[modifier] Les formules menant aux nombres premiers

[modifier] Formes polynômiales

[modifier] Formules explicites

Il existe un polynôme de degré 25 à 26 variables à coefficients entiers tel que, si vous limitez les valeurs des variables aux nombres entiers naturels, alors l'ensemble des valeurs strictement positives est égal à l'ensemble des nombres premiers (pour de nombreuses valeurs des variables, le résultat est négatif et le nombre peut être alors composé) :

(k+2)×[1−(wz+h+j−q)²−(2n+p+q+z−e)²−(a²y²−y²+1−x²)²

−(e³(e+2)(a+1)²+1−o²)²−(16(k+1)³(k+2)(n+1)²+1−f²)²

−(((a+u²(u²−a))²−1)(n+4dy)²+1−(x+cu)²)²−(ai+k+1−l−i)²

−((gk+2g+k+1)(h+j)+h−z)²−(16r²y⁴(a²−1)+1−u²)²

−(p−m+l(a−n−1)+b(2an+2a−n²−2n−2))²−(z−pm+pla−p²l+t(2ap−p²−1))²

−(q−x+y(a−p−1)+s(2ap+2a−p²−2p−2))²−(a²l²−l²+1−m²)²−(n+l+v−y)²]

Il a été déterminé par Jones, Sato, Wada et Wiens en 1976. On peut noter que ce polynôme est exprimé sous la forme d'un produit de deux facteurs dont l'un est la somme du nombre 1 et de 14 expressions toutes négatives. Le polynôme ne peut donc être positif que si ces 14 expressions sont simultanéments nulles, et le nombre premier obtenu est alors donné par le deuxième facteur, $k + 2$ . Ce polynôme nous donne donc un système de 14 équations diophantiennes à 26 inconnues, auquel il faut trouver une solution pour obtenir un nombre premier. Ce polynôme est d'une rare inefficacité. Si bien qu'à ce jour on a pu trouver avec que le nombre 2.

D'autres polynômes existent, mais ne sont pas explicités. Le polynôme ayant le moins de variables actuellement défini est dû à Yuri Matijasevic, en 1977. Il possède 10 variables mais son degré est de l'ordre de 10⁴⁵!

Ces expressions ont donc un intérêt théorique (encore que très relatif) et non pratique.

Aucun polynôme d'une seule variable ne peut générer tous les nombres premiers. Néanmoins, à titre de curiosité, certains polynômes en donnent en quantité. C'est le cas pour :
- f(n) = n² − n + 41 (dû à Euler) qui donne des nombres premiers pour n allant de 0 à 40, mais f(41) est composé,
- f(n) = 103n² − 3945n + 34381 (dû à R. Ruby) pour n allant de 0 à 42,
- f(n) = 47n² − 1701n + 10181 (dû à G. Fung) pour n allant de 0 à 42,
- f(n) = 36n² − 810n + 2753 (dû à R. Ruby) pour n allant de 0 à 44.

[modifier] Formules implicites

Parmi la famille des polynômes, une voie astucieuse est la recherche des nombres non premiers.

En partant de la définition de base, on peut facilement établir que si n = m(m+k) soit m² + m*k - n = 0 admet comme solution les décompositions de n. De là, s'il existe que pour solution le couple (1,n) alors n est premier. La restriction des solutions aux nombres impairs et sans la solution triviale ci-dessus, nous conduit au crible de Sundaram.

En effet, pour que n soit impair, il faut que m et (m+k) le soit aussi. Il existe alors 2 possibilités équivalentes :

Soit en posant m = 2m'+1, on en déduit que k doit être pair, soit k = 2k'. En replaçant dans l'expression, on obtient n = (2m'+1)(2m'+1+2k') = (2m'+1)² + 2k'(2m'+1) = 4m'(m'+k'+1) + 2k' + 1 avec m'>=1 ; k'>=0 ; m', k' entier.
Soit en posant m+k = 2p+1, et donc que m = 2q+1. Ceci traduit l'idée que les nombres non premiers impairs sont obtenus par le produit de deux nombres impairs supérieur à 1. En remplaçant dans l'expression, on obtient n = (2p+1)(2q+1) = 4pq + 2(p+q) + 1 avec p>=1 ; q>=1 ; p, q entier.

Ainsi tous les nombres impairs décomposables sont générés par une des formules ci-dessus. Réciproquement, seuls les nombres premiers impairs (donc $\mathbb{P}$ \ {2} ) ne sont pas générés par ces équations polynômiales à deux variables seulement. Mais il est vrai qu'ici nous n'avons pas une forme explicite pour obtenir un nombre premier.

On peut également noter le "parrallèle" du crible de Sundaram avec le crible d'Erathostène. En effet, tous les multiples rayés dans le crible d'Erathostène, sont ceux obtenus dans les formulations ci-dessus.

[modifier] Autres formulations

On peut obtenir les nombres premiers avec des formules basées sur le théorème de Wilson. Cependant, elles sont peu intéressantes dans la pratique à cause du calcul de la factorielle ; même en faisant du calcul modulaire, ce qui évite de devoir manipuler de grands nombres, le nombre d'opérations nécessaires au calcul d'une factorielle est rédhibitoire.

[modifier] Fonction basée sur le théorème de Wilson

La fonction suivante donne tous les nombres premiers, et uniquement les nombres premiers, pour tout entier naturel n>1 :

$f(n) = 2 + (2(n!) \mod \ (n+1))$

Dans cette formule l'expression a mod b désigne le reste dans la division euclidienne de a par b. Le nombre deux est engendré plusieurs fois et tous les autres nombres premiers sont engendrés exactement une fois par cette fonction. Plus précisément, si n est premier, alors f(n-1) donne n, et si n n'est pas premier, f(n-1) donne 2. Appliquer cette formule à un entier n-1 peut ainsi être considéré comme un test de primalité de l'entier n, particulièrement peu efficace.

[modifier] Autres fonctions basées sur le théorème de Wilson

En utilisant la fonction partie entière, [x] (la partie entière de x est le plus grand entier inférieur au nombre réel x), nous pouvons construire plusieurs formules donnant le nème nombre premier.

Définissons, pour tout entier m, le nombre π(m) de nombres premiers inférieurs à m. On démontre :

$\pi(m) = \sum_{j=2}^m \frac { \sin^2 ( {\pi \over j} (j-1)!^2 ) } { \sin^2( {\pi \over j} ) }$

ou, de manière équivalente,

$\pi(m) = \sum_{j=2}^m \left[ {(j-1)! + 1 \over j} - \left[{(j-1)! \over j}\right] \right]$

Le nème nombre premier p_n peut être écrit sous la forme :

$p_n = 1 + \sum_{m=1}^{2^n} \left[ \left[ { n \over 1 + \pi(m) } \right]^{1 \over n} \right]$

[modifier] Fonction basée sur la partie entière

Une autre approche n'utilisant ni les factorielles, ni le théorème de Wilson, mais toujours aussi largement la fonction partie entière (S. M. Ruiz 2000). Définissons d'abord :

$G(k) = k - 1 + \sum_{j=2}^k \left[ {2 \over j} \left(1 + \sum_{s=1}^{\left[\sqrt{j}\right]} \left(\left[{ j-1 \over s}\right] - \left[{j \over s}\right]\right) \right)\right]$

nous avons alors :

$p_n = 1 + \sum_{k=1}^{2([n \ln(n)]+1)} \left(1 - \left[{G(k) \over n} \right]\right)$

[modifier] Propriétés

[modifier] Propriétés des nombres premiers

Si p est un nombre premier et si p divise un produit ab d'entiers, alors p divise a ou p divise b (lemme de Gauss).
Si p est un nombre premier et a est un entier quelconque, alors a^p - a est divisible par p (petit théorème de Fermat).
Un entier p est premier ssi la factorielle (p-1)! + 1 est divisible par p (théorème de Wilson). Inversement, un entier n > 4 est composé si et seulement si (n-1)! est divisible par n.
Si n est un entier strictement positif, alors il existe toujours un nombre premier p tel que n < p ≤ 2n (postulat de Bertrand).
La somme des inverses de tous les nombres premiers forme une série divergente. (voir la démonstration). Plus précisément, si S(x) désigne la somme de tous les inverses des nombres premiers inférieurs à x, alors S(x) = O(ln(ln(x))) pour x → ∞ (voir notation grand O).
Dans toute progression arithmétique a, a+q, a+2q, a+3q, où les entiers positifs a et q ≥ 1 sont premiers entre eux, il y a une infinité de nombres premiers (théorème de Dirichlet).

[modifier] Développement décimal de 1/p

Euler a prouvé une relation entre un nombre premier p (différent de 2 et de 5) et le nombre de chiffres k de la période du développement décimal de 1/p : k est un diviseur de p-1. (Le développement de 1/2 et de 1/5 est fini). Ce résultat est lié au petit théorème de Fermat : p divise 10^p-1-1. Donc il existe a tel que ${1 \over p} = {a \over {10^{p-1}-1}}$ et p-1 est un multiple de la période.

_n	p_n	Binaire	1/p	Nombre de chiffres de la période
1	2	10	0,5	1
2	3	11	0,3...	1
3	5	101	0,2	1
4	7	111	0,142857...	6
5	11	1011	0,09...	2
6	13	1101	0,076923...	6
7	17	10001	0,0588235294117647...	16
8	19	10011	0,052631578947368421...	18
9	23	10111	0,0434782608695652173913...	22
10	29	11101	0,0344827586206896551724137931...	28
11	31	11111	0,032258064516129...	15
12	37	100101	0,027...	3
13	41	101001	0,02439...	5
14	43	101011	0,023255813953488372093...	21
15	47	101111	0,0212765957446808510638297872340425531914893617...	46
16	53	110101	0,0188679245283...	13
17	59	111011	0,01694915254237288135593220338983050847457627118644 06779661...	58
18	61	111101	0,01639344262295081967213114754098360655737704918032 7868852459...	60
19	67	1000011	0,014925373134328358208955223880597...	33
20	71	1000111	0,01408450704225352112676056338028169...	35
21	73	1001001	0,01369863...	8
22	79	1001111	0,0126582278481...	13
23	83	1010011	0,01204819277108433734939759036144578313253...	41
24	89	1011001	0,01123595505617977528089887640449438202247191...	44
25	97	1100001	0,01030927835051546391752577319587628865979381443298 9690721649484536082474226804123711340206185567...	96

[modifier] Écart entre les nombres premiers

L'écart entre le nème nombre premier p_n et le n+1ème nombre premier p_n+1 est défini comme étant le nombre de nombres composés compris entre les deux, i.e. g_n = p_n+1 - p_n - 1 (des définitions légèrement différentes sont parfois utilisées). Nous avons g₁ = 0 et g₂ = 1. La suite (g_n) des écarts entre les nombres premiers a été étudiée en profondeur. On peut montrer que les écarts ne sont pas bornés, i.e. pour tout nombre entier naturel N, il existe un indice n tel que g_n > N. Il suffit pour cela de considérer l'intervalle suivant : [ N!+2 ; N!+N ] qui est un intervalle de longueur N−2 ne contenant pas de nombre premiers (quel que soit N).

D'autre part, pour tout nombre réel strictement positif ε, il existe un indice de début n₀ tel que g_n < ε · p_n pour tout n > n₀.

Nous disons que g_n est un écart maximal si pour tout m<n, g_m < g_n. Le plus grand écart maximal connu est de 1 131, trouvé par T. Nicely et B. Nyman en 1999. C'est le 64^e plus petit écart maximal, et il se situe après le nombre premier 1 693 182 318 746 371.

[modifier] Relations d'ordre

En notant p_n le n^ième nombre premier avec p₁=2, il a été démontré les relations suivantes :

p_n + p_n+1> p_n+2
p_n * p_m> p_n+m

[modifier] Ordre de grandeur

Le n^ième nombre premier noté p_n est encadré :

Avec U. Felgner (1990) par : n ln(n) < p_n < 1,7 n ln(n)
Avec Rosser (1938) par : n (ln(n)+ln(ln(n)) -10) < p_n < n (ln(n)+ln(ln(n)) +8)

En notant Π(m) le nombre de nombres premiers inférieurs ou égaux à m, il a été démontré par le Russe Pafnouti Tchebychev (1851) que

pour m>300 on a : 0,9*m/ln(m) < Π(m)< 1,2*m/ln(m)
pour m>96908 on a : 0,921*m/ln(m) < Π(m)< 1,105*m/ln(m)

On peut également évaluer Π(m) par le logarithme intégral, noté Li(x). Voir à ce sujet la page Théorème des nombres premiers.

[modifier] Propriétés algébriques liées aux nombres premiers

L'anneau $\mathbb Z/n\mathbb Z$ (voir arithmétique modulaire) est un corps si et seulement si n est premier.
La caractéristique d'un corps quelconque est ou bien zéro ou bien un nombre premier.
Si G est un groupe fini et si pⁿ est la plus grande puissance du nombre premier p qui divise l'ordre de G, alors G a un sous-groupe d'ordre pⁿ. (théorèmes de Sylow)
Si p est premier et si G est un groupe ayant pⁿ éléments, alors G contient un élément d'ordre p.

[modifier] Curiosités

Le nombre premier suivant correspond aux 38 premiers chiffres de Pi (voir Sloane A005042) :

31 415 926 535 897 932 384 626 433 832 795 028 841

DIX est un nombre premier (DIX en chiffres romains vaut 109)

1 111 111 111 111 111 111 est un nombre premier, comprenant 19 un. Les répunits sont des nombres dont l'indice n est tel que 11...111 = (10^n - 1)/9. Les répunits suivants sont premiers (source : Sloane A004023) : $R 2$ , $R 19$ , $R 23$ , $R 317$ , $R 1031$ , $R 49081$ , $R 86453$ .

La suite des chiffres en base dix d'un nombre premier peut être un palindrome, comme dans le nombre premier 10³¹⁵¹² + 9700079 · 10¹⁵⁷⁵³ + 1. 11 et 2 sont des palindromes triviaux.

[modifier] Questions ouvertes

Il y a beaucoup de questions ouvertes sur les nombres premiers. Par exemple :

La conjecture de Goldbach : tout nombre pair strictement supérieur à 2, peut-il s'écrire comme somme de deux nombres premiers ?
conjecture des nombres premiers jumeaux : un couple de nombres premiers jumeaux est une paire de nombres premiers dont la différence est égale à 2, comme 11 et 13. Existe-t-il une infinité de jumeaux premiers ?
Toute suite de Fibonacci contient-elle une infinité de nombres premiers ?
Existe-t-il une infinité de nombres premiers de Fermat ?
Y a-t-il une infinité de nombres premiers de la forme n² + 1 ?
Y a-t-il une infinité de nombres premiers factoriels ?
Y a-t-il une infinité de nombres premiers primoriels ?

[modifier] Applications

Les nombres premiers ont de nombreuses utilisations pratiques, dont la cryptographie asymétrique. Les nombres premiers extrêmement grands (c'est-à-dire plus grand que 10¹⁰⁰) sont de possibles clés publiques cryptographiques, rendant ainsi impossible, dans l'état actuel de la technologie, un décryptage ("craquage") en temps réel. Un craquage anticipé reste cependant possible. On prête à la NSA le projet de constituer une immense base de données inverse où seraient précalculés tous les couples clé privée/clé publique jusqu'à une certaine taille. Lorsqu'on a un message à craquer, si sa clé publique est dans cette base, il suffit d'y prendre la clé privée associée, peut-être calculée quinze ans plus tôt. Les mémoires à exaoctet sont lentes, mais un seul accès nous suffit.

Les nombres premiers sont aussi utilisés pour construire des tables de hachage et pour constituer des générateurs de nombres pseudo-aléatoires.

[modifier] Généralisations des nombres premiers

Le concept de nombre premier est si important qu'il a été généralisé de différentes façons dans des branches variées des mathématiques. L'ensemble {2,3,5,7,11,…} est l'ensemble des nombres premiers des entiers naturels. L'ensemble {…,-11,-7,-5,-3,-2,2,3,5,7,11,…} est l'ensemble des nombres premiers des entiers relatifs. Lorsque nous parlons de nombres premiers sans précision, nous considérons les nombres premiers entiers naturels. Mais il arrive que certains dictionnaires de mathématiques définissent les nombres premiers en considérant les nombres premiers entiers relatifs.

En théorie des nombres, certains mathématiciens qualifient de nombres pseudo-premiers des entiers qui, parce qu'ils satisfont à un certain test, sont considérés comme des nombres premiers probables mais peuvent être en fait composés (comme les nombres de Carmichaël). Pour modéliser certaines des propriétés des nombres premiers, nous définissons les polynômes premiers ou irréductibles. Plus généralement, nous pouvons définir des éléments premiers et irréductibles dans tout anneau intègre. Les idéaux premiers constituent un outil indispensable et font l'objet d'une étude en algèbre commutative et en géométrie algébrique. Ils définissent des éléments se comportant comme des nombres premiers. Les nombres premiers de Gauss, dans l'anneau des entiers de Gauss, les polynômes irréductibles ou les nombres premiers d'Eisenstein en sont des exemples.

[modifier] Références

[modifier] Citations

« Un nombre premier est un nombre qui ne se casse pas quand on le laisse tomber par terre. » Paul Erdôs

« Les mathématiciens ont tâché jusqu'ici en vain de découvrir quelque ordre dans la progression des nombres premiers, et l'on a lieu de croire que c'est un mystère auquel l'esprit humain ne saurait jamais pénétrer. Pour s'en convaincre, on n'a qu'à jeter les yeux sur les tables des nombres premiers que quelques-uns se sont donné la peine de continuer au-delà de cent mille et l'on s'apercevra d'abord qu'il n'y règne aucun ordre ni règle. » Euler, 1751.

« La percée mathématique évidente serait le développement d'un moyen simple de factoriser les grands nombres en facteurs premiers. » Bill Gates, The Road Ahead, Viking Penguin (1995)

[modifier] Voir aussi

[modifier] Bibliographie

Jean-Paul Delahaye, Merveilleux nombres premiers, Éditions Belin - Pour la Science, 2000 - ISBN 2701150175
Paulo Ribenboim, The new book of big prime number records, Springer, 1996, ISBN 0387944575

[modifier] Articles connexes

[modifier] Liens externes

(en) Chris K. Caldwell : « La page des nombres premiers », http://www.utm.edu/research/primes/
(en) Chris K. Caldwell : « Nombre premiers illégaux », http://primes.utm.edu/glossary/page.php/Illegal.html
(en) J. O'Connor et E. F. Robertson : « histoire MacTutor des nombres premiers », http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/Prime_numbers.html
(en) Carlos Rivera : « les puzzles de nombres premiers » http://www.primepuzzles.net/
(es) La page de Sebastián Martín Ruiz : http://perso.wanadoo.es/smaranda/
(en) Manindra Agarwal, Nitin Saxena, Neeraj Kayal, « PRIMES is in P », Preprint, 6 août 2002, http://www.cse.iitk.ac.in/users/manindra/primality_v6.pdf (PDF)
(en) The « PRIMES is in P » FAQ http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html
(en) Les 100 000 premiers nombres premiers, http://gutenberg.net/etext/65

Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques.

Récupérée de « http://fr.wikipedia.org../../../n/o/m/Nombre_premier.html »

Catégories : Arithmétique élémentaire • Nombre premier