Vérificateur de pseudopremiers de Fermat pour toute base

Un composé qui réussit est un pseudopremier de Fermat pour la base choisie : il se comporte comme un nombre premier dans ce test précis sans l’être. Le plus grand commun diviseur est également fourni pour faciliter l’analyse et l’explication du résultat.

Ce que signifie réellement un résultat positif

Le petit théorème de Fermat affirme que si n est premier et que a n’est pas divisible par n, alors a élevé à la puissance n moins un laisse un reste égal à un modulo n. La réciproque n’est pas garantie. Certains entiers composés produisent eux aussi un reste égal à un pour certaines bases ; on les appelle des pseudopremiers de Fermat pour ces bases. Ce vérificateur exige délibérément que n soit composé, contrôle d’abord cette condition, puis évalue exactement la congruence. Lorsque passes_fermat_test et is_fermat_pseudoprime valent vrai, le composé fourni a trompé le test de Fermat pour cette base précise. Cela ne signifie pas que n est premier, probablement premier ou pseudopremier pour toutes les bases. La base fait partie intégrante de l’affirmation et doit toujours accompagner le résultat. Le reste renvoyé constitue la preuve arithmétique directe : un signifie que le test réussit, toute autre valeur qu’il échoue. Le plus grand commun diviseur aide en outre à reconnaître les bases premières avec n et les relations de facteur déjà visibles.

Comment le calcul reste exact

Les deux entrées sont des chaînes décimales afin que les entiers dépassant la plage numérique sûre de JavaScript ne soient pas arrondis avant le calcul. La plage admise s’arrête au plus grand entier non signé sur 64 bits, ce qui fixe une limite claire et vérifiable au contrôle de primalité. Avant le test de Fermat, le vérificateur applique une procédure déterministe de Miller–Rabin avec un ensemble de témoins suffisant sur toute cette plage. Un nombre premier détecté provoque une erreur de saisie : les nombres premiers satisfont le théorème, mais ne peuvent pas être des pseudopremiers par définition. Pour un composé valide, l’exponentiation modulaire emploie les carrés successifs au lieu de construire l’immense valeur a^(n-1). Chaque multiplication est réduite modulo n, ce qui maintient les valeurs intermédiaires bornées et exactes avec BigInt. L’algorithme d’Euclide calcule séparément gcd(a,n). La base doit respecter 2 <= a <= n - 2. Aucun témoin aléatoire, horodatage, appel réseau ou calcul flottant n’influence la réponse ; les mêmes entrées produisent donc toujours la même sortie.

Utilisation pour l’apprentissage et la vérification

Un exemple classique prend n = 341 et la base a = 2. Bien que 341 soit composé, 2^340 est congru à un modulo 341 ; il réussit donc le test et constitue un pseudopremier de Fermat en base deux. Avec une autre base, ce même composé peut échouer, raison pour laquelle un seul test de Fermat ne fournit pas un certificat général de primalité. Dans un cours, la sortie structurée relie directement la définition au reste calculé. Dans une suite de tests, elle permet de conserver des vecteurs connus de pseudopremiers et de non-pseudopremiers sans dépendre d’une bibliothèque mathématique ni de conversions propres à une machine. Pour explorer le phénomène, comparez plusieurs bases autorisées en gardant n fixe et observez l’importance du témoin choisi. Interprétez un résultat vrai comme une démonstration des limites du test de Fermat, jamais comme une autorisation d’accepter le nombre en tant que premier dans un code cryptographique ou sensible. L’API facture $0.002 par paire vérifiée, tandis que le navigateur exécute localement le même calcul déterministe.