English
English
In number theory, the Lucas-Lehmer primality test is an efficient method to determine whether a Mersenne number is prime. In this article, we will use PHP and the GMP extension (GNU Multiple Precision Arithmetic Library) to implement the Lucas-Lehmer test, providing complete code examples.
The Lucas-Lehmer test is specifically designed to check if numbers of the form M = 2^n - 1, called Mersenne numbers, are prime, where n is a positive integer greater than 1. The test relies on the Lucas-Lehmer sequence, iteratively calculating each element and checking if the last element is zero to determine primality.
PHP's built-in functions cannot handle extremely large integer calculations, so the GMP extension is required. You can install PHP with GMP enabled or activate the GMP extension in an existing PHP environment.
function lucasLehmerTest($n)
{
$s = '4';
$m = gmp_pow('2', $n) - '1';
for ($i = 1; $i < $n - 1; $i++) {
$s = gmp_mod(gmp_pow($s, 2) - 2, $m);
}
if ($s == '0') {
return true;
}
return false;
}Explanation:
The function calculates 2^$n - 1 using gmp_pow to get $m, then iterates $n-1 times to compute the Lucas-Lehmer sequence. The final element determines the number's primality.
$exponents = [2, 3, 5, 7, 13, 17];
foreach ($exponents as $exponent) {
$result = lucasLehmerTest($exponent);
if ($result) {
echo "2^$exponent - 1 is a prime number.";
} else {
echo "2^$exponent - 1 is not a prime number.";
}
}Explanation:
An array $exponents contains multiple exponent values. We loop through each exponent with foreach, call the Lucas-Lehmer test, and output whether each Mersenne number is prime.
Using PHP with the GMP extension, it's easy to implement the Lucas-Lehmer primality test and check large integers for primality. For large Mersenne numbers, the Lucas-Lehmer algorithm is efficient and can quickly determine primality. The provided code examples serve as a practical reference.
