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.