Do I just suck at implimenting psuedo code?

Cogman

Lifer
Sep 19, 2000
10,283
134
106
So, I have an assignment that I thought was going to be fairly straight forward. I had to basically implement a primality test. I'm given the psuedo code and everything for, yet the test doesn't seem to work correctly.

Here is the psuedo code
isProbablyPrime
Input: p, a candidate prime, and k >= 1 determining the maximum error probability to be 2^-k.
Output: whether or not p is probably prime.
1. If p is even, return (p == 2).
2. Select a1; a2; : : : ; ak randomly in Z+
p .
2
3. For each i from 1 to k:
4. Compute ai^p-1 mod p and return false if different from 1.
5. Let p - 1 = st where s is odd and t = 2^h is a power of 2.
6. Compute the sequence ai^(s*2^0) ; ai^(s*2^1) ; ai^(s*2^2) ; : : : ; ai^(s*2^h) modulo p.
7. If some element of this sequence is not 1,
find the last element that is not 1 and return false if that element is not -1.
8. All tests have passed at this point, so return true.

Sounds fairly straight forward, right? So here is the code I generated (c++)

template <class T>
bool isProbablyPrimeBroken(T number, T numTests)
{
if (number % 2 == 0)
return number == 2;

// Generate S and the max power for later use, no need to loop on it.
T power = 0;
T m = number - 1;

// Determine the largest power of 2 in prime candidate.
while (m % 2 == 0)
{
++power;
m >>= 1;
}
T s = (number - 1) / fastPow(mpz_class(2), power);

for (T i = 0; i < numTests; ++i)
{
T numb = primePool[rand() % primePool.size()];

T modCheck = modexp(numb, T(number - 1), number);
if (modCheck != 1)
{
return false;
}

for (T i = 0; i < power; ++i)
{
modCheck = modexp(numb, T(fastPow(T(2), i) * s), number);
if ((modCheck != 1) && (modCheck != -1))
{
return false;
}
}
}
return true;
}

It isn't a terrible test, however, what bothers me is this portion of the handout
This probabilistic primality algorithm has one-sided error probability. When the algorithm returns false, the
input must be composite. When true is returned, the input could be prime or composite. Thus an incorrect
answer can only occur when the input is a composite number.

As I have implemented it, it is NOT one sided, 97 for example will return as a non-prime when in fact it is prime.

From my reading on primality tests, I came across the Miller-Rabin Test. From what I can tell, it is very similar to the one described in the psuedocode, but just different enough to make it not the same thing. Am I going crazy? Does the psuedo-code describe the Miller-Rabin test and I just implemented it wrong, or is the psuedo-code just wrong?

(It should be noted that my modexp, and fastExp functions both work perfectly. modexp(number, power, modulus) does number ^ power % modulus, fast ;). and fastExp just does number^power fast as well (using binary expansion).)
 

Ken g6

Programming Moderator, Elite Member
Moderator
Dec 11, 1999
16,480
4,326
75
1. What is "(number - 1) / fastPow(mpz_class(2), power);" calculating? Edit: I see, s*t=P-1? Isn't "m" == s?
2. What type is T? Int32? BigInt? Float/double? (The right answer is either Int32, Int64, or BigInt.)
3. Can you break your tests up and see which one is failing?
 

Cogman

Lifer
Sep 19, 2000
10,283
134
106
Originally posted by: Ken g6
1. What is "(number - 1) / fastPow(mpz_class(2), power);" calculating? Edit: I see, s*t=P-1? Isn't "m" == s?
2. What type is T? Int32? BigInt? Float/double? (The right answer is either Int32, Int64, or BigInt.)
3. Can you break your tests up and see which one is failing?

1. Humm, I guess you are right there. That can speed things up a bit.
2. T is of type mpz_class which is a number out of the big number library.
3. It will fail some of the time, the problem is that it is failing by saying a prime number is not prime. It shouldn't do this, a number that fails the test should be guaranteed to be composite.

It is failing on 5, 13, 17, 23, 29, 37, 41, 47, 53, 61, 73, and 97. It fails on them consistently, regardless of which primes are chosen to check them. Barring some implementation problem, I am of the opinion that the pseudo-code is bad or trying to describe something that it is not (the Miler-Rabin test).

[edit] Well apparently I just suck at psuedo code :). I found the problem, it was in step 7. After putting the correction in, it works much like it is supposed to.[/edit]