test de primalité

ARITHMETIQUE

Un test de primalité est un algorithme permettant de savoir si un nombre est premier .
Ils sont utilisés en cryptographie.
Il existe différents tests de primalité : les uns anciens (crible d’Eratosthène ), ou datant du 17e siècle (test de Fermat utilisant le petit théorème de Fermat http://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_de_Fermat ) ou beaucoup plus récents comme les tests de Lucas-Lehmer , de Solovay-Strassen, de Miller-Rabin , voire très récents comme le test AKS des mathématiciens indiens Agrawal, Kayal et Saxena (2002).
On distingue trois types de tests : les tests déterministes, les tests probabilistes, les tests de composition (de pseudo-primalité).