The remaining potential factors are tested using the powering algorithm above. This process eliminates roughly 95% of potential factors. Also, bits representing potential factors of 3 or 5 mod 8 areĬleared. The sieve then eliminates any potential factors that are divisible by prime numbers below 40,000 or so. The GIMPS factoring code creates a modified sieve of Eratosthenes with each bit representing a potentialĢkp+1 factor. Finally, an efficient program can take advantage of the fact that any potential factor q must be prime. One very nice property of Mersenne numbers is that any factor q of 2 p-1 must be of the form 2kp+1. Since we've shown that 47 is a factor, 2 23-1 is not prime. Value by 2, then compute the remainder upon division by 47. Starting with 1, repeatedly square, remove the top bit of the exponent and if 1 multiply squared Convert the exponent 23 to binary, you get 10111. There are very efficient algorithms for determining if a number divides 2 P-1. The next step is to eliminate exponents by finding a small factor. Thus, the first step in the search is to create a list of prime exponents to test. That if 2 P-1 is prime, then P must be a prime. Mersenne numbers are of the simple form 2 P-1, where P is the exponent to be tested. Is there a better method than Lucas-Lehmer?.I will not go into too much mathematical detail but will try to provide pointers instead. As I am more a computer programmer than a mathematician,
This page discusses some of the math behind and the computer algorithms used in an efficient search for Mersenne primes. Last updated: JMathematics and Research Strategy
0 kommentar(er)
