20050116, 06:25  #1 
2^{4}×547 Posts 
sumthing is worong with my LucasLehmer C implementation
Code:
bool Lucas_Lehmer_Test(unsigned long p) { // check if p is an odd prime /*if(p % 2 == 0) return false; for(unsigned long c = 3; (c * c) <= p; c += 2) if (p % c == 0) return false;*/ unsigned long int mp = (1 << p)  1; // 2^p  1 unsigned long s = 4; // s := 4 for(unsigned long i = 3; i <= p; i++) // for i from 3 to p do { s = ((s * s)  2) % mp; // s := s^2  2 mod 2^p  1 } return !s; // if s == 0 then // 2p1 is prime // else // 2p1 is composite } for numbers 1 to 31 inclusive so anyone know why this is not working 
20050116, 09:00  #2 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
Unsigned long is 32 bits, right?
When p = 17 (or more), mp = 2^171 (or more). So s could reach a value greater than 2^16. If so, then in your s = ((s * s)  2) % mp step, the s*s intermediate value could overflow 32bits. 
20050117, 01:47  #3 
Aug 2002
500_{8} Posts 
Also make sure the value is not negative when you're doing the modular reduction. The mod operation in C has undefined behavior for negative integers.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
LucasLehmer test  Mathsgirl  Information & Answers  23  20141210 16:25 
lucaslehmer theorem  Robot2357  Math  6  20130615 03:10 
lucas lehmer outstretch  science_man_88  Miscellaneous Math  7  20100714 12:35 
LucasLehmer Test  storm5510  Math  22  20090924 22:32 
LucasLehmer  Dougal  Information & Answers  9  20090206 10:25 