From morain@polytechnique.frMon Apr 29 21:22:00 1996
Date: Mon, 29 Apr 1996 15:06:07 EDT
From: Francois Morain
To: Multiple recipients of list NMBRTHRY
Subject: (2^12391+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 N_p for p in {1709, 2617, 3539} using ECPP [Morain90]
and recently [Morain96] that N_10501 using the factorizations of the
Cunningham tables. Going one step further and using the same tables, I
have just finished that of p=12391.
The algebraic factors of N_12391-1 are the Phi_d(2) for d in
{1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 59, 70, 105, 118,
177, 210, 295, 354, 413, 590, 826, 885, 1239, 1770, 2065, 2478, 4130,
6195, 12390}
where Phi_d is the d-th cyclotomic polynomial.
For d <= 885 and d=1770, Phi_d(2) is completely factored
and the factors can be found in the Cunningham tables.
For the other values, we found:
d || factors of Phi_d(2)
----------------------------------
1239 || 263483263
2065 || 12391, 161071, 107429561, 34612315434702943134556428791471, P371
2478 || none
4130 || 78215598439665331
6195 || 224853721, 549273481
12390 || 6363561727426051
The factorization of Phi_{2065}(2) is new, as far as I know. I
obtained it with Lercier's mecm program using a 2nd classical stage
with B1=10^6 and B2=5*10^7. The primality of the cofactor was
established using ECPP.
The factored part F of N-1 amounts to log_10 F = 1273.751390, compared to
log_10 N = 3729.59. Since log(F)/log(N)= 0.3415, we have enough information to
prove the primality of N using for instance Theorem 5, pp. 624 of
[BrLeSe75].
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.
[Morain96] F. Morain
(2^10501+1)/3 is prime, announcement on nmbrthry, april 1996.
[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.