Nombre pseudo-premier d'Euler-Jacobi

Un nombre composé impair n est dit pseudo-premier d'Euler-Jacobi de base a s'il est premier avec a et si

${\displaystyle a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}}$

où ${\displaystyle \left({\frac {a}{n}}\right)}$ est le symbole de Jacobi.

Cette définition^[1],[2] est motivée par le fait que tous les nombres premiers n satisfont l'équation précédente, d'après le critère d'Euler. L'équation peut être testée assez rapidement, ce qui peut être utilisé pour les tests de primalité probabilistes. Ces tests sont plus de deux fois plus forts que les tests basés sur le petit théorème de Fermat.

Tout nombre pseudo-premier d'Euler-Jacobi est aussi un nombre pseudo-premier de Fermat et un nombre pseudo-premier d'Euler (vérifiant ${\displaystyle a^{(n-1)/2}\equiv \pm 1{\pmod {n}}}$). Il n'existe pas de nombre qui soit pseudo-premier d'Euler-Jacobi pour toutes les bases première avec lui : ce ne sont pas des nombres de Carmichael. Solovay et Strassen ont montré que^[3] pour tout nombre composé n, pour au moins n/2 bases inférieures à n, n n'est pas un nombre pseudo-premier d'Euler-Jacobi.

Ces nombres sont parfois appelés « nombres pseudo-premiers d'Euler »^[4],[5].

La table ci-dessous donne tous les nombres pseudo-premiers d'Euler-Jacobi inférieurs à 10 000 pour les bases premières a < 100.

a
2	561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481 (suite A047713 de l'OEIS)
3	121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911 (suite A048950 de l'OEIS)
5	781, 1541, 1729, 5461, 5611, 6601, 7449, 7813 (suite A262052 de l'OEIS)
7	25, 325, 703, 2101, 2353, 2465, 3277, 4525
11	133, 793, 2047, 2465, 4577, 4921, 5041, 5185
13	85, 105, 1099, 1785, 5149, 7107, 8841, 8911, 9577, 9637
17	9, 91, 145, 781, 1111, 1305, 2821, 4033, 4187, 5365, 5833, 6697, 7171
19	9, 45, 49, 169, 343, 1849, 2353, 2701, 3201, 4033, 4681, 6541, 6697, 7957, 8281, 9997
23	169, 265, 553, 1271, 1729, 2465, 2701, 4033, 4371, 4681, 6533, 6541, 7189, 7957, 8321, 8651, 8911, 9805
29	15, 91, 341, 469, 871, 2257, 4371, 4411, 5149, 5185, 6097, 8401, 8841
31	15, 49, 133, 481, 931, 2465, 6241, 7449, 8911, 9131
37	9, 451, 469, 589, 685, 817, 1233, 1333, 1729, 3781, 3913, 4521, 5073, 8905, 9271
41	21, 105, 231, 671, 703, 841, 1065, 1281, 1387, 1417, 2465, 2701, 3829, 8321, 8911
43	21, 25, 185, 385, 925, 1541, 1729, 1807, 2465, 2553, 2849, 3281, 3439, 3781, 4417, 6545, 7081, 8857
47	65, 85, 221, 341, 345, 703, 721, 897, 1105, 1649, 1729, 1891, 2257, 2465, 5461, 5865, 6305, 9361, 9881
53	9, 27, 91, 117, 1405, 1441, 1541, 2209, 2529, 2863, 3367, 3481, 5317, 6031, 9409
59	15, 145, 451, 1141, 1247, 1541, 1661, 1991, 2413, 2465, 3097, 4681, 5611, 6191, 7421, 8149, 9637
61	15, 217, 341, 1261, 2465, 2701, 2821, 3565, 3661, 6541, 6601, 6697, 7613, 7905
67	33, 49, 217, 561, 703, 1105, 1309, 1519, 1729, 2209, 2245, 5797, 6119, 7633, 8029, 8371
71	9, 35, 45, 1387, 1729, 1921, 2071, 2209, 2321, 2701, 4033, 6541, 7957, 8365, 8695, 9809
73	9, 65, 205, 259, 333, 369, 533, 585, 1441, 1729, 1921, 2553, 2665, 3439, 5257, 6697
79	39, 49, 65, 91, 301, 559, 637, 1649, 2107, 2465, 2701, 3913, 6305, 6533, 7051, 8321, 9881
83	21, 65, 231, 265, 561, 689, 703, 861, 1105, 1241, 1729, 2665, 3277, 3445, 4411, 5713, 6601, 6973, 7665, 8421
89	9, 15, 45, 153, 169, 1035, 1441, 2097, 2611, 2977, 3961, 4187, 5461, 6697, 7107, 7601, 7711
97	49, 105, 341, 469, 481, 949, 973, 1065, 2701, 3283, 3577, 4187, 4371, 4705, 6811, 8023, 8119, 8911, 9313

Notes et références

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

1. « Euler-Jacobi Pseudoprime », sur archive.lib.msu.edu (consulté le 4 février 2023)
2. (en) Richard G.E. Pinch, « Absolute quadratic pseudoprimes », Proceedings of Conference on Algorithmic Number Theory,‎ 2007 (lire en ligne [PDF])
3. (en) R. Solovay et V. Strassen, « A Fast Monte-Carlo Test for Primality », SIAM Journal on Computing, vol. 6, n^o 1,‎ mars 1977, p. 84–85 (ISSN 0097-5397 et 1095-7111, DOI 10.1137/0206006, lire en ligne, consulté le 4 février 2023)
4. (en) Carl Pomerance, J. L. Selfridge et Samuel S. Wagstaff, « The pseudoprimes to 25⋅10⁹ », Mathematics of Computation, vol. 35, n^o 151,‎ 1980, p. 1003–1026 (ISSN 0025-5718 et 1088-6842, DOI 10.1090/S0025-5718-1980-0572872-7, lire en ligne, consulté le 4 février 2023)
5. (en) Zihao Jiang, « Applications of Number Theory in Cryptography » [PDF], 2013

Article connexe

Nombre premier probable

• Arithmétique et théorie des nombres