Why does the BigInteger.isProbablePrime() function in Java return true for negative numbers?

Question

I am implementing the RSA public-key cryptographic algorithm in Java. It requires generating two random prime numbers. I have been using the SecureRandom class to generate two 1024 bit numbers to create a 2048 bit key. I handle the numbers using the BigInteger class. I use the isProbablePrime() function to determine whether it is prime, with a certainty of 100. However, I have noticed that this function has returned true for negative numbers, even though by definition, prime numbers cannot be negative.

Answer 1

We can't give you a definitive answer to the "why" question. For that, you would need to talk to the people who designed the API.

I'm inclined to agree with @weston's conjecture that "it doesn't matter"; see this link. And another takeaway from the link is that it depends on which definition of prime number is being used as to whether prime numbers are negative. (By the most widely used definition, they aren't, but ...)

However, I can tell you that the implementation behavior is deliberate. The implementation of the method is as follows:

public boolean isProbablePrime(int certainty) {
    if (certainty <= 0)
        return true;
    BigInteger w = this.abs();
    if (w.equals(TWO))
        return true;
    if (!w.testBit(0) || w.equals(ONE))
        return false;
    return w.primeToCertainty(certainty, null);
}

Notice how it takes the absolute value of the candidate before testing.

This behavior has been in place for a long time with (from what I can see) ZERO recorded Java Bug Reports about it. This supports @weston's conjecture.

---

Irrespective of whether isProbablePrime's behavior is correct, the pragmatic solution is to add a test to see if your candidate is negative before testing it.

Answer 2

On primes, I pointed out it may not matter. But what does matter is when converting the 1024 random bits to an integer, you must consider which is the correct approach; treat it as signed (like you are) or treat it unsigned?

So for example in 8 bits, if I randomly generate 11010011 that is 211 when treated as an unsigned integer which is a prime number.

If I treat the same bits 11010011 as a signed integer, I get -45 which is not a prime, even if you accept negative primes.

Get this wrong and your code will both falsely exclude valid keys and falsely accept invalid keys. And if you exclude all negatives just to be on the safe side, then you will only get 1023 bit primes (twos-complement negatives always have a 1 in the most significant bit).

So the way you deal with the conversion from bits to integer is able to avoid negatives and avoid the whole question of negative primes, and RSA would only have one correct interpretation of the number selected as the key. My guess is that interpretation is unsigned.