Test probabiliste de primalité

Les probabilités peuvent apparaître dans un contexte inhabituel : c'est le cas lorsqu'on parle de "nombres premiers probables".
Deux endroits où vous pouvez rencontrer de tels nombres.

Le logiciel de calcul formel MAPLE indique comme documentation de la fonction isprime, : The function isprime is a probabilistic primality testing routine. It returns false if n is shown to be composite within one strong pseudo-primality test and one Lucas test and returns true otherwise. If isprime returns true, n is ``very probably'' prime - see Knuth ``The art of computer programming'', Vol 2, 2nd edition, Section 4.5.4, Algorithm P for a reference and H. Riesel, ``Prime numbers and computer methods for factorization''. No counter example is known and it has been conjectured that such a counter example must be hundreds of digits long.
Le logiciel de calcul formel en ligne WIMS, si vous utilisez l'outil Primes vous prévient :Primes est un outil pour les recherches de nombres premiers. Il vous permet de rechercher des nombres premiers de différentes façons, et peut générer des nombres premiers de très grande taille (jusqu'a 200 chiffres ou plus). Par souci d'efficacité, l'outil vous donne d'abord des listes de nombres premiers probables comme résultat de recherche; vous pouvez ensuite cliquer sur un nombre pour le passer dans un test de primalité rigoureux. (Sachez tout de même que vous n'avez qu'une chance sur des milliards pour trouver un nombre premier probable qui n'est pas premier.)

Voici un exemple simple de test probabiliste de primalité.

Les nombres de Carmichaël
Pour tester si un nombre est premier, la méthode la plus connue, dite du crible, consiste à chercher s'il est divisible par un nombre premier inférieur à sa racine carrée. Malheureusement cette méthode est peu efficace pour de grands nombres puisque le nombre d'opérations croit exponentiellement avec le nombre de chiffres du nombre à tester.

On peut aussi envisager d'utiliser le (petit) théorème de Fermat : si p est premier et que a est premier avec p, alors a^p-1 est congru à 1 modulo p.
On calcule a^p-1 modulo p (il existe une méthode simple pour effectuer ce calcul) et, si le résultat n'est pas 1, le nombre n'est pas premier. Malheureusement, la réciproque du théorème est fausse. En effet, il existe même des nombres composés p qui vérifient : pour tout entier a, a^p-1 est congru à 1 modulo p. Ce sont les nombres de Carmichaël.
Les premiers nombres de Carmichaël sont :
561 = 3 · 11 · 17
1 105 = 5 · 13 · 17
1 729 = 7 · 13 · 19
2 465 = 5 · 17 · 29
2 821 = 7 · 13 · 31
6 601 = 7 · 23 · 41
8 911 = 7 · 19 · 67
On sait beaucoup de choses sur les nombres de Carmichaël : par exemple qu'ils sont tous produits d'au moins trois nombres premiers impairs différents. Pour en savoir plus sur les nombres de Carmichael voir : http://www.research.att.com/~njas/sequences/A002997

Réciproque probabiliste
Cependant on peut envisager une sorte de réciproque probabiliste du théorème de Fermat.

Si 1 = 2 ^n-1 (modulo n) [T1], (on choisit a= 2 dans le théorème de Fermat) alors nous savons que le nombre n est probablement premier. Sinon n est composé. Si un nombre x verifie : x n'est pas premier, a est premier avec x et x divise a^x-1- 1 , alors x est appelé un pseudopremier de base a. Les pseudopremiers de base 2 sont appelés nombres de Poulet.
Essayons d'avoir une idée du risque pris en considérant qu'un nombre de Poulet est premier. Le plus petit nombre pseudopremier de Fermat pour la base 2 est 341. 341 vérifie le test T1 et n'est pas premier, en effet 2340 = 1 mod 341 mais 341= 11x31. Il existe seulement 3 pseudopremiers de base 2 inférieurs à 1 000 et 245 inférieurs à un million.
Pour en savoir plus sur les nombres de Poulet : http://www.research.att.com/~njas/sequences/A001567

On peut diminuer le risque en choisissant d'autres entiers a que 2. Si 1 = 2 ^n-1 = 3 ^n-1 = 5 ^n-1 = 7 ^n-1 (modulo n), alors le nombre n est probablement premier. C'est la méthode que choisit le programme de chiffrage PGP (http://fr.wikipedia.org/wiki/Pretty_Good_Privacy) pour examiner si les grands nombres aléatoires qu'il choisit sont premiers.

Remarques

En pratique on utilise souvent des tests un peu plus complexes comme le test de Rabin-Miller http://www.math.u-bordeaux.fr/~jehanne/Agregation/Rabin_Miller.pdf
En 2002, trois mathématiciens indiens ont trouvé un nouvel algorithme pour tester la primalité d'un entier : il indique si n est premier ou composé en un temps qui est un polynôme de la taille de n http://smf.emath.fr/Publications/Gazette/2003/98/smf_gazette_98_14-29.pdf