n=<number to factor>
curr=sqrt(n)
if( even(curr) ) curr++; // Make sure curr is odd

while( curr > 0 ) {
if( curr is not divisible by 3, 5, 7, 11, 13, 15, 17, 19, 21 or 23 ) {
rem=n%curr;
if( rem == 0 ) {
print out curr;
exit;
}
}
curr-=2;
}

In dealing with Mersenne numbers, it is easy to prove that if 2P-1 is prime, then P must be a prime. Thus, the first step in the search is to create a list of prime exponents to test.


--------------------------------------------------------------------------------

Trial Factoring

--------------------------------------------------------------------------------

The next step is to eliminate exponents by finding a small factor. There are very efficient algorithms for determining if a number divides 2P-1. For example, let's see if 47 divides 223-1. Convert the exponent 23 to binary, you get 10111. Starting with 1, repeatedly square, remove the top bit of the exponent and if 1 multiply squared value by 2, then compute the remainder upon division by 47.

Remove Optional
Square top bit mul by 2 mod 47
------------ ------- ------------- ------
1*1 = 1 1 0111 1*2 = 2 2
2*2 = 4 0 111 no 4
4*4 = 16 1 11 16*2 = 32 32
32*32 = 1024 1 1 1024*2 = 2048 27
27*27 = 729 1 729*2 = 1458 1

Thus, 223 = 1 mod 47. Subtract 1 from both sides. 223-1 = 0 mod 47. Since we've shown that 47 is a factor, 223-1 is not prime.

One very nice property of Mersenne numbers is that any factor q of 2P-1 must be of the form 2kp+1. Furthermore, q must be 1 or 7 mod 8. A proof is available. Finally, an efficient program can take advantage of the fact that any potential factor q must be prime.

Lucas_Lehmer_Test(p):
s := 4;
for i from 3 to p do s := s2-2 mod 2p-1;
if s == 0 then
2p-1 is prime
else
2p-1 is composite;The theory for this test was initiated by Lucas in the late 1870's and then made into this simple test about 1930 by Lehmer