All,
Here is version 1.1 of the FAQ.
I corrected a few typos. I then added 500 more of them when I added the LL
section. The LL section needs major revision, and clarification, especially
the repeating LL part. I think we might add a section on FFT, and DWT, though
I don't know enough about math to do it. I also like the idea of a history
section. I have read something about the history of GIMPS, as well as some of
the list's archives, but I have only been here since February...
-Lucas Wiman
Q: What are mersenne numbers?
A: Mersenne numbers are numbers of the form 2^p-1, (2 to the pth power minus 1)
Generally, when mersenne numbers are mentioned, mersenne numbers with prime
exponents are what is actually meant.
Q: What is a mersenne prime?
A: A mersenne prime is a mersenne number Mp which is prime. P must itself
be prime, otherwise Mp has a trivial factorization.
Q: How can we prove these massive numbers are prime?
A: We can use a method known as the Lucas-Lehmer (LL) test. It works like
this:
For p odd, the Mersenne number 2^p-1 is prime if and only if 2^p-1 divides
S(p-1) where S(n+1) = S(n)^2-2, and S(1)=4
Q: Won't those S(n) get huge very quickly? How can we check whether 2^p-1
divides S(p-1)?
A: Yes, and with the magic of modular arithmetic.
Modular arithmetic deals with remainders from long division (like you did in
grade school). We say that if a==b mod c if a and b both have the same
remainder when divided by c (which is read "a is congruent to b mod c," on
paper, we would write this a=b mod c where = has 3 horizontal lines.)
Another way to think of this is (a-b)/c is an integer. Here are the most
important things involving modular arithmetic:
(1) if a==0 mod c then a is divisable by c
(2) (a+b) mod c = (a mod c)+(b mod c) mod c
(3) (a*b) mod c = (a mod c)*(b mod c) mod c
(4) a^b mod c = (a mod c)^b mod c
Now, we can define a new series (call it s(n)) where
s(1)=4, and s(n+1)=s(n)^2-2 mod (2^p-1).
Using these rules of modular arithmetic, we can see that 2^p-1 divides S(p-1)
if and only if s(p-1)=0. Therefore, the numbers we work with can never get
above (2^p-1)^2 (no bigger than 2^p-1 with some cleverness).
Q: If the remainders of the LL series ever repeated, we could skip the rest of
the test, because it could never equal 0. Why don't we test for this?
A: Well, a simple heuristic argument involves simple probabilities.
Think about this, for the recurrance to be important, it must occurr in the
first p-1 iterations. *BUT* there are 2^p-1 possible remainders, that means
that the that the probability of such a recurance is aproximatly (p-1)/(2^p-1).
These odds are better than suddenly being transported to Mars by quantum
fluctuations, but worse than winning all the lotteries in the world
simultaniously. (well, of course depending upon the size of p, when it gets
large enough, the probability can get arbitrarily close to zero)
Here's another way to think of it:
as the S-sequence is defined above,
S(n)=L(2^n) (where L(n)=(2+sqrt(3))^n+(2-sqrt(3))^n)
Now suppose for instance the recurance occurred between L(2^(n-3)) and
L(2^(n-2)) - which, even assuming the "first" recurrence is equally likely
anywhere, would occur with probability 50%. The S-sequence would not even see
it.
And furthermore:
We can illustrate working modulo M23 = 8388607 = 47 * 178481.
3 is a quadratic reside modulo 47 (e.g, 12^2 == 3 mod 47),
so 2 + sqrt(3) is in the base field of order 47.
The multiplicative order of 2 + sqrt(3) divides 47-1, and turns out to be 23.
3 is a quadratic nonresidue modulo q = 178481. The order of 2 + sqrt(3)
divides q + 1 = 178482 = 2 * 3 * 151 * 197 and turns out to be 178482.
The least common multiple of these orders is
2 * 3 * 23 * 151 * 197. So L(2 * 3 * 23 * 151 * 197) == L(0) mod M23.
For the L sequence, we need two powers of 2 whose difference is
divisible by 2 * 3 * 23 * 151 * 197.
The orders of 2 modulo 3, 23, 151, 197 are 2, 11, 15, 196, respectively.
The order of 2 modulo 3 * 23 * 151 * 197 is the least common multiple
of these orders, namely 2^2 * 3 * 5 * 7^2 * 11 = 32340.
To include a factor of 2, we need L(2^32341) == L(2^1) mod M23.
That is, S(32341) == S(1) mod M23.
This is far more than 23 LL steps before the sequence repeats.
(Thankyou, Chris Nash, and Peter Lawrence Montgomery)
Q: Wouldn't it make more sense to record the S (without taking the remainder)
series, and save the result, thereby saving alot of work?
A: No. The number of digits in the S series doubles with each iteration.
thus by the 270th iteration, you've run out of protons in the universe to
store it in.
Q: If some s(n) is larger than half the size of the mersenne number, wouldn't
it make sense to take 2^p-1-s(n) and square that and subtract 2?
A: This would usually take off one bit. When there's seven million of them,
it really doesn't make much difference, and it would take longer to determine
if s(n) is greater than 2^(p-1) than the time gained from 1 or 2 bits.
Furthermore, this would slow down all the other iterations, which is
something we really don't want...
Q: How is factoring done on mersenne numbers?
A: We check a potential factor n of Mp by seeing if 2^p (mod n)=1
Q: But doesn't this mean using very large numbers, and computing 2^p?
A: Not at all, there is a very simple algorithm for finding a^b (mod c),
and here's how it works:
we set res=1,
then multiply res by a^(2^n) mod c whenever the nth binary digit of b is 1
a^(2^n) mod c is relativly easy to calculate through repeated sqaring of
a mod c.
Q: That's still a lot of factors!!!
A: Well we can significantly reduce the number of factors through some
simple theorems which state that:
(1) any factor of 2^p-1 must be of the form 2*k*p+1 for k>0
(2) any factor of 2^p-1 must be of the form 8*n+1 or 8*n-1 for n>0
(3) the smallest factor (other than 1) of any number must be prime
Theorem (1) reduces the number of cases to 1/(2*p) of all numbers.
Theorem (2) reuduces those to 1/2 of those.
Theorem (3) can reduce the factors down to only prime numbers, but that takes
too much time.
It is generally better simply to sieve out potential factors with very small
factors.
Q: But how can you sieve out small factors from potential factors?
A: Well, I think an example would be most illistrative.
Say we want to seive out all potential factors divisable by 3, 5, or 7.
Well we can create an array of 3*5*7=105 elements, with all elements set
to 1 (we'll call this array N). Then elementate all N[i] such that i is
divisable by 3, 5, or 7. Then we can keep a running value of 2*k*p+1 mod 105
then if N[2*k*p+1 mod 105]=0 we skip that factor, and go on to the next one.
Q: How much does all this actually help?
A: The sieving for small factors (up to 17), as well as theorem (2)
leaves only about 32% of potential factors of the form (2*k*p+1).
Q: Wouldn't it be more effiecient to check prime numbers and see if they
divide as certain 2^p-1?
A: Yes and no. It is theoretically more effiecient to do this, however
this also produces uninteresting (and relativly useless) results for where p
itself is composite.
Q: A prime number cannot divide more than one mersenne number, so why not
create a table of all the prime numbers which divide mersenne numbers so
as not to duplicate work?
A: This isn't really workable because it would take longer to check the
table than it would to just check the factor.
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
