Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Test de primalité de Fermat

Le petit théorème de Fermat affirme que si p est un nombre premier et si a est premier avec p, alors a^p-1 - 1 est divisible par p. Ceci peut être aussi écrit

(pour mod voir arithmétique modulaire)

La réciproque de ce théorème est fausse, par exemple : 561=3×11×17 n'est pas premier et pourtant pour entier a premier avec 561, on a (voir les nombres de Carmichaël)

Mais nous pouvons tout de même écrire :

Si p est composé, alors est de façon improbable, congru à 1 modulo p pour une valeur arbitraire de a

ce qui représente une sorte de réciproque probabiliste du théorème.

Le programme de chiffrage PGP tire profit de cette propriété du théorème pour examiner si les grands nombres aléatoires qu'il choisit sont premiers. Il examine les valeurs que nous appellerons x en utilisant quatre valeurs de a (appelées témoins) en employant la formule ci-dessus. Ces quatre valeurs sont 2, 3, 5 et 7, les quatre premiers nombres premiers.

Si

, alors nous savons que le nombre x est probablement premier.

Si l'une quelconque de ces équations donne une valeur autre que 1, alors x est définitivement composé. Utiliser des témoins supplémentaires diminue la chance qu'un nombre composé x soit considéré premier, bien que très peu de grands nombres puissent duper les 4 témoins.

L'article sur les nombres pseudopremiers donne une explication détaillée sur les nombres qui dupent les tests de primalité de ce type.