Nombre Premier Probable

Nombre Premier Probable

Nombre premier probable

En Arithmétique modulaire, un nombre premier probable (NPP) est un entier qui satisfait à une condition qui est satisfaite aussi par tous les nombres premiers. Ces nombres premiers probables peuvent être composés (appelés pseudopremiers), ils sont rares, dépendants du test utilisé.

Le test de Fermat pour la composition, qui est basé sur le petit théorème de Fermat énonce ce qui suit : soit un entier donné n, choisissons un certain entier a premier avec n et calculons an − 1 modulo n. Si le résultat est différent de 1, n est composé. S'il est égal à 1, n est premier ou pas ; n est alors appelé un nombre premier probable faible de base a.

Le test de Fermat peut être amélioré par l'usage du fait que les seules racines carrées de 1 modulo un nombre premier sont 1 et −1. Les nombres indiqués comme premiers par ce test renforcé sont connus comme des nombres premiers probables forts de base a .

Un nombre premier d'Euler probable est un entier qui est indiqué premier par le théorème quelque peu renforcé qui affirme que: pour n'importe quel nombre premier p, et n'importe quel a, a(p − 1)/2 = \left( \frac{a}{p}\right) modulo p, où \left( \frac{a}{p}\right) est le symbole de Legendre. Ce test est également efficace et il est au moins deux fois plus fort que le test de Fermat. Un nombre premier probable d'Euler qui est composé est appelé un pseudopremier d'Euler-Jacobi.

La primalité probable est une base pour les algorithmes de test d'efficience de primalité, qui trouvent une application en cryptologie. Ces algorithmes sont généralement probabiliste de nature. L'idée est qu'alors il existe des bases composées a probablement premières pour n'importe quel a fixé, nous pouvons renverser les rôles : pour n'importe quel n composé fixé et un a choisi aléatoirement, nous pouvons espérer que n n'est pas une base a pseudopremière, avec une haute probabilité.

Ceci est malheureusement faux pour les nombres premiers probables faibles, parce qu'il existe les nombres de Carmichael ; mais cela est vrai pour des notions plus raffinées de primalité probable, telles que les nombres premiers probables forts (nous obtenons alors l'algorithme de Miller-Rabin), ou les nombres premiers probables d'Euler (algorithme de Solovay-Strassen).

Même lorsqu'une preuve de primalité déterministe est requise, une étape très utile est le test par primalité probable.

Un test NPP est quelquefois combiné avec une table de petits pseudopremiers pour établir rapidement la primalité d'un nombre donné plus petit qu'un certain seuil.

Voir aussi

Liens externes

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Nombre premier probable ».

Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Nombre premier probable — En Arithmétique modulaire, un nombre premier probable (NPP) est un entier qui satisfait à une condition qui est satisfaite aussi par tous les nombres premiers. Ces nombres premiers probables peuvent être composés (appelés pseudopremiers), ils… …   Wikipédia en Français

  • Nombre pseudo-premier — Nombre pseudopremier Un nombre pseudopremier est un nombre premier probable (un entier qui partage une propriété commune à tous les nombres premiers) qui n est pas premier. Les nombres pseudopremiers peuvent être classés par rapport à la… …   Wikipédia en Français

  • Nombre Pseudopremier — Un nombre pseudopremier est un nombre premier probable (un entier qui partage une propriété commune à tous les nombres premiers) qui n est pas premier. Les nombres pseudopremiers peuvent être classés par rapport à la propriété qu ils satisfont.… …   Wikipédia en Français

  • Nombre De Wagstaff — En mathématiques, un nombre premier p de la forme pour un nombre premier q est appelé un nombre premier de Wagstaff ; ils sont reliés à la nouvelle conjecture de Mersenne. Les nombres premiers de Wagstaff ont été nommés en l honneur du… …   Wikipédia en Français

  • Nombre de wagstaff — En mathématiques, un nombre premier p de la forme pour un nombre premier q est appelé un nombre premier de Wagstaff ; ils sont reliés à la nouvelle conjecture de Mersenne. Les nombres premiers de Wagstaff ont été nommés en l honneur du… …   Wikipédia en Français

  • Nombre Pseudopremier D'Euler — En mathématiques et plus précisément en arithmétique modulaire un nombre pseudopremier d Euler désigne un nombre entier particulier. Un nombre impair composé n est appelé un pseudopremier d Euler de base a, si a et n sont premiers entre eux, et… …   Wikipédia en Français

  • Nombre pseudopremier d'euler — En mathématiques et plus précisément en arithmétique modulaire un nombre pseudopremier d Euler désigne un nombre entier particulier. Un nombre impair composé n est appelé un pseudopremier d Euler de base a, si a et n sont premiers entre eux, et… …   Wikipédia en Français

  • Nombre Pseudopremier D'Euler-Jacobi — Un nombre entier impair composé n est appelé pseudopremier d Euler Jacobi de base a, si a et n sont premiers entre eux, et où est le symbole de Jacobi. Cette définition est motivée par le fait que tous les nombres premiers n satisfont l équation… …   Wikipédia en Français

  • Nombre pseudopremier d'euler-jacobi — Un nombre entier impair composé n est appelé pseudopremier d Euler Jacobi de base a, si a et n sont premiers entre eux, et où est le symbole de Jacobi. Cette définition est motivée par le fait que tous les nombres premiers n satisfont l équation… …   Wikipédia en Français

  • Nombre pseudopremier — Un nombre pseudopremier est un nombre premier probable (un entier qui partage une propriété commune à tous les nombres premiers) qui n est pas premier. Les nombres pseudopremiers peuvent être classés par rapport à la propriété qu ils satisfont.… …   Wikipédia en Français

Share the article and excerpts

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