# Lucas Lehmer Primality Test

I have coded the Lucas-Lehmer primality test following Wikipedia's description. I used the mod 2^n - 1 suggested in the article but was wondering if there were any other improvements I could make. I am using the GMP library for arbitrary precision integers. The program asks an integer n as input, then checks every Mersenne number M(i) for all i less than n. n = 10000 takes around 25 seconds on my computer.

#include <gmp.h>
#include <stdio.h>

_Bool mersenne_prime(unsigned long exponent) {
mpz_t sequence, number, temp;
// Intialize variables
mpz_init_set_ui(sequence, 4);
mpz_init(temp);
// Set number to 2^n - 1
mpz_init_set_ui(number, 1);
mpz_ui_pow_ui(number, 2, exponent);
mpz_sub_ui(number, number, 1);
// Repeat exponent-2 times
for (unsigned long counter = exponent; --counter - 1;) {
mpz_mul(sequence, sequence, sequence);
// Modulus suggested by wikipedia
while (mpz_cmp(sequence, number) > 0) {
// Most significant bits of sequence
mpz_div_2exp(temp, sequence, exponent);
// Least significant bits of sequence
mpz_mod_2exp(sequence, sequence, exponent);
}
// Erratic case
if (mpz_cmp(number, sequence) == 0) {
mpz_set_ui(sequence, 0);
}
mpz_sub_ui(sequence, sequence, 2);
}
// sequence == 0 means prime
_Bool result = mpz_sgn(sequence) == 0;
// Clear variables
mpz_clears(sequence, number, temp, NULL);
return result;
}

int main() {
mpz_t num;
unsigned long limit;
mpz_init_set_ui(num, 3);
// Get limit
scanf("%lu", &limit);
printf("Searching for Mersenne primes...\nM2 is prime!\n");
while (mpz_cmp_ui(num, limit) < 0) {
unsigned long num_ui = mpz_get_ui(num);
if (mersenne_prime(num_ui)) {
printf("M%lu is prime!\n", num_ui);
}
mpz_nextprime(num, num);
}
// Clear num
mpz_clear(num);
return 0;
}