Gmp.mpz.probably_prime_p inconsistently handles negative prime numbers
While conducting some tests using Gmp.mpz()->probably_prime_p(), I've noticed that so-called 'negative primes' are handled inconsistently.
While testing using https://github.com/google/wycheproof/blob/master/testvectors/primality_test.json, some tests deal with so-called 'negative values of prime numbers' – "Some libraries accept the negative of a prime number as prime. For crypto libraries this just adds another potential pitfall".
Pike's probably_prime_p() seems to classify these as 'not a prime number'. However, there is a single test which probably_prime_p() classifies as a prime number: ff38e38e39.
The following code tests the testcases:
int main() {
array vals = ({
"feff",
"ff3b13b13b",
"ff38e38e39",
"ae4c415c9882b931",
"a6c0964fda6c0965",
"ff05050505050505050505050505050505",
"ff20ffbe0083fef8020ffbe0083fef8021",
"ff5075075075075075075075075075075075075075075075075075075075075075",
});
for(int i=0; i<sizeof(vals); i++) {
mixed p = Gmp.mpz(vals[i], 16)->probably_prime_p(10000);
if(p == 0) {
write("%s is not a prime.\n", vals[i]);
} else if (p == 2){
write("%s is a prime.\n", vals[i]);
} else {
write("%s is maybe a prime.\n", vals[i]);
}
}
return 0;
}
I would expect all of the tests to return the same result. However, the following is printed:
feff is not a prime.
ff3b13b13b is not a prime.
ff38e38e39 is a prime.
ae4c415c9882b931 is not a prime.
a6c0964fda6c0965 is not a prime.
ff05050505050505050505050505050505 is not a prime.
ff20ffbe0083fef8020ffbe0083fef8021 is not a prime.
ff5075075075075075075075075075075075075075075075075075075075075075 is not a prime.
It may not be a bug, but I thought I would report that the test produces inconsistent results; something I would not expect. Could the classification of ff38e38e39
being a prime be a bug?
If this is not unexpected, apologies for the false report, but best to report the unexpected result