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