Miller-Rabin test

[mizocom2002]

[cpp]
int Prime(int n, int alpha)
// Returns 1 if n is a prime and 0 otherwise.
// alpha is the probability parameter.
{
int q = n-1;
for (int i=1; i<=(alpha*log(n)); i++) {
int m = q, y = 1;
int a = random() % q + 1;
// Choose a random number in the range [1, n-1].
int z = a;
// Compute a^{n-1}mod n.
while (m > 0) {
while (m%2 == 0) {
int x = z; z = (z*z) % n;
// If x is a nontrivial square
// root of 1, n is not a prime.
if ((z==1) && (x != 1) && (x != q))
return(0);
m /= 2;
}
m--; y = (y*z) % n;
}
if (y != 1) return(0);
// If a^{n-1}mod n is not 1, n is not a prime.
}
return(1);
}


//this code is from the following book: computer algorithms/c++ for Horowitz and rajasekaran[/cpp]

[Miguel Angel]

Just change int by long,
it doesn't work for example when n = 997 (return 0), i think it maybe to the (z*z), in such case will be (10^3)*(10^3) > 2^15-1

[Jordan Gordeev]

Miguel, I haven't read the code, but I know that int and long are both 32-bit signed integers for the Judge's C/C++ compiler.