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 a p -1 - 1 est divisible par p.



Catégories :

Test de primalité

Page(s) en rapport avec ce sujet :

  • Nombres premiers. Test de primalité. Décomposition en facteurs premiers. Test de primalité de Fermat. Test de primalité de Miller-Rabin.... (source : labri)
  • Exemple de programmation : TEST DE PRIMALITÉ OPTIMISÉ, JAVA / J2EE.... l'algorithme probabiliste est basé sur le test du théorème de fermat et c'est ... la primalité pour la plupart de valeurs mais pas des valeurs... (source : javafr)
  • Un test plus rapide, le Test de Fermat s'appuie sur le petit théorème de Fermat qui affirme que pour tout nombre premier p et tout... En recommençant le même test pour d'autres valeurs de la base a on... (source : gymnase-yverdon.vd)

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ˆ{p-1}\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 néenmoins pour tout entier a premier avec 561, on a aˆ{560}\equiv 1 \ \ (561) (voir les nombres de Carmichaël)

Mais nous pouvons tout de même écrire :

Si p est composé, alors ap − 1 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 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

1\equiv 2ˆ{x-1}\equiv 3ˆ{x-1}\equiv 5ˆ{x-1}\equiv 7ˆ{x-1} \ \ (x), alors nous savons que le nombre x est certainement 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 reconnu premier, quoique particulièrement 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.

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_de_Fermat.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu