tillorgias

9th July 2010, 14:47

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

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