Abuda Posted December 29, 2010 Share Posted December 29, 2010 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. Link to comment https://forums.phpfreaks.com/topic/222874-lucas%E2%80%93lehmer-primality-test/ Share on other sites More sharing options...
sasa Posted December 29, 2010 Share Posted December 29, 2010 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. } ?> Link to comment https://forums.phpfreaks.com/topic/222874-lucas%E2%80%93lehmer-primality-test/#findComment-1152451 Share on other sites More sharing options...
Abuda Posted December 29, 2010 Author Share Posted December 29, 2010 Thanks a million, results are reasonable now. Edit: I just discovered that the algorithm fails horribly for higher values of $i (20 --> 40). :-( Link to comment https://forums.phpfreaks.com/topic/222874-lucas%E2%80%93lehmer-primality-test/#findComment-1152459 Share on other sites More sharing options...
Recommended Posts
Archived
This topic is now archived and is closed to further replies.