Nombre premier
Un nombre premier est un nombre entier supérieur à 1 dont les seuls facteurs sont 1 et lui-même.
Un facteur est un nombre entier qui peut être divisé de façon égale en un autre nombre. Les dix nombres premiers inférieurs à trente sont 2, 3, 5, 7, 11, 13, 17, 19, 23 et 29. Les nombres qui ont plusieurs facteurs sont appelés nombres composés. Le nombre 1 n'est ni premier, ni composé.
Pour chaque nombre premier p, il existe un nombre premier p' supérieur à p. Cette preuve mathématique, qui a été démontrée dans l'Antiquité par le mathématicien grec Euclide, valide le concept selon lequel il n'existe pas de « plus grand » nombre premier. Cependant, à mesure que l'ensemble de nombres naturels N = {1, 2, 3, ...} se poursuit, les nombres premiers deviennent généralement moins fréquents et sont plus difficiles à trouver dans un délai raisonnable. A ce jour, le plus grand nombre premier connu contient plus de 23 millions de chiffres. Baptisé M77232917, il dépasse d'un million de chiffres le précédent record.
Comment déterminer si un nombre est un nombre premier
Il est possible d'utiliser un ordinateur pour déterminer si un nombre extrêmement grand est un nombre premier. Mais comme il n'y a pas de limite à la grandeur des nombres naturels, il arrive toujours un moment où cela devient trop difficile même pour un superordinateur très puissant.
Divers algorithmes ont été créés pour essayer de générer des nombres premiers de plus en plus grands. Par exemple, supposons que n soit un nombre entier, et que personne ne sache encore s'il s'agit d'un nombre premier ou composé. Commençons par extraire la racine carrée (ou la puissance 1/2) de n, puis arrondissons ce nombre au nombre entier suivant le plus élevé et appelons le résultat m. Cherchons ensuite tous les quotients suivants :
qm = n / m
q(m-1) = n / (m-1)
q(m-2) = n / (m-2)
q(m-3) = n / (m-3)
. . .
q3 = n / 3
q2 = n / 2
Le nombre n est un nombre premier si, et seulement si, aucun des nombres q dérivés ci-dessus n'est un nombre entier.
Nombres premiers de Mersenne et de Fermat
Un nombre premier de Mersenne doit être réductible à la forme 2 n - 1, où n est un nombre premier. Les premières valeurs connues de n qui produisent des nombres premiers de Mersenne sont celles où n = 2, n = 3, n = 5, n = 7, n = 13, n = 17, n = 19, n = 31, n = 61 et n = 89.
Un nombre premier de Fermat est un nombre de Fermat qui est également premier. Un nombre de Fermat F n s'écrit sous la forme 2 m + 1, où m est la n-ième puissance de 2 (c'est-à-dire m = 2 n, où n est un nombre entier).
Nombres premiers et cryptographie
Le chiffrement suit toujours une règle fondamentale : l'algorithme (à savoir la procédure suivie) n'a pas besoin d'être secret, mais la clé doit l'être. Aucun pirate, même le plus sophistiqué du monde, ne pourra déchiffrer des données tant que la clé restera secrète, et les nombres premiers sont très utiles pour créer des clés. Par exemple, la fiabilité du chiffrement à clé publique ou privée réside dans le fait qu'il est facile de calculer le produit de deux nombres premiers choisis de manière aléatoire, mais qu'il peut être très difficile et long de déterminer les nombres premiers utilisés pour créer un produit extrêmement grand, lorsque seul le produit est connu.
Dans le chiffrement à clé publique RSA (Rivest-Shamir-Adleman), les nombres premiers sont toujours supposés être uniques. En revanche, les nombres premiers utilisés par les systèmes de cryptographie de l'échange de clés Diffie-Hellman et de l'algorithme DSS (Digital Signature Standard) sont souvent normalisés et utilisés par un grand nombre d'applications.
