From morain@polytechnique.frMon Apr 8 15:48:40 1996 Date: Mon, 8 Apr 1996 09:26:07 EDT From: Francois Morain To: Multiple recipients of list NMBRTHRY Subject: (2^10501+1)/3 is prime The numbers N_p = (2^p+1)/3 for prime p are studied in relation to the New Mersenne Conjecture [BaSeWa89]. Sam Wagstaff had found that N_p is a probable prime for p in {61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479}. I proved the primality of 1709, 2617 and 3539 using ECPP [Morain90]. I was surprised to see that the Cunningham tables contained enough information to prove the primality of N_10501, which I did. Here are some details: 2^{10500}-1 = prod_{d | 10500} Phi_d(2) where Phi_d is the d-th cyclotomic polynomial. The divisors of 10500 are {1, 2, 3, 4, 5, 6, 7, 10, 12, 14, 15, 20, 21, 25, 28, 30, 35, 42, 50, 60, 70, 75, 84, 100, 105, 125, 140, 150, 175, 210, 250, 300, 350, 375, 420, 500, 525, 700, 750, 875, 1050, 1500, 1750, 2100, 2625, 3500, 5250, 10500} For d <= 1500 and d in {2100, 3500}, Phi_d(2) is completely factored and the factors can be found in the Cunningham tables. Their product forms F0 such that log F0 = 3535.050621. For the other values, we found: d || factors of Phi_d(2) ---------------------------------- 1750 || {558251, 10022251} 2625 || none 5250 || 362-digit prime 10500 || { 10501, 60018001 } The primality of Phi_{5250}(2) was established using ECPP. The factored part F of N-1 amounts to log F = 4422.944035, compared to log N = 7277.639931. This shows that we have enough information to prove the primality of N using for instance Corollary 1, pp. 623 of [BrLeSe75]. For the other values of p, the situation is not as favorable. The case p = 5807 might be doable in the near future. F. Morain References =========== [BaSeWa89] P. T. Bateman and J. L. Selfridge and S. S. {Wagstaff, Jr.} The new Mersenne conjecture. Amer. Math. Monthly, 96, 2, 1989, pp. 125--128. [Morain90] F. Morain Distributed Primality Proving and the primality of (2^{3539}+1)/3. Proc. EUROCRYPT'90, Lecture Notes in Comput. Sci. 473, 1991. [BrLeSe75] J. Brillhart and D. H. Lehmer and J. L. Selfridge New primality criteria and factorizations of 2^m +/- 1. Math. Comp. 29, 130, 1975, pp. 620--647.