Test de primalité de Fermat

Infos
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. Ceci peut être aussi écrit :a^\equiv 1 \ \ (p) (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 tout entier a premier avec 561, on a a^\equiv 1 \ \ (561) (voir les nombres de Carmichaël) Mais nous pouvons tout de mê
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 ap-1 - 1 est divisible par p. Ceci peut être aussi écrit :a^\equiv 1 \ \ (p) (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 tout entier a premier avec 561, on a a^\equiv 1 \ \ (561) (voir les nombres de Carmichaël) Mais nous pouvons tout de même écrire : Si p est composé, alors a^ 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 :1\equiv 2^\equiv 3^\equiv 5^\equiv 7^ \ \ (x), 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. Fermat cs:Fermatův test prvočíselnosti de:Fermatscher Primzahltest en:Fermat primality test es:Test de primalidad de Fermat it:Test di Fermat pl:Test pierwszości Fermata simple:Fermat's primality test vi:Kiểm tra Fermat zh:费马素性检验
Sujets connexes
Arithmétique modulaire   Congruence sur les entiers   Nombre composé   Nombre de Carmichaël   Nombre premier probable   Nombre pseudopremier   Petit théorème de Fermat   Réciproque  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^