Lucas–Lehmer Primality Test

[Abuda]

Hello,

 

Here's the Wikipedia Page explaining how to test a number for primality using the mentioned algorithm.

 

In Short:

 

[tex]

M_p = \text2^p - 1

[/tex]

 

[tex]

s_i=    \begin{cases}    4 & \text{if }i=0;    \\    s_{i-1}^2-2 & \text{otherwise.}    \end{cases} 

[/tex]

 

[tex]\color{blue} M_p[/tex] is a prime if and only if:

 

[tex]s_{p-2}\equiv0\pmod{M_p}.[/tex]

 

I tried to interpret that to PHP as the following:

 

<?php
for($i = 2; $i < 10; $i++) { // testing from (2^2 - 1) to (2^10 - 1)

$s = 4;
$m = pow(2, $i) - 1; // define M

if($i > 2){ // Start computing $s only if ($i - 2) > 0, otherwise $s remains equal to 4.
for($j = 1; $j <= $i - 2; $j++) { // Find S(p-2)
$s = (($s * $s) - 2);
}
}

if($s % $m == 0) { echo "<br />$m"; } // Print out detected prime number.

}
?>

 

Here's the output:

7

31

255

511

The code is already messing up since 2 of those results are not prime numbers.

Any idea where I might have gone wrong?

 

Thanks.

[sasa]

number $s is overflow integers (try to echo it)

to fix it use modulo operator in calculating $s

<?php

for ($i = 2; $i < 10; $i++) { // testing from (2^2 - 1) to (2^10 - 1)
    $s = 4;
    $m = pow(2, $i) - 1; // define M
    if ($i > 2) { // Start computing $s only if ($i - 2) > 0, otherwise $s remains equal to 4.
        for ($j = 1; $j <= $i - 2; $j++) { // Find S(p-2)
            $s = (($s * $s) - 2) % $m;
        }
    }
    if ($s == 0) {
        echo "<br />$m";
    } // Print out detected prime number.
}
?>

[Abuda]

Thanks a million, results are reasonable now.

 

Edit:

I just discovered that the algorithm fails horribly for higher values of $i (20 --> 40). :-(