Pourquoi étudier les nombres premiers ?

Les nombres premiers ont des propriétés qui les rendent très importants dans des applications numériques, aussi bien du coté théorique que pratique.  L'aspect le plus important est probablement le fait qu'ils indiquent quels sont les anneaux modulaires qui sont des champs, c'est à dire, dans quels cas on peut calculer un inverse multiplicatif de tout nombre dans l'anneau.  Mais ils ont d'autres propriétés: le fait que tout entier peut être écrit comme un produit unique de nombres premiers est une autre raison pour laquelle les nombres premiers sont importants.  Ils permettent, par exemple, de coder dans un seul entier une liste illimitée d'entiers (qui seront les puissances des nombres premiers successives dans le codage).

Nombres qui sont des nombres premiers relatifs et la fonction Phi de Euler

Deux entiers sont des nombres premiers relatifs, s'ils n'ont en commun que le diviseur trivial 1.  Par exemple, 8 et 15 sont des nombres premiers relatifs.  Les diviseurs de 8 sont {1,2,4,8}, et les diviseurs de 15 sont {1,3,5,15}.  Seulement 1 est en commun.  Bien sûr, chaque nombre premier est un nombre premier relatif à tout entier, mais, comme nous voyons avec l'exemple, deux nombres non-premiers peuvent très bien être des nombres premiers relatifs.

Dans un anneau modulaire, tous les éléments qui sont nombre premier relatif avec le module, ont un inverse multiplicatif.  Bien sûr, les diviseurs même du module ne sont pas nombre premier relatif avec le module, et donc, ils n'ont pas d'inverse: c'est pourquoi un anneau modulaire avec un module qui n'est pas un nombre premier n'est pas un champs.  Le nombre 1 est bien sûr, strictement parlé, un nombre premier relatif avec tout nombre, mais n'est pas compté comme nombre premier.

Si nous avons un anneau modulaire avec module M, alors le nombre d'éléments qui possèdent un inverse multiplicatif est égal au nombre d'entiers qui sont plus petits que M, et qui sont des nombres premiers relatifs avec M.  Ce nombre est utilisé pour définir une fonction bizarre sur les entiers: la fonction Phi de Euler.

La fonction Phi de Euler, Phi(M), est égal au nombre de nombres plus petit que M, qui sont nombres premiers relatifs avec M.  On peut aussi dire: la fonction Phi(M) est égal au nombre d'éléments possédant un inverse multiplicatif dans l'anneau modulaire avec module M.

Une façon simple et évidente, mais immensément lente, pour calculer Phi(M), est de parcourir les nombers 2, 3, 4, ... , M-1, et de calculer le PGDC de ce nombre avec M.  Chaque fois que le résultat est 1, nous avons donc un nombre qui est un nombre premier relatif avec M, et donc qui possède un inverse multiplicatif. 

Mais il y a un théorème qui nous permet de calculer la valeur de Phi(M) bien plus vite:

M peut être factorisé en nombres premiers de la façon suivante:

M = (p1)e1  (p2)e2 .... (pk)ek

Alors: Phi(M) = le produit des nombres [ (pi)ei - (pi)ei - 1 ]

Par exemple, si M = 60, alors nous écrivons M comme un produit de facteurs premiers:  60 = 22 31 51

La formule pour Phi(60) est alors [ 22 - 21 ] [ 31 - 30 ] [51 - 50 ] = [4 - 2] [3 - 1] [5 - 1] = 2 . 2 . 4 = 16

Dans un anneau modulaire avec module 60, il y a donc 16 nombres qui ont un inverse multiplicatif ; il y a 16 nombres qui sont des premiers relatifs avec 60.

Notez que cela implique que Phi(p) = p - 1 si p est un nombre premier.  Mais on le savait déjà: dans un anneau modulaire avec module p qui est un nombre premier, l'anneau devient un champs, et tout élément sauf 0 possède un inverse, donc il y en a p - 1.

Le théorème d'Euler

Rappelons le petit théorème de Fermat:

ap = a (mod p)

où a est un entier et p est un nombre premier.

On peut aussi l'écrire comme:

ap - 1 = 1 (mod p)

Le théorème d'Euler est une généralisation du petit théorème de Fermat dans le sens suivant:

aPhi(m) = 1 (mod m)

Effectivement, dans le cas où p est un nombre premier, ceci devient le petit théorème de Fermat car Phi(p) = p - 1 dans ce cas, mais le théorème d'Euler est valable pour tout entier.

Tests de primalité

Il est souvent nécessaire de sélectionner (de façon aléatoire et secrète, ou de façon publique) un très grand nombre premier.  La façon standard de vérifier qu'un grand nombre est un nombre premier, est en divisant le candidat par tous les diviseurs potentiels premiers jusqu'à la racine carré du nombre candidat.  Mais cela devient impossible dans la pratique quand nous parlons de très grands nombres premiers, car il faudrait tester beaucoup trop de diviseurs.

