Test de primalité

Un test de primalité est un algorithme servant à savoir si un nombre entier est premier.



Catégories :

Test de primalité - Cryptologie

Page(s) en rapport avec ce sujet :

  • Les nombres premiers sont redevenus un sujet fort à la mode.... Un algorithme de test de primalité est par conséquent polynômial si, prenant un entier n, ... (source : bibmath)
  • Un test de primalité, est une condition qui sera satisfaite obligatoirement par un nombre premier, et ne marchera que 1/p fois sur un nombre qui ne l'est ... (source : ody2000.free)
  • pour reconnaître si un nombre est premier, pour afficher l'ensemble des nombres premiers compris entre deux entiers donnés. Le test de primalité est basé sur la... (source : dept-info.labri)

Un test de primalité est un algorithme servant à savoir si un nombre entier est premier.

Méthode naïve

Le test le plus simple est le suivant : pour tester N, on vérifie s'il est divisible par l'un des entiers compris entre 2 et N (limites comprises). Si la réponse est négative, alors N est premier, sinon il est composé.

Plusieurs changements permettent de perfectionner les performances de cet algorithme :

Tests probabilistes

Les tests probabilistes ne sont pas des tests de primalité au sens strict : ils ne permettent pas de s'assurer de façon certaine qu'un nombre est premier, mais sont acceptables pour des applications pratiques telles que la cryptologie qui fréquemment dépend de façon critique des grands nombres premiers. Ils sont néenmoins particulièrement utilisés dans les cas où un faible taux d'erreur est acceptable : on les nomme des nombres premiers industriels. L'idée de base est la suivante :

  1. Prendre aléatoirement un nombre a.
  2. Vérifier une certaine égalité entre a et le nombre donné N. Si l'égalité échoue, alors N est un nombre composé, a est connu comme un témoin pour la composition, et le test s'arrête.
  3. Répéter l'étape 1 jusqu'à ce que la certitude requise soit achevée.

Après plusieurs itérations, si N n'est pas reconnu comme un nombre composé, alors il est déclaré certainement premier.

Ces tests sont rapides mais fréquemment imparfaits. Pour un test donné, il peut exister certains nombres composés qui seront déclarés «certainement premier» quel que soit le témoin. De tels nombres sont nommés nombres pseudopremiers pour ce test .

Le test de primalité probabiliste le plus simple est le test de primalité de Fermat. Il est quelque fois utilisé si un affichage rapide des nombres est indispensable, par exemple, dans la phase de génération de clé de l'algorithme de cryptographie à clé publique RSA. Le test de primalité de Miller-Rabin et le test de primalité de Solovay-Strassen sont des variantes plus particulièrement élaborées qui détectent l'ensemble des composés ; ils sont fréquemment des méthodes de choix.

Tests déterministes rapides

Le test cyclotomique est un test de primalité déterministe ; on démontre que son temps d'exécution est O (nclog (log (n) ) ), où n est le nombre de chiffres de N et c est une constante indépendante de n. Il est plus lent que le temps polynomial.

On peut démontrer que le test de primalité de courbe elliptique est d'exécution O (n6), mais uniquement en utilisant certaines conjectures de théorie analytique des nombres non toujours démontrées mais beaucoup acceptées comme vraies. Dans la pratique, ce test est plus lent que le test cyclotomique pour les nombres comportant plus de 10 000 chiffres.

L'implémentation de ces deux méthodes est plutôt complexe, et leur probabilité d'erreur dans la pratique peut être donc énormément plus élevée que celles des méthodes probabilistes mentionnées ci-dessus.

Si l'hypothèse de Riemann généralisée est vraie, le test de Miller-Rabin peut être converti en une version déterministe avec un temps d'exécution Õ (n4). Dans la pratique, cet algorithme est plus lent que les deux qui ont précédé pour des tailles de nombres qui peuvent être traités par eux.

En 2002, Manindra Agrawal, Nitin Saxena et Neeraj Kayal ont décrit un nouveau test de primalité déterministe qui s'exécute en Õ (n12), et cette limite peut être démontrée rigoureusement. Qui plus est , selon une conjecture (non démontrée, par conséquent, mais beaucoup reconnue comme vraie), il s'exécuterait en Õ (n6). C'est par conséquent le premier test de primalité déterministe de temps d'exécution polynomial. Dans la pratique, cet algorithme est plus lent que les autres méthodes.

Méthodes basées sur la théorie des nombres

La théorie des nombres apporte des méthodes; un bon exemple est le test de Lucas-Lehmer pour tester si un nombre est premier. Ce test est relié au fait que l'ordre multiplicatif d'un certain nombre a modulo n est n-1 pour un nombre premier n lorsque a est une racine primitive. Si nous pouvons montrer que a est une racine primitive pour n, nous pouvons montrer que n est premier.

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.
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