From 70372.1170@CompuServe.COM Thu Feb 13 22:30:20 1997
Date: Thu, 13 Feb 1997 12:23:07 -0500
From: Harvey Dubner <70372.1170@CompuServe.COM>
To: NMBRTHRY@LISTSERV.NODAK.EDU
Subject: Record Primes
Verifying primality of numbers with many thousands of digits is usually
easy because most of them are of the form (k*b^c +/- 1) so that the
factors of N+1 or N-1 are obvious. Loosely speaking, prime verification
requires that N+1 or N-1 must be at least 1/3 factored, that is, the product
of the known factors must exceed 1/3 the number of digits of N.
Repunits ( R(n)=(10^n-1)/9 ) consist of n 1's and can be used to create
large primes with interesting digit patterns. However as the numbers get
larger it is more and more difficult to prove true primality because the
factors of R(n) are not easily found.
A tremendous amount of computer time has been expended finding factors of
repunits, mostly for the Cunningham project. Until recently the largest
repunit that was 1/3 factored was R(9240). Now, R(10080) has been 1/3
factored making it possible to find interesting primes in the Gigantic
prime category (greater than 10,000 digits). Consider the following form,
P = k*R(a*b)/R(b)*.10 + 1
k is a small palindrome with 1 added on the left, and is b digits long. k
repeats a times then 1 is appended. P is a*b+1 digits and is a
palindrome. By varying k the following Palindromic Primes were found and
verified. It took about 100 Cruncher-days to find these primes and about
1.5 days to verify each prime. Without the Crunchers it would have taken
about 150 days to verify each prime on a 486/33 (assuming I had appropriate
software, which I don't).
a*b b k digits comments
----- --- ---------- ------ --------------------------------------
10080 6 110101 10081 palindrome, all 1's and 0's
10080 6 159795 10081 palindrome, odd digits only
10080 10 1165000561 10081 palindrome
10080 10 1816606618 10081 palindrome
10080 10 1818535818 10081 palindrome
Richard Brent, Peter Montgomery, Sam Wagstaff, and their associates found
the last several hundred digits of the 1/3 factored portion of R(10080)
making verification possible.
Unfortunately, we do not have a name for these special primes where
verification depends on 1/3 factorization. I know of others doing work
in this area. This group includes Francois Morain, Chris Caldwell,
Tony Forbes,Wilfrid Keller, Richard Brent. I would appreciate any
information about related work.
If anyone wants technical and sales information about the Cuncher, just ask.
Harvey Dubner