Posted in Math on October 31, 2007|
Leave a Comment »

Mersenne prime is a prime in the form of 2

^{p}-1 denoted as M

_{p}, where p must be a prime.

It can be showed by quadratic residue that any divisor q of M

_{p} satisfies that:

1) q = +/-1 (mod 8)

2) q = 1 (mod p)

A deterministic primality test called Lucas-Lehmer test is suitable for testing Mersenne prime.

Let L_{1}=4, L_{n+1}=L_{n}*L_{n}-2, then M_{p} is prime if and only if L_{p-1} = 0 (mod M_{p}).Sufficiency Proof:Let w=2+sqrt(3), v=2-sqrt(3), then L

_{n}=w

^{2n-1}+v

^{2n-1}Say R is a divisor of M

_{p} such that R*R <= M

_{p}.

L

_{p-1}=w

^{2p-2}+v

^{2p-2} = 0 (mod M

_{p})

==> w

^{2p-1}=-1 (mod M

_{p})

==> w

^{2p-1}=-1 (mod R)

==> w

^{2p}=1 (mod R)

So the number of elements in the group {a+b*sqrt(3) (mod R) | a+b*sqrt(3) is invertible}

is at least the order of w, 2

^{p}.

Then R*R-1 >= 2

^{p }==> M

_{p} >= 2p, a contradiction.

Necessity Proof:

Say M

_{p} is prime.

It’s easy to show that 3 is not a quadratic residue of M

_{p} by Legendre sign.

We just need prove w

^{2p-1}=-1 (mod M

_{p}).

It can be proved that for any a+b*sqrt(3):

(a+b*sqrt(3))

^{Mp} = a-b*sqrt(3) (mod M

_{p})

(a+b*sqrt(3))

^{2p} = a*a- 3b*b (mod M

_{p})

Let z=(1+sqrt(3))/sqrt(2) (mod M

_{p}).

z must exist, because 2 is a quadratic residue of M

_{p}.

So z

^{2} = w (mod M

_{p}) ==> w

^{2p-1} = z

^{2p} = (-2/2) = -1 (mod M

_{p}).

Q.E.D.

The generalized Lucas-Lehmer primality test is not necessary.

Namely, prime p may not pass the test for some specific parameters.

GIMPS is a organization searching Mersenne prime by collecting spare

CPU time of computers in the Internet.

Now, they are searching for one million digits Mersenne prime.

Read Full Post »