C++: Lucas-Lehmer Test

Posted on September 1, 2017April 1, 2018 by TFE Times

Bjarne-stroustrup

Lucas-Lehmer Test: for $p$ an odd prime, 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$ .

The following programs calculate all Mersenne primes up to the implementation’s maximum precision, or the 47th Mersenne prime. (Which ever comes first).

#include <iostream>
#include <gmpxx.h>
 
static bool is_mersenne_prime(mpz_class p)
{
        if( 2 == p )
                return true;
        else
        {
                mpz_class s(4);
                mpz_class div( (mpz_class(1) << p.get_ui()) - 1 );
                for( mpz_class i(3);  i <= p;  ++i )
                {
                        s =  (s * s - mpz_class(2)) % div ;
                }
 
                return ( s == mpz_class(0) );
        }
}
 
int main()
{
        mpz_class maxcount(45);
        mpz_class found(0);
        mpz_class check(0);
        for( mpz_nextprime(check.get_mpz_t(), check.get_mpz_t());
             found < maxcount;
             mpz_nextprime(check.get_mpz_t(), check.get_mpz_t()))
        {
                //std::cout << "P" << check << " " << std::flush;
                if( is_mersenne_prime(check) )
                {
                        ++found;
                        std::cout << "M" << check << " " << std::flush;
                }
        }
}

Output:

(Incomplete; It takes a long time.)

 M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213 M19937 M21701 M23209 M44497

Content is available under GNU Free Documentation License 1.2.

Related