Test de primalite


Test de primalite

Test de primalité

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

Sommaire

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 (bornes comprises). Si la réponse est négative, alors N est premier, sinon il est composé.

Plusieurs changements permettent d'améliorer les performances de cet algorithme :

  • il suffit de tester tous les nombres de 2 à \sqrt{N} seulement, puisque si N = pq alors soit p \leq \sqrt{N} soit q \leq \sqrt{N},
  • on peut encore diviser par deux le travail en ne testant que les nombres impairs, une fois que la divisibilité par deux a échoué,
  • de façon générale, on peut calculer à l'avance une liste des nombres premiers inférieurs à une limite (avec un crible d'Ératosthène), pour ne tester que ceux-ci (soit 46 tests pour les nombres inférieurs à 39000, par exemple).

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 souvent dépend de façon critique des grands nombres premiers. Ils sont pourtant très utilisés dans les cas où un faible taux d'erreur est acceptable : on les appelle 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é probablement premier.

Ces tests sont rapides mais souvent imparfaits. Pour un test donné, il peut exister certains nombres composés qui seront déclarés « probablement premier » quel que soit le témoin. De tels nombres sont appelé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 nécessaire, 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 sophistiquées qui détectent tous les composés ; ils sont souvent 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 seulement en utilisant certaines conjectures de théorie analytique des nombres non encore démontrées mais largement 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 difficile, et leur probabilité d'erreur dans la pratique peut être par conséquent bien 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 précédents 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 borne peut être démontrée rigoureusement. De plus, selon une conjecture (non démontrée, donc, mais largement reconnue comme vraie), il s'exécuterait en Õ(n6). C'est donc 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 fournit 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 quand a est une racine primitive. Si nous pouvons montrer que a est une racine primitive pour n, nous pouvons montrer que n est premier.

  • Portail des mathématiques Portail des mathématiques
  • Portail de l’informatique Portail de l’informatique
  • Portail de la cryptologie Portail de la cryptologie

Ce document provient de « Test de primalit%C3%A9 ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Test de primalite de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Test de primalité — Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier. Sommaire 1 Méthode naïve 2 Tests probabilistes 3 Tests déterministes rapides …   Wikipédia en Français

  • Test de primalite AKS — Test de primalité AKS Le test de primalité AKS (aussi connu comme le test de primalité Agrawal Kayal Saxena et le test cyclotomique AKS) est un algorithme déterministe de preuve de primalité découvert et publié le 6 août 2002 par trois… …   Wikipédia en Français

  • Test de primalité aks — Le test de primalité AKS (aussi connu comme le test de primalité Agrawal Kayal Saxena et le test cyclotomique AKS) est un algorithme déterministe de preuve de primalité découvert et publié le 6 août 2002 par trois scientifiques indiens nommés… …   Wikipédia en Français

  • Test de primalite de Miller-Rabin — Test de primalité de Miller Rabin Le test de primalité de Miller Rabin est un test de primalité probabiliste : c’est à dire un algorithme qui détermine si un nombre donné est probablement premier, de façon similaire au test de primalité de… …   Wikipédia en Français

  • Test de primalité de miller-rabin — Le test de primalité de Miller Rabin est un test de primalité probabiliste : c’est à dire un algorithme qui détermine si un nombre donné est probablement premier, de façon similaire au test de primalité de Fermat et le test de primalité de… …   Wikipédia en Français

  • Test de primalite de Solovay-Strassen — Test de primalité de Solovay Strassen Le test de primalité de Solovay Strassen, dû à Robert M. Solovay et Volker Strassen, est un test probabiliste permettant de déterminer si un nombre impair est un nombre composé ou un nombre premier probable.… …   Wikipédia en Français

  • Test de primalité de solovay-strassen — Le test de primalité de Solovay Strassen, dû à Robert M. Solovay et Volker Strassen, est un test probabiliste permettant de déterminer si un nombre impair est un nombre composé ou un nombre premier probable. Les concepts Le mathématicien suisse… …   Wikipédia en Français

  • Test de primalite de Lucas-Lehmer — Test de primalité de Lucas Lehmer Le test de primalité de Lucas Lehmer est une méthode pour tester la primalité de certains nombres n ; il requiert que les facteurs premiers de n 1 soient connus. S il existe un a inférieur à n et plus grand… …   Wikipédia en Français

  • Test de primalité de lucas-lehmer — Le test de primalité de Lucas Lehmer est une méthode pour tester la primalité de certains nombres n ; il requiert que les facteurs premiers de n 1 soient connus. S il existe un a inférieur à n et plus grand que 1 tel que et, pour tous les… …   Wikipédia en Français

  • Test de primalite de Lucas-Lehmer pour les nombres de Mersenne — Test de primalité de Lucas Lehmer pour les nombres de Mersenne En mathématiques, le test de Lucas Lehmer est un test de primalité pour les nombres de Mersenne. Le test fut originellement développé par Édouard Lucas en 1878 et amélioré de façon… …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.