1

The JavaDoc of BigInteger makes me feel very insecure, for example the following constructor says:

BigInteger(int bitLength, int certainty, Random rnd)

Constructs a randomly generated positive BigInteger that is probably prime, with the specified bitLength.

Why only probably? Why not certainly? Can I still trust that the result would be a prime number?

Rudy Velthuis
  • 28,387
  • 5
  • 46
  • 94
curiouscupcake
  • 1,157
  • 13
  • 28
  • 1
    Did you read [the detailed section](https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#BigInteger(int,%20int,%20java.util.Random))? The increasing runtime is why only probably. See also https://stackoverflow.com/q/8744085/3001761 – jonrsharpe Nov 10 '18 at 20:39
  • 2
    It's only probably because it uses a prime testing algorithm that may fail. The rest of the documentation provides an upper bound on the probability of failure. – President James K. Polk Nov 10 '18 at 20:40
  • 1
    There is an algorithm due to Maurer that find primes that are guaranteed to be prime. See for example [this](https://programmingpraxis.com/2017/03/31/generating-random-large-primes/) problem. This algorithm is not currently available in the Java runtime. – President James K. Polk Nov 10 '18 at 21:03

2 Answers2

5

From the docs for BigInteger(int bitLength, int certainty, Random rnd):

certainty: a measure of the uncertainty that the caller is willing to tolerate. The probability that the new BigInteger represents a prime number will exceed (1 - ½certainty). The execution time of this constructor is proportional to the value of this parameter.

So the constructor lets you specify the certainty that it will be prime, which is why the docs say "probably"

President James K. Polk
  • 40,516
  • 21
  • 95
  • 125
GBlodgett
  • 12,704
  • 4
  • 31
  • 45
5

Because the probabilistic algorithm runs a lot faster than verifying that the number is definitely prime.

OpenSauce
  • 8,533
  • 1
  • 24
  • 29