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);
        }
    }
};

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);
        }
    }
};

To copy to clipboard, switch view to plain text mode 

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;
}

#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;
}

To copy to clipboard, switch view to plain text mode 

The output looks like that:

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

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

To copy to clipboard, switch view to plain text mode 

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.