Lucas-Lehmer Test (C++)

The Test

The Lucas-Lehmer test is a primality test used specifically to determine whether a Mersenne number is prime. A Mersenne number has the form:

$$M_p = 2^p - 1$$

The test works by computing a sequence $s_0, s_1, s_2, \ldots$ where:

$s_0 = 4$
$s_{i+1} = s_i^2 - 2 \pmod{M_p}$

If $s_{p-2} \equiv 0 \pmod{M_p}$, then $M_p$ is prime.

Why It Matters

This is the hyper-efficient checking mechanism that the Great Internet Mersenne Prime Search (GIMPS) uses. Without it, we wouldn't have the computational power to verify such enormous primes.

You can see all known Mersenne Primes on our Mersenne Primes page.

C++ Implementation

This code uses the GMP (GNU Multiple Precision) library to handle the enormous numbers involved. Try 19 first - it should confirm that $2^{19} - 1 = 524287$ is a Mersenne prime.

C++ (with GMP)

#include <iostream>
#include <gmp.h>

bool is_prime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i <= n / i; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

bool lucas_lehmer_test(int p) {
    if (p == 2) return true; // 2^2 - 1 = 3 is a Mersenne prime
    if (!is_prime(p)) return false; // If p is not prime, 2^p - 1 is not a Mersenne prime

    mpz_t s;
    mpz_init_set_ui(s, 4); // Initialize s to 4
    mpz_t M;
    mpz_init(M);
    mpz_ui_pow_ui(M, 2, p); // M = 2^p
    mpz_sub_ui(M, M, 1); // M = M - 1, so M = 2^p - 1

    for (int i = 0; i < p - 2; i++) {
        mpz_pow_ui(s, s, 2); // s = s^2
        mpz_sub_ui(s, s, 2); // s = s - 2
        mpz_mod(s, s, M); // s = s mod M
    }

    // If s == 0 then 2^p - 1 is prime
    bool is_mersenne_prime = (mpz_cmp_ui(s, 0) == 0);

    // Clear the mpz_t variables
    mpz_clear(s);
    mpz_clear(M);

    return is_mersenne_prime;
}

int main() {
    int p;
    std::cout << "Enter a prime number p to test if 2^p - 1 is a Mersenne prime: ";
    std::cin >> p;

    bool result = lucas_lehmer_test(p);
    if (result) {
        std::cout << "2^" << p << " - 1 is a Mersenne prime." << std::endl;
    } else {
        std::cout << "2^" << p << " - 1 is not a Mersenne prime." << std::endl;
    }

    return 0;
}

Compiling & Running

Terminal

# Install GMP first
# macOS: brew install gmp
# Ubuntu: sudo apt install libgmp-dev

# Compile (include -lgmp flag!)
g++ -o lucas lucas.cpp -lgmp

# Run
./lucas

# Try these known Mersenne prime exponents:
# 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127...

First Mersenne Primes

The first several Mersenne primes are:

$M_2 = 2^2 - 1 = 3$
$M_3 = 2^3 - 1 = 7$
$M_5 = 2^5 - 1 = 31$
$M_7 = 2^7 - 1 = 127$
$M_{13} = 2^{13} - 1 = 8191$
$M_{17} = 2^{17} - 1 = 131071$
$M_{19} = 2^{19} - 1 = 524287$

Related Resources

GIMPS - Great Internet Mersenne Prime Search

Join the distributed computing project searching for new Mersenne primes.

mersenne.org Project

All Known Mersenne Primes

Complete list of all 51 known Mersenne prime exponents.

dumbprime.com Reference