- 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
Sounds fairly straight forward, right? So here is the code I generated (c++)
It isn't a terrible test, however, what bothers me is this portion of the handout
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).)
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