sumthing is worong with my Lucas-Lehmer C implementation

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

[cheesehead]

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.

[ColdFury]

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.