From morain@polytechnique.frMon Apr 8 15:48:40 1996
Date: Mon, 8 Apr 1996 09:26:07 EDT
From: Francois Morain <morain@polytechnique.fr>
To: Multiple recipients of list NMBRTHRY <NMBRTHRY@vm1.nodak.edu>
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.