Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Discrete Mathematics
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search