Test de primalité de Fermat

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En algorithmique, le test de primalité de Fermat est un test de primalité basé sur le petit théorème de Fermat.

Base arithmétique[modifier | modifier le code]

Le petit théorème de Fermat affirme que si p est un nombre premier et si a est premier avec p, alors ap-1-1 est divisible par p. C'est-à-dire, en termes de congruence sur les entiers :

La réciproque de ce théorème est fausse, par exemple : 561=3×11×17 n'est pas premier et pourtant pour tout entier a premier avec 561, on a . Les nombres qui font échouer la réciproque sont appelés nombres de Carmichaël, et forment un ensemble infini.

Test de primalité[modifier | modifier le code]

Le test de primalité de Fermat repose sur l'idée suivante : si p est composé, alors est de façon improbable, congru à 1 modulo p pour une valeur arbitraire de a.

Test PGP[modifier | modifier le code]

Le logiciel de chiffrement 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.

Histoire[modifier | modifier le code]

Notes et références[modifier | modifier le code]