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.

So you're using a random number generator and just hoping to hit a 1024 bit prime? You should look at this: http://crypto.stackexchange.com/questions/71/how-can-i-generate-large-prime-numbers-for-rsa — weston, Jan 07 '17 at 23:31
Maybe because it doesn't matter: https://primes.utm.edu/notes/faq/negative_primes.html — weston, Jan 07 '17 at 23:34
Maybe that **is** the correct approach reading that crypto link but sounds like a long shot to me! — weston, Jan 07 '17 at 23:42
Note that there is no reason to generate random numbers manually. The BigInteger class has a [constructor](https://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html#BigInteger-int-int-java.util.Random-) that does exactly what you want. — President James K. Polk, Jan 08 '17 at 13:41

Stephen C · Answer 1 · 2017-01-11T23:32:41.997

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.

"...to add a test to see if your candidate is negative before testing it" or don't generate negatives, as it's their choice when taking the random bits to an integer to treat them as signed or unsigned. — weston, Jan 12 '17 at 15:32

weston · Answer 2 · 2017-01-08T14:57:54.933

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.

edited Jan 08 '17 at 14:57

answered Jan 08 '17 at 14:51

weston

54,145
21
145
203

The problem I am having is that the numbers I was generating which were tested true as probable primes don't work for a certain part of RSA because they are negative when signed. It involves finding a modular multiplicative inverse, where the modulus is the LCM of the two random primes, each subtracted by one. BigInteger has a built-in function for this. This does not work when the modulus is a negative value. – Jan 09 '17 at 01:53
Are you saying you found a positive probable prime, with leading bit 1 which didn't work later on? – weston Jan 09 '17 at 11:51
Yes. The BigInteger class treats all numbers as if they were represented in two's-complement notation. There is really no practical way of implementing RSA in Java other than with the BigInteger class. – Jan 17 '17 at 09:13
Show me your code that takes bits to BigInteger and I will show you how to treat it unsigned. – weston Jan 17 '17 at 12:18
"There is really no practical way of implementing RSA in Java other than with the BigInteger class." not if you want to reinvent the wheel, no. Otherwise here's a simple example: http://stackoverflow.com/a/13501136/360211 – weston Jan 17 '17 at 13:39

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

2 Answers2