Nombre premier probable

En arithmétique modulaire, un nombre premier probable est un entier naturel qui satisfait à une condition (nécessaire mais pas suffisante) qui est satisfaite aussi par tous les nombres premiers.

Les nombres premiers probables qui se révèlent finalement non premiers (c'est-à-dire composés) sont appelés pseudo-premiers. Il en existe une infinité, mais ils restent cependant rares pour chaque condition utilisée.

Condition de Fermat

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 naturel n > 1, choisissons un certain entier naturel a premier avec n et calculons a^{n − 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 ». Les nombres composés probables faibles en toute base première avec eux sont les nombres de Carmichael.

Condition d'Euler

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 nombre pseudo-premier d'Euler-Jacobi.

Utilité des nombres premiers probables

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 probabilistes 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 pseudo-première, avec une haute probabilité.

Pour exemple, le langage informatique Java implémente un tel algorithme dans sa méthode isProbablePrime() définie sur des entiers arbitrairement longs.

Ceci est 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 (nombre premier probable) est quelquefois combiné avec une table de petits pseudopremiers pour établir rapidement la primalité d'un nombre donné plus petit qu'un certain seuil.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Probable prime » (voir la liste des auteurs).

Liens externes

• (en) « probable prime », sur Prime Pages
• (en) « PRP Records — Probable Primes Top 10000 », sur primenumbers.net