mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2005-01-16, 06:25   #1
leith
 

24×547 Posts
Question 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
  Reply With Quote
Old 2005-01-16, 09:00   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

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.
cheesehead is offline   Reply With Quote
Old 2005-01-17, 01:47   #3
ColdFury
 
ColdFury's Avatar
 
Aug 2002

5008 Posts
Default

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.
ColdFury is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lucas-Lehmer test Mathsgirl Information & Answers 23 2014-12-10 16:25
lucas-lehmer theorem Robot2357 Math 6 2013-06-15 03:10
lucas lehmer outstretch science_man_88 Miscellaneous Math 7 2010-07-14 12:35
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32
Lucas-Lehmer 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.