Why does Java BigInteger say 'probably prime' and not 'certainly prime'?
up vote
0
down vote
favorite
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?
java biginteger
edited Nov 10 at 22:08
Rudy Velthuis
23.8k43474
asked Nov 10 at 20:29
Long Nguyen
919
add a comment |
up vote
0
down vote
favorite
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?
java biginteger
edited Nov 10 at 22:08
Rudy Velthuis
23.8k43474
asked Nov 10 at 20:29
Long Nguyen
919
1
Did you read the detailed section? The increasing runtime is why only probably. See also stackoverflow.com/q/8744085/3001761
– jonrsharpe
Nov 10 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.
– James K Polk
Nov 10 at 20:40
1
There is an algorithm due to Maurer that find primes that are guaranteed to be prime. See for example this problem. This algorithm is not currently available in the Java runtime.
– James K Polk
Nov 10 at 21:03
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
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?
java biginteger
edited Nov 10 at 22:08
Rudy Velthuis
23.8k43474
asked Nov 10 at 20:29
Long Nguyen
919
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?
java biginteger
java biginteger
edited Nov 10 at 22:08
Rudy Velthuis
23.8k43474
asked Nov 10 at 20:29
Long Nguyen
919
edited Nov 10 at 22:08
Rudy Velthuis
23.8k43474
asked Nov 10 at 20:29
Long Nguyen
919
edited Nov 10 at 22:08
Rudy Velthuis
23.8k43474
edited Nov 10 at 22:08
Rudy Velthuis
23.8k43474
edited Nov 10 at 22:08
Rudy Velthuis
23.8k43474
23.8k43474
asked Nov 10 at 20:29
Long Nguyen
919
asked Nov 10 at 20:29
Long Nguyen
919
asked Nov 10 at 20:29
Long Nguyen
919
919
1
Did you read the detailed section? The increasing runtime is why only probably. See also stackoverflow.com/q/8744085/3001761
– jonrsharpe
Nov 10 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.
– James K Polk
Nov 10 at 20:40
1
There is an algorithm due to Maurer that find primes that are guaranteed to be prime. See for example this problem. This algorithm is not currently available in the Java runtime.
– James K Polk
Nov 10 at 21:03
add a comment |
1
Did you read the detailed section? The increasing runtime is why only probably. See also stackoverflow.com/q/8744085/3001761
– jonrsharpe
Nov 10 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.
– James K Polk
Nov 10 at 20:40
1
There is an algorithm due to Maurer that find primes that are guaranteed to be prime. See for example this problem. This algorithm is not currently available in the Java runtime.
– James K Polk
Nov 10 at 21:03
1
1
Did you read the detailed section? The increasing runtime is why only probably. See also stackoverflow.com/q/8744085/3001761
– jonrsharpe
Nov 10 at 20:39
Did you read the detailed section? The increasing runtime is why only probably. See also stackoverflow.com/q/8744085/3001761
– jonrsharpe
Nov 10 at 20:39
2
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.
– James K Polk
Nov 10 at 20:40
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.
– James K Polk
Nov 10 at 20:40
1
1
There is an algorithm due to Maurer that find primes that are guaranteed to be prime. See for example this problem. This algorithm is not currently available in the Java runtime.
– James K Polk
Nov 10 at 21:03
There is an algorithm due to Maurer that find primes that are guaranteed to be prime. See for example this problem. This algorithm is not currently available in the Java runtime.
– James K Polk
Nov 10 at 21:03
add a comment |
2 Answers
2
active
oldest
votes
up vote
4
down vote
accepted
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"
edited Nov 10 at 20:41
James K Polk
29.2k106694
answered Nov 10 at 20:39
GBlodgett
7,14541329
add a comment |
up vote
4
down vote
Because the probabilistic algorithm runs a lot faster than verifying that the number is definitely prime.
answered Nov 10 at 20:40
OpenSauce
7,05311628
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
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"
edited Nov 10 at 20:41
James K Polk
29.2k106694
answered Nov 10 at 20:39
GBlodgett
7,14541329
add a comment |
up vote
4
down vote
accepted
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"
edited Nov 10 at 20:41
James K Polk
29.2k106694
answered Nov 10 at 20:39
GBlodgett
7,14541329
add a comment |
up vote
4
down vote
accepted
up vote
4
down vote
accepted
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"
edited Nov 10 at 20:41
James K Polk
29.2k106694
answered Nov 10 at 20:39
GBlodgett
7,14541329
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"
edited Nov 10 at 20:41
James K Polk
29.2k106694
answered Nov 10 at 20:39
GBlodgett
7,14541329
edited Nov 10 at 20:41
James K Polk
29.2k106694
edited Nov 10 at 20:41
James K Polk
29.2k106694
edited Nov 10 at 20:41
James K Polk
29.2k106694
29.2k106694
answered Nov 10 at 20:39
GBlodgett
7,14541329
answered Nov 10 at 20:39
GBlodgett
7,14541329
answered Nov 10 at 20:39
GBlodgett
7,14541329
7,14541329
add a comment |
add a comment |
up vote
4
down vote
Because the probabilistic algorithm runs a lot faster than verifying that the number is definitely prime.
answered Nov 10 at 20:40
OpenSauce
7,05311628
add a comment |
up vote
4
down vote
Because the probabilistic algorithm runs a lot faster than verifying that the number is definitely prime.
answered Nov 10 at 20:40
OpenSauce
7,05311628
add a comment |
up vote
4
down vote
up vote
4
down vote
Because the probabilistic algorithm runs a lot faster than verifying that the number is definitely prime.
answered Nov 10 at 20:40
OpenSauce
7,05311628
Because the probabilistic algorithm runs a lot faster than verifying that the number is definitely prime.
answered Nov 10 at 20:40
OpenSauce
7,05311628
answered Nov 10 at 20:40
OpenSauce
7,05311628
answered Nov 10 at 20:40
OpenSauce
7,05311628
answered Nov 10 at 20:40
OpenSauce
7,05311628
7,05311628
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53243130%2fwhy-does-java-biginteger-say-probably-prime-and-not-certainly-prime%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
Did you read the detailed section? The increasing runtime is why only probably. See also stackoverflow.com/q/8744085/3001761
– jonrsharpe
Nov 10 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.
– James K Polk
Nov 10 at 20:40
1
There is an algorithm due to Maurer that find primes that are guaranteed to be prime. See for example this problem. This algorithm is not currently available in the Java runtime.
– James K Polk
Nov 10 at 21:03