Lucas-Lehmer Test

Lucas-Lehmer Test

ByAbdul Wahab Junaid

The Lucas-Lehmer Test is a specialized algorithm used to determine whether a number of the form (2^p - 1) (a Mersenne number) is prime. It is particularly efficient for testing the primality of Mersenne numbers and is widely used in the search for new Mersenne primes.

The Lucas-Lehmer Test:

The Lucas-Lehmer test works as follows:

  1. Input: A prime number (p).
  2. Initialize: Start with the value (S_0 = 4).
  3. Iterate: Compute the sequence (S_n) using the recursive formula:
    [S_{n} = S_{n-1}^2 - 2 \mod (2^p - 1)] This is done for (n = 1) to (n = p-2).
  4. Final Check: After computing (S_{p-2}), if (S_{p-2} \mod (2^p - 1) = 0), then (2^p - 1) is prime. Otherwise, it is composite.

Steps Explained with an Example:

Let’s test whether (2^7 - 1 = 127) is a Mersenne prime using the Lucas-Lehmer test:

  1. Input: (p = 7), which is prime.
  2. Initialize: Start with (S_0 = 4).
  3. Iterate:
  • Compute (S_1 = S_0^2 - 2 \mod 127 = 4^2 - 2 \mod 127 = 14).
  • Compute (S_2 = S_1^2 - 2 \mod 127 = 14^2 - 2 \mod 127 = 194 \mod 127 = 67).
  • Compute (S_3 = S_2^2 - 2 \mod 127 = 67^2 - 2 \mod 127 = 4489 \mod 127 = 42).
  • Compute (S_4 = S_3^2 - 2 \mod 127 = 42^2 - 2 \mod 127 = 1764 \mod 127 = 111).
  • Compute (S_5 = S_4^2 - 2 \mod 127 = 111^2 - 2 \mod 127 = 12321 \mod 127 = 0).
  1. Final Check: Since (S_5 = 0), (2^7 - 1 = 127) is confirmed to be a prime number.

Key Points:

  • The Lucas-Lehmer test is efficient and only applicable to Mersenne numbers.
  • The test leverages the structure of Mersenne primes, making it faster than general primality tests for this specific type of number.
  • The test is deterministic, meaning it will always correctly determine the primality of a Mersenne number.

Summary:

The Lucas-Lehmer test is the go-to method for proving the primality of Mersenne numbers. If you have a candidate Mersenne prime (2^p - 1), and (p) is prime, running the Lucas-Lehmer test will efficiently tell you if (2^p - 1) is a prime number.

Discover more from Science blog by awjunaid

Subscribe to get the latest posts sent to your email.

Leave a Reply