Finding and Factoring Large or Mersenne Primes

Date: 02/22/98 at 03:06:33
From: Nathan Cypra
Subject: Finding Large Primes (Mersenne Primes), Efficient 
Factorization

I have two questions:

1. How do you find extremely large primes (Mersenne Primes) and how 
do you tell if they are prime?
2. What is the most efficient way of finding prime factors?

I have come up with no possible solutions and am completely stumped.   
Thanks.

Date: 03/03/98 at 12:45:12
From: Doctor Nick
Subject: Re: Finding Large Primes (Mersenne Primes), Efficient 
Factorization

Hello Nathan -

For your first question, you'll want to take a look at what's known as 
the Lucas-Lehmer test (L-L test). This is the best way for checking if 
a large Mersenne number is prime. 

A Mersenne number is a number of the form 2^n-1. That is, it's any 
number that's one less than a power of 2. Let M(n) = 2^n -1.

The L-L test says that all we have to do to see if M(n) is prime is to 
check if it divides evenly into a certain other number. That "certain 
other number" is generated in the following way. We make a sequence 
s(m) starting with s(0) = 4 by squaring and subtracting 2 to get to 
the next number. So,

   s(1) = s(0)^2 -2 = 4^2 - 2 = 14.
   s(2) = s(1)^2 -2 = 14^2 - 2 = 194.
   s(3) = s(2)^2 -2 = 194^2 - 2 = 37634.
   s(4) = s(3)^2 - 2 = 37634^2 -2 = 1416317954.
   s(5) = s(4)^2 - 2 = 1416317954^2 - 2 = 2005956546822746114.

And so on. Notice the numbers get big really fast.

Now, the L-L test says that

   M(n) is prime if (and only if) M(n) evenly divides s(n-2).

So for instance,

   M(3) = 2^3 - 1 = 7 is prime because 7 evenly divides 14, which is 
s(3-2) = s(1), since 14/7 = 2.

   M(4) = 2^4 - 1 = 15 is not prime because 15 does not evenly divide 
194, which is s(4-2) = s(2), since 194/15 = 12 + 14/15.

   M(5) = 2^5 - 1 = 31 is prime because 31 evenly divides 37634, which 
is s(5-2) = s(3), since 37634/31 = 1214.

Now, the numbers s(m) get big really fast, and that could be a problem
for our calculations. It turns out we can improve things by doing 
what's called "reducing modulo M(n)" at each step.  What that means is 
that if s(m) is bigger than M(p) at any step, we can subtract M(n) 
until it is less than M(n), but still bigger than 0. For example, to 
reduce 29 modulo 6, we subtract 6 from 29 repeatedly until we get less 
than 6:

   29 - 6 = 23 -> 23 - 6 = 17 -> 17 - 6 = 11 -> 11 - 6 = 5.

So 29 reduced modulo 6 is 5. Another way to get there, instead of 
repeatedly subtracting, is to divide and take the remainder: dividing 
6 into 29 gives 4 with a remainder of 5.

Now getting back to our test, suppose we want to see if

   M(5) = 31 = 2^5 - 1

is prime.

We generate the s(m), but reduce by 31 as we go. So we get

   s(0) = 4.
   s(1) = 4^2 - 2 = 14.
   s(2) = 14^2 - 2 = 194 = 31*6 + 8 (so 194 reduced modulo 31 is 8), 
so we have s(2) = 8.
   s(3) = 8^2 - 2 = 62 = 31*2 (so 62 reduced modulo 31 is 0), so we 
have s(3) = 0.

Since 31 divides 0 (everything divides 0), 31 is prime.

Let's do another example.
Suppose we want to see if M(7) = 127 = 2^7 - 1 is prime. We generate 
the s(m), each time reducing modulo 127. We get

   s(0) = 4.
   s(1) = 14.
   s(2) = 194 -> 67 (since 194 - 127 = 67).
   s(3) = 67^2 - 2 = 4487 -> 42 (since 4487 = 35*127 + 42).
   s(4) = 42^2 - 2 = 1762 -> 111 (since 1762 = 13*127 + 111).
   s(5) = 111^2 - 2 = 12319 -> 0 (since 12319 = 97*127).

Again, since M(7) divides s(5), M(7) is prime. You can see here that 
reducing modulo 127 kept the numbers we had to deal with from getting 
too large.  

One more example of the L-L test. To check if M(6) = 2^6 - 1 = 63 is 
prime, we have

   s(0) = 4.
   s(1) = 14.
   s(2) = 194 -> 5.
   s(3) = 5^2 - 2 = 23.
   s(4) = 23^2 - 2 = 527 -> 23.

Since 63 doesn't divide 23, we can tell that 63 is not prime.

By the way, it can be shown that if M(n) is prime, then n itself is 
prime. So you don't need to check, for instance, M(8) - we know it's 
not prime since 8 isn't prime.  

For your second question, have a look at 

   http://mathforum.org/dr.math/faq/faq.prime.num.html   

If you want to efficiently factor numbers that aren't too big, the 
fastest way (and it's pretty fast) is to test for divisibility by 
primes. To do that well, you'll need a table of primes, which you can 
generate using the Sieve of Eratosthenes (it's described at the web 
page above). If you want to find the prime factors of n, try dividing 
it by 2, then 3, then 5, etc., running through the primes.  At each 
step, if the prime divides the number, replace that number with the 
result of that division. This will speed things up. For example, if we 
want to find the prime divisors of 30, we start by dividing by 2, 
which gives us 15, then 3, which gives 5, which is itself prime. Hence 
the prime factors of 30 are 2, 3 and 5.

Another example: take 98. It's divisible by 2. We get 98/2 = 49. Now 
we try to divide 3 into 49: we get a remainder of 1, so 3 doesn't 
divide 49. Now try to divide 5 into 49: we get a remainder of 4, so 5 
doesn't divide 49. Now try to divide 7 into 49: we find it divides 
evenly and gives us 7. We know 7 is prime, so we're done.  The result 
is that 98 = 2 * (7^2).

Once you have a table of primes to work from, this method is probably
fast enough unless the number you're trying to factor is pretty large 
(say, at least 10^12). There are ways to check if a number is prime, 
though, to save you the trouble of trying all those prime factors. 
There are tests like the Lucas-Lehmer test that can be applied to 
numbers of any form.

Now, for really large numbers, there are very sophisticated factoring
methods, such as the Number Field Sieve. These methods work on numbers 
of all sizes, but for small numbers, there are faster methods. 

Your questions are part of the area of mathematics known as number 
theory. You can probably find books on number theory in a local 
library which you might enjoy.

Have fun,

-Doctor Nick, The Math Forum
 http://mathforum.org/dr.math/