Hi there,

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

(MillerRabin.h)
Qt Code: 
  1. class MillerRabin {
  2.  
  3. public:
  4.     MillerRabin(){
  5.         as<<2<<7<<61;
  6.     }
  7.  
  8. private:
  9.     QVector<qint64> as;
  10.  
  11.     unsigned long modpow(unsigned long x, unsigned long c, unsigned long m) {
  12.         unsigned long result = 1;
  13.         unsigned long aktpot = x;
  14.         while (c > 0) {
  15.           if (c % 2 == 1) {
  16.              result = (result * aktpot);
  17.              result = result % m;
  18.           }
  19.          aktpot *= aktpot;
  20.          aktpot = aktpot%m;
  21.          c /= 2;
  22.         }
  23.       return result;
  24.     }
  25.  
  26.     bool millerRabin(unsigned long n) {
  27.         outer:
  28.         unsigned long a;
  29.         for (int xf = 0; xf < as.count();xf++) {
  30.             a = as.at(xf);
  31.             if (n>a) {
  32.                 unsigned long s = 0;
  33.                 unsigned long d = n - 1;
  34.                 while (d % 2 == 0) {
  35.                     s++;
  36.                     d /= 2;
  37.                 }
  38.                 unsigned long x = modpow(a, d, n);
  39.                 if (!(x == 1) && !(x == n - 1)) {
  40.                     for (unsigned long r = 1; s < r; r++) {
  41.                         x *= x;
  42.                         x = x % n;
  43.                         if (x == 1) {
  44.                             return false;
  45.                         }
  46.                         if (x == n - 1) {
  47.                             goto outer;
  48.                         }
  49.                     }
  50.                     return false;
  51.                 }
  52.             }
  53.         }
  54.         return true;
  55.     }
  56.  
  57. public:
  58.     bool isPrime(unsigned long n) {
  59.         if (n < 1 || n == 1) {
  60.             return false;
  61.         } else if (n < 3 || n == 3) {
  62.             return true;
  63.         } else if (n % 2 == 0) {
  64.             return false;
  65.         } else {
  66.             return millerRabin(n);
  67.         }
  68.     }
  69. };
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)
Qt Code: 
  1. #include "MillerRabin.h"
  2.  
  3. int main(int argc, char **argv)
  4. {
  5.     MillerRabin *mr = new MillerRabin();
  6.     for(int i = 0; i < 100;i++){
  7.         if(mr->isPrime(i))
  8.             qDebug()<<i;
  9.     }
  10.     return 0;
  11. }
To copy to clipboard, switch view to plain text mode 

The output looks like that:
Qt Code: 
  1. $ millerrabintest
  2. 2 
  3. 3 
  4. 7 
  5. 11 
  6. 19 
  7. 23 
  8. 31 
  9. 43 
  10. 47 
  11. 59 
  12. 67 
  13. 71 
  14. 79 
  15. 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