Malheureusement, il n'existe pas un test exhaustif et sûr pour de très grands nombres qui ne se réduit pas à une variante de tester tous les diviseurs.  Mais il existent de bons tests statistiques, qui permettent de conclure qu'un entier est un nombre premier avec une très faible probabilité d'erreur.  Ces tests indiquent avec certitude qu'un nombre n'est pas un nombre premier, mais n'indiquent que avec une grande probabilité qu'il soit nombre premier.

La densité des nombres premiers est grosso modo 2/ln(N) parmi les nombres impairs, c'est à dire, la probabilité qu'un grand nombre impair, N, soit un nombre premier est 2/ln(N).  Une façon de choisir un nombre premier "au hasard" (et secret), avec à peu près k chiffres, est de choisir un nombre entier q avec k chiffres au hasard.  En suite, on va tester si q, q+1, q+2, .... est un nombre premier ; le premier qu'on trouve dans la suite sera notre nombre premier "tiré au hasard".  Avec la probabilité qu'un nombre impair soit un nombre premier de 2/ln(N), cela veut dire que si on veut un nombre premier de 1024 bits, alors un nombre impair sur 354 sera un nombre premier.  Il faudra donc essayer en moyenne 354 nombres impairs avant de trouver un nombre premier.

Le nombre d'essais nécessaire pour trouver un nombre premier monte proportionnellement avec le nombre de bits voulu dans le nombre premier.

Le test de primalité de Fermat

Ce test est basé sur le petit théorème de Fermat.  In en va ainsi si on veut tester si p est un nombre premier:

  1. choisissez un nombre aléatoire de test a dans l'ensemble {2,3,....p-1}
  2. calculez ap-1 mod p
  3. si le résultat n'est pas 1, alors p n'est pas nun nombre premier, on s'arrête là
  4. si le résultat est 1, retournez à l'étape 1 jusqu'à ce que vous en avez assez

Ce test est sûr si nous essayons toutes les valeurs de a, mais c'est bien sûr impossible.  Ainsi, nous allons choisir de façon statistique quelques valeurs dans l'étape 1.  Plus de valeurs qu'on teste, et plus de valeurs qui n'indiquent pas que p n'est pas un nombre premier, plus que la probabilité que p soit un vrai nombre premier, augmente.

Le problème avec le test de Fermat est qu'il existe un petit ensemble de nombres, les nombres Carmichael, qui ne sont pas des nombres premiers, mais qui réussissent le test tant qu'on ne choisit en étape 1, une valeur de a qui soit nombre premier relatif à p (ce qui est quasiment toujours le cas).  Il est estimé qu'il y ait à peu près un nombre Carmichael sur 10 milliards.  Si on tombe sur un nombre Carmichael comme p, alors c'est presque sûr que le test de primalité de Fermat indiquera erronément que se soit un nombre premier, même avec un très grand nombre d'itérations.

Le test de primalité de Miller-Rabin

Un test qui évite le problème des nombres Carmichael du test de Fermat, et qui est devenu la façon standard de tester pour un nombre premier, est le test de Miller Rabin.  Il en va ainsi, quand on veut tester si p est un nombre premier:

  1. trouver la décomposition p - 1 = 2u r (il faut donc trouver u et r)
  2. choisissez un nombre de test a dans l'ensemble {2,3,.... p-1}
  3. vérifiez que ar mod p n'est pas 1 ou p -1 (si c'est le cas, allez à l'étape 8 directement)
  4. remplacez a par a2
  5. si le nouveau a est égal à p - 1, allez à l'étape 8
  6. si le nouveau a est égal à 1, alors p n'est pas un nombre premier ; on peut s'arrêter
  7. répétez les étapes 4 - 7 autant de fois que nous aurons pris le carré de a (u - 1) fois
  8. si p est toujours potentiellement un candidat premier, alors retournez à l'étape 2 jusqu'à ce que vous en avez marre
  9. si p est toujours là, il est fort probable que ce soit un nombre premier

Le test de Miller Rabin est basé sur le théorème de Miller, qui dit que pour un entier p qui n'est pas un nombre premier, le test décrit ci-dessus n'arrive pas à détecter cela pour des nombres a (choisis en étape 2.) en moins de Phi(p)/4 cas.  En d'autres termes, en choisissant un a, si le test de Miller-Rabin marche, on a déjà une probabilité de plus que 3/4 que p soit un nombre premier, quel qu'il soit.  En choisissant un autre a, cette probabilité monte à 87.5%.  Et ainsi de suite.  Le test de Miller Rabin est très bon à repérer des nombres Carmichael, ce qui était la faille du test de Fermat.