mersenneforum.org sumthing is worong with my Lucas-Lehmer C implementation
 Register FAQ Search Today's Posts Mark Forums Read

 2005-01-16, 06:25 #1 leith   24×547 Posts sumthing is worong with my Lucas-Lehmer 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 // 2p-1 is prime // else // 2p-1 is composite } ive been tryin for ages to get this to work but it only outputs the numbers 3, 5, 7, 13 for numbers 1 to 31 inclusive so anyone know why this is not working
 2005-01-16, 09:00 #2 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 22×3×641 Posts Unsigned long is 32 bits, right? When p = 17 (or more), mp = 2^17-1 (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 32-bits.
 2005-01-17, 01:47 #3 ColdFury     Aug 2002 5008 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Mathsgirl Information & Answers 23 2014-12-10 16:25 Robot2357 Math 6 2013-06-15 03:10 science_man_88 Miscellaneous Math 7 2010-07-14 12:35 storm5510 Math 22 2009-09-24 22:32 Dougal Information & Answers 9 2009-02-06 10:25

All times are UTC. The time now is 14:38.

Sun Apr 18 14:38:55 UTC 2021 up 10 days, 9:19, 0 users, load averages: 1.71, 1.66, 1.58