Miller-Rabin-Test fails for 13 and 17

[tillorgias]

Hi there,

I am trying to write a class that does the miller rabin test.
Currently, it looks like that:

(MillerRabin.h)


class MillerRabin {

public:
MillerRabin(){
as<<2<<7<<61;
}

private:
QVector<qint64> as;

unsigned long modpow(unsigned long x, unsigned long c, unsigned long m) {
unsigned long result = 1;
unsigned long aktpot = x;
while (c > 0) {
if (c % 2 == 1) {
result = (result * aktpot);
result = result % m;
}
aktpot *= aktpot;
aktpot = aktpot%m;
c /= 2;
}
return result;
}

bool millerRabin(unsigned long n) {
outer:
unsigned long a;
for (int xf = 0; xf < as.count();xf++) {
a = as.at(xf);
if (n>a) {
unsigned long s = 0;
unsigned long d = n - 1;
while (d % 2 == 0) {
s++;
d /= 2;
}
unsigned long x = modpow(a, d, n);
if (!(x == 1) && !(x == n - 1)) {
for (unsigned long r = 1; s < r; r++) {
x *= x;
x = x % n;
if (x == 1) {
return false;
}
if (x == n - 1) {
goto outer;
}
}
return false;
}
}
}
return true;
}

public:
bool isPrime(unsigned long n) {
if (n < 1 || n == 1) {
return false;
} else if (n < 3 || n == 3) {
return true;
} else if (n % 2 == 0) {
return false;
} else {
return millerRabin(n);
}
}
};


It's not a nice style, I know, but I just imported it from java source code. Well, now, the problem is that if I use it in the following small program, I don't get every prime number in the output:

(main.cpp)


#include "MillerRabin.h"

int main(int argc, char **argv)
{
MillerRabin *mr = new MillerRabin();
for(int i = 0; i < 100;i++){
if(mr->isPrime(i))
qDebug()<<i;
}
return 0;
}


The output looks like that:


$ millerrabintest
2
3
7
11
19
23
31
43
47
59
67
71
79
83


For example, there are 13 and 17 missing.
Well, I know that Miller-Rabin-Test does not work on 100%, but if it fails, it says that a number is a prime number that is not, and in Java-implementation (where I imported it from), this class does not fail for numbers that are smaller than 10^7 I think.

I hope you find the problem, maybe it's very simple...

Tillorgias

[tbscope]

I'm not familiar with the algorithm, but try setting breakpoints and step through the program, line by line to see where the problem is.