Les tests les plus utilisés pour tester la primalité d'un nombre sont les tests de Fermat et de Miller-Rabin. Ce sont des tests probabilistiques qui prouvent qu'un nombre n'est pas premier ou qui supposent avec une certaine probabilité qu'un nombre est premier. Ces tests se basent sur le théorème de Fermat qui dit :
si p est premier et 1<=a<n alors a^(n-1) = 1 mod p
# Compléments
Posté par jcs (site web personnel) . En réponse à la dépêche Encore plus de Nombres Premiers. Évalué à 10.
si p est premier et 1<=a<n alors a^(n-1) = 1 mod p
plus d'infos sur
http://www.utm.edu/research/primes/prove/index.html(...)
Autre précision, tester la primalité d'un nombre sert aussi à créer des pairs de clés publiques/privés pour le RSA, DSA... par exemple.