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