Test de Primalité

Un test de primalité est un procédé mathématique permettant de déterminer si un nombre donné est un est un nombre premier (c'est-à-dire qu'il n'a aucun diviseur à par 1 ou lui-même).

Pour déterminer si un nombre est premier, il doit réussir un test de primalité qui confirme son statut de nombre premier.

Différents algorithmes de test peuvent être utilisés pour effectuer cette vérification.

Il existe différents tests pour savoir si un nombre est premier, le plus ancien est la crible d'Ératosthène, et les plus courants sont les tests de Miller–Rabin et Lucas-Lehmer.

Le crible d'Ératosthène est un algorithme ancien et efficace pour trouver tous les nombres premiers jusqu'à un certain nombre N. Il passe en revue tous les nombres entre 2 et racine de N, et élimine leurs multiples, les nombres restant sont des nombres premiers.

Pour les nombres inférieurs à 10^10, les tests sont déterministes, avec une vérification des potentiels diviseurs.

Pour les nombres inférieurs à 10^16, dCode utilise le test de Rabin-Miller puis le test de pseudo-primalité de Lucas, le résultat est garanti.

Pour les nombres supérieurs, les tests sont identiques, mais le résultat n'est plus certain mathématiquement, cependant le taux de faux positif est extrèmement faible (inférieur à 10^-10).

Un test de primalité déterministe fournit une réponse certaine sur la primalité d'un nombre, c'est-à-dire qu'il garantit si le nombre est premier ou non. En revanche, un test probabiliste fournit une réponse probable, avec une marge d'erreur contrôlée, ce qui signifie qu'il peut indiquer si un nombre est probablement premier ou probablement composé.

La définition même d'un nombre premier exige qu'il ait exactement deux diviseurs distincts : 1 et lui-même. Dans le cas de 1, il ne satisfait pas cette condition, car il n'a qu'un seul diviseur.

Cependant, c'est principalement une convention mathématique qui évite de nombreux problèmes dans les définitions et théorèmes mathématiques (où il faudrait exclure 1 ou le traiter comme cas particulier). Autre avantage, la décomposition en facteurs premiers est unique 6 = 2*3 et non pas 1*2*3 ou 1*1*1*2*3.

L'algorithme déterministe tente tous les nombres ou presque (il évite les nombres pairs et les multiples de 3). Voici un pseudo code applicable pour nombres premiers pas trop grands : // pseudo-code
fonction estPremier(n) {
si n ≤ 1 retourner FAUX
sinon si n ≤ 3 retourner VRAI
sinon si (n mod 2 = 0) ou (n mod 3 = 0) retourner FAUX
i = 5
tant que (i*i ≤ n) {
si (n mod i = 0) ou (n mod (i + 2) = 0) retourner FAUX
i = i + 6
}
retourner VRAI

Cette fonction vérifie si un nombre n donné est premier ou non en utilisant la méthode de division par essais, qui consiste à diviser n par tous les nombres entiers de 2 jusqu'à la racine carrée de n. Si aucun diviseur n’est trouvé dans cette plage, le nombre est premier. L'optimisation dans ce pseudo-code évite de vérifier les multiples de 2 et 3, pour accélérer le processus.

Les ordinateurs quantiques pourraient potentiellement révolutionner les tests de primalité en utilisant des algorithmes spécifiques à la mécanique quantique.

Certains algorithmes quantiques, tels que l'algorithme de Shor, pourraient factoriser rapidement de grands nombres, remettant en question la sécurité de certaines méthodes de cryptographie actuelles basées sur la difficulté de factorisation.

Des nombres premiers jumeaux sont deux nombres premiers consécutifs ayant un écart de 2.

Les nombres premiers de Mersenne sont des nombres premiers de la forme $ 2^n - 1 $.

Le test de primalité de Lucas-Lehmer est très efficace pour tester les nombres de Mersenne, ainsi, les plus grands nombres premiers connus sont tous des nombres de Mersenne.

Un test de primalité permet uniquement de déterminer si un nombre est premier ou non.

La factorisation en nombres premiers est un processus distinct et les méthodes employées ne permettent souvent pas de connaitre les diviseurs.

NB: Si le nombre est premier, alors sa factorisation est lui-même.