Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Test de primalité de Fermat
Résumé
vignette|Si le test de Fermat échoue, alors le nombre est composé. Si le test réussit, il y a de fortes chances que le nombre soit premier (illustration inspirée de , p. 30).
En algorithmique, le test de primalité de Fermat est un test de primalité probabiliste basé sur le petit théorème de Fermat. Il est de type Monte-Carlo : s'il détecte qu'un nombre est composé alors il a raison ; en revanche, il peut se tromper s'il prétend que le nombre est premier.
Petit théorème de Fermat
Le petit théorème de Fermat s'énonce en termes de congruence sur les entiers :
La réciproque du théorème est vraie car si p n'est pas premier, un diviseur non trivial a de p, plus généralement un a non premier avec p, n'est pas inversible modulo p, donc ne peut a fortiori avoir une puissance congrue à 1 modulo p. Mais les témoins de non primalité réellement apportés par le théorème de Fermat sont les a premiers avec p tels que .
Si on fixe a, il se peut que sans que p ne soit premier ; un tel nombre a est nécessairement premier avec p. Le nombre p est dit alors pseudo-premier de Fermat de base a. Un nombre p qui est pseudo-premier pour toute base a telle que a est premier avec p, est appelé nombre de Carmichael (on peut se restreindre à 1 < a < p). Les nombres de Carmichael sont « rares » mais il en existe une infinité.
Une conséquence du petit théorème de Fermat est que, lorsque est premier, pour tout entier a. Les nombres de Carmichael sont aussi les nombres composés vérifiant pour tout a (on peut se restreindre à 1 < a < p).
Le test de primalité de Fermat repose sur l'idée suivante : si p est composé, alors il est peu probable que a soit congru à 1 modulo p pour une valeur arbitraire de a. Voici un pseudo-code pour le test de Fermat, comme présenté par Dasgupta et al. :
fonction testPrimaliteFermat(N)
choisir un entier positif a < N au hasard
si aN-1 ≡ 1 mod N alors
renvoyer oui (N est probablement premier)
sinon
renvoyer non (N est composé)
Le calcul de aN-1 se fait avec un algorithme d'exponentiation modulaire. Cormen et al. (voir p.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.