nombre pseudo-premier

Prenons 341. On peut le décomposer en 11 × 31 : il n'est donc pas premier. Pourtant, si un test n'essaie que la base 2, ce nombre se comporte comme un nombre premier et passe le contrôle.

Un tel imposteur arithmétique est appelé pseudo-premier pour la base et le test choisis. Une autre base peut révéler immédiatement qu'il est composé. Le mot ne décrit donc pas une catégorie unique : il faut toujours préciser la propriété imitée et, souvent, la base utilisée.

Un nombre pseudo-premier est un entier composé qui satisfait un critère nécessaire de primalité sans être premier. La qualification dépend donc du critère. Pour le test de Fermat, on fixe un entier composé n et une base entière non triviale a, strictement comprise entre 1 et n, qui n'a aucun diviseur commun avec n, hormis 1. Le nombre n est pseudo-premier de Fermat en base a lorsque .

La base fait partie de l'énoncé : 341 est pseudo-premier de Fermat en base 2, mais pas en base 3. Un nombre de Carmichael, aussi appelé pseudo-premier absolu, est au contraire un entier composé qui vérifie la congruence de Fermat pour toute base a première avec lui. L'expression « toutes les bases » signifie donc toutes les classes de bases admissibles, et non les multiples d'un facteur de n.

D'autres critères produisent d'autres familles, notamment les pseudo-premiers d'Euler, de Fibonacci et les pseudo-premiers forts associés au test de Miller-Rabin. Un entier peut passer une base particulière sans passer les autres. Un test probabiliste répété avec plusieurs bases réduit le risque de faux positif ; il ne faut toutefois jamais confondre un verdict « probablement premier » avec une preuve déterministe de primalité.

Testons 341 avec le critère de Fermat. La figure résume les trois informations décisives : sa factorisation, le succès en base 2 et l'échec en base 3.

Données.
Entier testé : n = 341.
Factorisation : 341 = 11 × 31.
Première base : a = 2.
Base de contrôle : a = 3.

Étape 1. Comme 341 possède les facteurs 11 et 31, il est composé. Il ne peut donc être premier.

Étape 2. En base 2, on obtient 2¹⁰ = 1 024 = 3 × 341 + 1. Ainsi, 2¹⁰ laisse le reste 1 dans la division par 341.

Étape 3. Puisque 340 = 10 × 34, le calcul complet devient : $2^{340}=(2^{10}{)}^{34}\equiv 1^{34}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}341)2^\{340\}=(2^\{10\})^\{34\}\; \backslash equiv\; 1^\{34\}\; \backslash equiv\; 1\; \backslash pmod\{341\}$. 341 passe donc le test de Fermat en base 2 : c'est un pseudo-premier pour cette base.

Contrôle. En base 3, le calcul donne $3^{340}\equiv 56(\mathrm{m}\mathrm{o}\mathrm{d}341)3^\{340\}\; \backslash equiv\; 56\; \backslash pmod\{341\}$, et 56 n'est pas 1. Cette base détecte le caractère composé de 341 et confirme qu'il ne s'agit pas d'un nombre de Carmichael.

Pour écarter rapidement de grands entiers composés, on applique un test de primalité à une ou plusieurs bases. Dès qu'une base fournit un témoin d'échec, l'entier est certainement composé et le calcul peut s'arrêter.

Quand un test de Fermat réussit, le bon verdict est seulement que l'entier a passé ce test pour cette base. On préfère Miller-Rabin pour un filtrage plus robuste, car son critère fort élimine davantage de composés ; plusieurs bases renforcent encore le contrôle.

Lorsqu'une certitude est requise, par exemple pour établir un résultat mathématique, un test probabiliste positif ne suffit pas à lui seul. Il faut employer une méthode déterministe ou produire un certificat de primalité vérifiable.

Nombre pseudo-premier et nombre premier. Un pseudo-premier est composé par définition, même s'il passe le critère testé. La factorisation 341 = 11 × 31 tranche immédiatement : 341 est pseudo-premier en base 2, mais il n'est pas premier.

Pseudo-premier de Fermat et nombre de Carmichael. Le premier terme concerne une base fixée ; le second exige un succès pour toute base première avec l'entier. Le succès de 341 en base 2 et son échec en base 3 le placent seulement dans la première catégorie.

Pseudo-premier de Fermat et pseudo-premier fort. Les deux notions viennent de tests différents. Un entier peut réussir le test de Fermat pour une base et échouer au critère plus exigeant de Miller-Rabin pour cette même base ; le nom du test doit accompagner le verdict.

Une seule base ne prouve rien. Le symptôme est une congruence réussie, comme en base 2 pour 341. Il faut essayer d'autres témoins ou choisir un test accompagné d'une garantie adaptée au besoin.

La base doit être admissible. Le critère de Fermat suppose que la base et l'entier testé sont premiers entre eux. Si leur plus grand diviseur commun dépasse 1, ce calcul ne relève pas du cas défini ; ce diviseur commun révèle déjà un facteur de l'entier.

« Absolu » ne signifie pas tous les entiers sans condition. Pour un nombre de Carmichael, le quantificateur porte sur toutes les bases premières avec le nombre. Il faut conserver cette hypothèse dans toute formulation ou vérification.

Le résultat dépend du test nommé. « Pseudo-premier » employé seul masque le critère imité. Il faut préciser Fermat, Euler, Fibonacci ou fort selon la propriété effectivement vérifiée, sans transférer automatiquement un succès d'une famille à une autre.

Le petit théorème de Fermat donne la congruence imitée par 341 en base 2 et précise pourquoi tout nombre premier satisfait ce contrôle.

La fiche sur le nombre de Carmichael approfondit les entiers composés qui trompent le test de Fermat pour toutes les bases admissibles.

Le test de primalité replace Fermat et Miller-Rabin parmi les méthodes servant à distinguer preuve, témoin de composition et verdict probabiliste.

La notion de nombre premier rappelle la propriété de divisibilité que les pseudo-premiers ne possèdent jamais, malgré leur comportement trompeur dans certains tests.