Skip to content

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