46931635677864055013377 divides 2^(2^31)+1 On Thursday, 12. April 2001, a factor of the 31st Fermat number (F_31) was discovered, thus proving that F_31 is composite. Since the primality proof by Crandall, Mayer & Papadopoulos, which showed F_24 to be composite, F_31 was the smallest Fermat number whose primality status was unknown. That distinction now goes to F_33; a detailed list of known factors and primality status of Fermat numbers can be found at http://www.prothsearch.net/fermat. The factor was found by Alexander Kruppa on one of five AMD Thunderbird 1GHz computers located at the Technische Universitaet Muenchen. The program that was used is MFAC, written by Tony Forbes. To find a divisor of F_m, MFAC computes a list of numbers of the form (Q*k + h)*2^m + 1, where Q is 4*(2*3*5*..*q) and q is a small prime. In our case, q=11 was used. MFAC chooses h so that gcd(h*2^e + 1, Q) = 1. Composite numbers are eliminated from the list by sieving all multiples of small primes, in our case all primes <= 611999. Each remaining candidate factor d is then tested by verifying the condition 2^2^n == -1 (mod d), for n <= m + x, where x is the greatest integer so that 2^(x+2) | (Q*k + h). It took about 2 weeks to find the factor on the five available machines. The discoverer had checked the range up to k=10^9*2310, where k*2^33+1 is the candidate divisor, on different hardware before (as have other searchers before him) and then assigned subintervals of size 2*10^8*2310 to each machine in turn. At k=5463561471303, the factor was found. At that point, about 2.3*10^11 trial divisions with candidate divisors had been performed, while about 9*10^11 candidate divisors had been eliminated by sieving. The cofactor has 646456971 decimal digits, its primality status is unknown. We would like to thank the staff of Lehrstuhl XIII, Systemarchitektur und Betriebssysteme, an der Technischen Universitaet Muenchen, in particular Christian Rehn, for granting use of their computer hardware. Alexander Kruppa would like to dedicate the discovery to his father, Andreas Kruppa, who passed away while Alexander was making a first contact to Fermat number research by helping with the computation for the F_24 compositeness proof. Alexander Kruppa [EMAIL PROTECTED] Tony Forbes [EMAIL PROTECTED] _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
