Lucas-Lehmer primality test
The
Lucas-Lehmer primality test is a method of testing the
primality of some number
n based on testing whether some other number is
primitive modulo
n.
If there exists some a less than n and greater than 1 such that firstly an-1≡1 and then
-
where
qi represents the prime factors of
n-1, then
n is prime, since this is the requirement for
a to be primitive mod
n, resulting then the
multiplicative order of
a mod
n to be
n-1.
For example, take n=71, n-1=70=(2)(5)(7).
Take a=2 first:
-
This doesn't show that the order of 2 mod 70 is 1 because some factor of 70 may also work above. So check 70's factors:
-
-
So 2 is primitive mod 71 and thus 71 is prime.
If the factors of n-1 are not easily obtained, this method becomes difficult to use as these factors must be obtained in the a(n-1)/qi terms.
See also