Miller-rabin exception number?
- by nightcracker
Hey everyone. This question is about the number 169716931325235658326303.
According to http://www.alpertron.com.ar/ECM.HTM it is prime.
According to my miller-rabin implementation in python with 7 repetitions is is composite. With 50 repetitions it is still composite. With 5000 repetitions it is STILL composite.
I thought, this might be a problem of my implementation. So I tried GNU MP bignum library, which has a miller-rabin primality test built-in. I tested with 1000000 repetitions. Still composite.
This is my implementation of the miller-rabin primality test:
def isprime(n, precision=7):
if n == 1 or n % 2 == 0:
return False
elif n < 1:
raise ValueError("Out of bounds, first argument must be > 0")
d = n - 1
s = 0
while d % 2 == 0:
d //= 2
s += 1
for repeat in range(precision):
a = random.randrange(2, n - 2)
x = pow(a, d, n)
if x == 1 or x == n - 1: continue
for r in range(s - 1):
x = pow(x, 2, n)
if x == 1: return False
if x == n - 1: break
else: return False
return True
And the code for the GMP test:
#include <gmp.h>
#include <stdio.h>
int main(int argc, char* argv[]) {
mpz_t test;
mpz_init_set_str(test, "169716931325235658326303", 10);
printf("%d\n", mpz_probab_prime_p(test, 1000000));
mpz_clear(test);
return 0;
}
As far as I know there are no "exceptions" (which return false positives for any amount of repetitions) to the miller-rabin primality test. Have I stumpled upon one? Is my computer broken? Is the Elliptic Curve Method wrong? What is happening here?
EDIT
I found the issue, which is http://www.alpertron.com.ar/ECM.HTM. I trusted this applet, I'll contact the author his applet's implementation of the ECM is faulty for this number. Thanks.
EDIT2
Hah, the shame! In the end it was something that went wrong with copy/pasting on my side. NOR the applet NOR the miller-rabin algorithm NOR my implementation NOR gmp's implementation of it is wrong, the only thing that's wrong is me. I'm sorry.
