From tonyforbes@ltkz.demon.co.uk Sat Dec 7 06:53:39 1996
Date: Fri, 6 Dec 1996 17:29:06 -0500
From: Tony Forbes
To: NMBRTHRY@LISTSERV.NODAK.EDU
Subject: Large prime triplets
Large Prime Triplets
--------------------
Tony Forbes
-----------
On 4 December 1996 I found the triplet of 1083-digit primes
(1) 437850590*(2^3567 - 2^1189) - 6*2^1189 - 5,
437850590*(2^3567 - 2^1189) - 6*2^1189 - 1,
437850590*(2^3567 - 2^1189) - 6*2^1189 + 1.
I believe this to be the largest known prime triplet and, according to
Chris Caldwell's Titanic Primes database, it seems to be the only known
example where the individual primes have more than a thousand decimal
digits each. In [1, 2] I reported a triplet of 1041-digit probable (but
unproven) primes.
Of related interest, Warut Roonguthai [3] has found prime quadruplets p,
p+2, p+6, p+8 of 500 decimal digits and Harvey Dubner [4] discovered two
Carmichael numbers of the form (6k+1)*(12k+1)*(18k+1), where each factor
is a prime of either 1024 or 1025 decimal digits.
The numbers we consider have the form
(2) m*(2^(3*n) - 2^n) - 6*2^n + e, e = -5, -1, 1,
where 0 < m < 2^31 and where n = +/-1 (mod 6) is such that 2^n + 1 is
completely factorized into primes.
For primality proofs we apply Theorems 7 and 19 of [5]. Write
N = m*(2^(3*n) - 2^n) - 6*2^n.
When e = +/-1, we need to at least partially factorize N. Let N = F*R,
where F is completely factorized into primes, 2|F, R > 1, gcd(F, R) = 1
and p|R implies p >= B. Define r and s by
R = 2*F*s + r 0 < r < 2*F for e = 1,
R = 2*F*s + r -F < r < F for e = -1.
In order to make Theorems 7 and 19 work, the preliminary conditions we
have to satisfy are
(3) N + e < (B*F + e)*(2*F^2 + e*(|r| - B)*F + 1),
and
(4) either s = 0 or r^2 - 8*e*s is not a square.
The factors 2^n and 3 supply nearly, but usually not quite, all of the
primes required to produce a sufficiently large F. We hope to find a few
small primes p|N, p > 3. But if there are not enough small factors, we
have to establish a suitable B by trial division. Provided (4) holds and
n is not too small, we can always find a B < m/27 < 2^31/27, so the
method is usually quite feasible.
Similar considerations apply to N - 5. We have N - 6 = (2^n +
1)*(m*2^n(2^n - 1) - 6), we apply [5, Theorem 19], and most of the prime
factors of N - 6 come from 2^n + 1.
In our particular case, N = 437850590*(2^3567 - 2^1189) - 6*2^1189 is
divisible by 2^1191*3^2*7^2 and we can set B = 11. On the other hand, N
- 6 is divisible by (2^1189 + 1)*2*17 and (N - 6)/(2^1189 + 1) has no
prime factors p, 17 < p < 3389. The Cunningham tables provide the
complete factorization of 2^1189 + 1.
To find (1) I first prepared a list of m's which had been sieved by
primes up to 2^31 - 1. Then the N - 1 forms were tested for probable
primality using the Fermat test 2^(N-1) = 1 (mod N-1). Reduction modulo
N - 1 is very fast because we can take advantage of the special form of
N - 1 and avoid the need for long division. The performance of the
Fermat test is therefore dominated by the squaring algorithm. Here we
chop the number up into 60-bit digits, zero-pad to 128 digits and use an
all-integer discrete Fourier transform modulo 2^128 + 1.
The Fermat test on a 120 MHz Pentium takes about 3.7 seconds for each
number. For comparison, the test takes about 21.2 seconds using the
school method of squaring together with long division for the
reductions.
The computer also found an additional 38 pairs of twin primes
m*(2^(3567) - 2^1189) - 6*2^1189 +/- 1. These have all been verified and
will be posted to the Titanic Primes database. The most difficult case
was m=428142099, e = -1. Here, N has no small prime factors other than 2
and 3, N/(3*2^1189) is composite, and we need B = 11892869 to satisfy
(3).
I wish to thank A.O.L. Atkin for showing me a general method (of which
(2) is a special case) for devising patterns of three or four numbers
such that the primality of each number can be readily established.
I would also like to thank Harvey Dubner for providing independent
verification of the primes (1).
References
----------
[1] Tony Forbes, "1041-digit [probable] prime triplet", M500, 145 (July
1995), 19.
[2] Tony Forbes, "A small collection of prime k-tuplets", Number Theory
mailing list, January 16, 1996.
[3] Warut Roonguthai, "Large prime quadruplets", Number Theory mailing
list, September 16, 1996.
[4] Harvey Dubner, "Carmichael number record", Number Theory mailing
list, May 1, 1996.
[5] John Brillhart, D. H. Lehmer and J. L. Selfridge, "New primality
criteria and factorizations of 2^m +/- 1", Math. Comp, 29 (1975), 620-
647.
--
Tony