Vérificateur Euler-Jacobi

Un pseudopremier d'Euler–Jacobi relativement à une base donnée est un entier composé impair qui obéit au critère d'Euler comme s'il était premier. Pour une base a première avec n, cela signifie que a élevé à (n moins un) sur deux est congruent au symbole de Jacobi de a sur n, modulo n. Tout premier impair qui ne divise pas a satisfait la même congruence, si bien que les composés qui passent encore sont les échecs intéressants d'un test à la Solovay–Strassen. Ce vérificateur répond précisément à cette question : étant donnés n composé impair et la base a, décider si n est un pseudopremier d'Euler–Jacobi pour a. La réponse rapporte le gcd, le symbole de Jacobi, la puissance modulaire, si la congruence tient, et un booléen vrai seulement lorsque la définition entière est remplie.

Qu'est-ce qu'un pseudopremier d'Euler–Jacobi, et en quoi il diffère des tests de Fermat et d'Euler

Le critère d'Euler affirme que si p est un premier impair et que a n'est pas divisible par p, alors a élevé à (p moins un) sur deux est congruent au symbole de Legendre de a sur p, modulo p. Le symbole de Jacobi (a/n) étend ce caractère quadratique des premiers impairs à tout entier positif impair n, d'où la tentation d'écrire la même congruence avec n à la place de p. Lorsque n est un premier impair, les deux symboles coïncident et la congruence est un théorème.

Lorsque n est impair et composé, la congruence peut encore tenir pour certaines bases bien que n ne soit pas premier. Ces n s'appellent des pseudopremiers d'Euler–Jacobi en base a, pourvu que gcd(a, n) vaille un. La condition est strictement plus forte que le test de Fermat (a élevé à n moins un congruent à un modulo n) et aussi plus forte que le test d'Euler faible, qui demande seulement que la puissance modulaire vaille plus un ou moins un.

L'illustration classique est trois cent quarante et un en base deux : c'est un pseudopremier de Fermat, deux élevé à cent soixante-dix vaut un modulo trois cent quarante et un, mais le symbole de Jacobi (2/341) vaut moins un, donc la congruence d'Euler–Jacobi échoue. Cinq cent soixante et un, le plus petit nombre de Carmichael, satisfait bien la congruence en base deux et est donc un pseudopremier d'Euler–Jacobi pour cette base. Quatre-vingt-onze en base dix est un autre exemple de cours que ce vérificateur confirme.

Contrat d'entrée, champs de réponse et comportement d'erreur

Si n est inférieur à neuf, pair ou premier, le gestionnaire rejette la requête : les pseudopremiers d'Euler–Jacobi sont des composés impairs par définition, et traiter un premier comme un pseudopremier manqué enseignerait la mauvaise leçon. Ces échecs de validation ne sont pas facturés. La chaîne criterion répète a^((n-1)/2) ≡ (a/n) (mod n) pour qu'une page ou un carnet affiche la définition à côté du verdict.

Lorsque gcd est supérieur à un, Jacobi vaut zéro et le couple n'est pas d'Euler–Jacobi même si une puissance accidentelle s'annule. Exemple : n égal à cinq cent soixante et un et a égal à deux donne jacobi un, remainder un et un drapeau vrai ; n égal à trois cent quarante et un et a égal à deux donne jacobi moins un, remainder un et un drapeau faux. Toute l'arithmétique est du BigInt exact ; il n'y a ni virgule flottante ni témoin aléatoire.

Où un vérificateur de pseudopremier d'Euler–Jacobi trouve son utilité

Les cours de théorie des nombres et les plateformes de concours utilisent un vérificateur de pseudopremier d'Euler–Jacobi pour que les élèves séparent les menteurs de Fermat des menteurs de Solovay–Strassen sans implémenter à la main la réciprocité de Jacobi ni l'exponentiation modulaire.

Les carnets de recherche et les balayages récréatifs appellent le même contrat lorsqu'ils veulent un oracle indépendant pour une liste publiée : cinq cent soixante et un, mille cent cinq, mille sept cent vingt-neuf et les autres exemples classiques en base deux doivent renvoyer vrai, tandis que trois cent quarante et un en base deux doit renvoyer faux.

Les ateliers de cryptographie qui présentent le test de primalité de Solovay–Strassen ont besoin d'un outil qui refuse n premier, car le point pédagogique est le composé qui imite le critère d'Euler, non de répéter que les premiers passent. Les équipes d'ingénierie qui écrivent des tests de propriétés pour leurs propres bibliothèques de Jacobi ou de puissance modulaire peuvent figer cette réponse comme contre-épreuve.

Préférez cet outil lorsque la question est strictement de savoir si un composé impair donné satisfait la congruence d'Euler–Jacobi pour une base donnée — non lorsque vous avez besoin d'une recherche sur toutes les bases, d'un test Fermat seul, d'un rapport de témoins Miller–Rabin ou de certificats pour des entiers de plusieurs milliers de bits.