Table des matières
Un nombre premier est un nombre entier qui a EXACTEMENT deux diviseurs, 1 et lui-même. Par exemple : 2, 3, 5, 7, 11, 13, etc.
1 n'est pas premier (un seul diviseur).
Résultat important :
Tout nombre entier est factorisable DE MANIÈRE UNIQUE en produit de nombre premiers.
Les nombres premiers et la factorisation des entiers sont des notions connues depuis l'antiquité. Ils sont restés longtemps dans le domaine des mathématiques pures. Depuis l'essor de la cryptographie (surtout en informatique) ces notions sont passées dans le camp des mathématiques (très) appliquées.
Il y a une infinité de nombres premiers.
Ils sont de plus en plus rares à mesure qu'on s'avance dans les grands nombres.
Le nombre des entiers premiers inférieurs à un nombre x est noté π(x) et cette fonction est (pour des grandes valeurs de x) approximativement égale à
(Conjecture de Gauss, en 1798, démontrée en 1896 par Jacques Hadamard et Charles de La Vallée-Poussin, indépendamment l'un de l'autre.)
Il existe un nombre infini de paires de nombres premiers de la forme (n,n+2), comme par exemple (5,7), (29,31), etc.
Dans [RechHS] on trouve :
On connaît depuis 1969 un polynôme particulier, à 24 variables et de degré 37, dont les valeurs positives quand les variables parcourent l'ensemble des entiers positifs et négatifs sont exactement les nombres premiers. Cette formule est malheureusement inutilisable dans la pratique. Les variables doivent prendre des valeurs tellement astronomiques que le seul nombre premier qui ait pu être obtenir grâce à elle est 2.
Il est assez facile de décider si un entier est premier. Pour un entier relativement petit, le crible d'Ératosthène est suffisant.
Pour des entiers plus grands, il existe des algorithmes efficaces pour décider de la primarité. Certains permettent seulement de décider en un temps raisonnable qu'un entier n'est pas premier, mais pas de décider qu'il est premier (on applique un test : si la réponse est positive, l'entier n'est pas premier ; si la réponse est négative, l'entier est PROBABLEMENT premier).
Sur des nombres ayant certaines particularités, on a pu trouver des nombres premiers très grands. Par exemple parmi les nombres de Mersennes (de la forme 2q-1 où q est un entier positif), on a pu trouver un nombre premier de 258 716 chiffres.
Mais même parmi les nombres sans propriétés particulières on peut montrer en quelques minutes qu'un nombre de 200 chiffres est premier ou non.
Il est assez facile de factoriser un nombre n raisonnablement petit en facteurs premiers : il suffit d'essayer de la diviser par tous les nombres plus petits que la racine carrée de n. Si on les connaît, on se limitera à diviser par des nombres premiers.
Cette solution est inapplicable aussitôt qu'on arrive dans des nombres grands.
Et la frontière des grands nombres est beaucoup plus basse pour ce problème que pour le précédent. Il peut exister des nombres dont on peut dire qu'ils ne sont pas premiers sans qu'on sache trouver leur factorisation en un temps raisonnable.
En quelques minutes sur un seul ordinateur on peut décider si un nombre de 200 chiffres est premier, mais il faudra quelques semaines pour factoriser un nombre de 100 chiffres.
La notion de temps raisonnable signifie simplement : en un temps acceptable avec des moyens acceptables pour que la solution soit moins coûteuse qu'une autre solution.
Si le problème est de trouver une solution à une crise mondiale ou un traitement contre une maladie grave (je ne crois pas qu'il y ait actuellement de rapport entre les nombres premiers et ce type de problème, mais supposons...), le fait d'utiliser tous les ordinateurs de la planète à temps plein pendant une semaine, cette durée reste un temps tout à fait raisonnable.
Si le problème est de casser la protection d'un système, alors que cette protection est modifiée tous les jours, la même méthode correspond évidemment un temps tout à fait déraisonnable.
Dans [RechHS] on trouve par exemple :
En 1995 on pouvait factoriser avec des moyens raisonnables (en quelques semaines sur un micro-ordinateur) un nombre de 90 chiffres. Avec des moyens déraisonnables on pouvait venir à bout d'un nombre de 130 chiffres (en utilisant des milliers d'ordinateurs à travers le monde, reliés grâce à un internet).
[RechHS] « L'intrigue des nombres premiers ». La Recherche. Hors série n°2. Août 1999.
[PLS251] « La factorisation des grands nombres ». Pour La Science. n°251. Septembre 1998.
[PLS256] « Formules pour les nombres premiers ». Pour La Science. n°256. Février 1999.
[ManuGPG] « Le manuel de GNU Privacy Guar ». http://www.gnupg.org/gph/fr/manual.html . The Free Software Foundation. 1999.