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

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 ). 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 modifier

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

Article connexe modifier

Nombre premier probable