BigInteger.isProbablePrime

Question

I just want to confirm my intuition about this method. Consider the code below.

long knownPrime = // some large known prime
int certainty = // some integer greater than 0

BigInteger b = BigInteger.valueOf(knownPrime);
boolean isPrime = b.isProbablePrime(certainty);

For a large known prime, and for any certainty > 0, is it accurate to say that b.isProbablePrime(certainty) will always return true?

Or are there any cases where the method "guesses" that a known prime number is composite?

Perhaps I completely misinterpreted the documentation the way I read it, if the value of certainty increases, then the accuracy of the answer should also increase? If that is correct, then yes, it should always return true, with a certainty of 1 would be the only point of potential error or "guessing." Of course I could have completely misunderstood that. — Brandon Buck, Mar 19 '15 at 21:29
Actually, an answer to you question is contained in the method name. This method doesn't guess if number is composite, it guesses the opposite condition, i.e. method returns false (with any certainty) only if it's sure that number is composite. — bsiamionau, Mar 19 '15 at 21:38

Anderson Vieira · Accepted Answer · 2015-03-19T21:31:24.797

For a large known prime, and for any certainty > 0, is it accurate to say that b.isProbablePrime(certainty) will always return true?

Yes. The documentation says it will return false only if it is certain that the number is composite.

Returns: true if this BigInteger is probably prime, false if it's definitely composite.

So the certainty parameter will influence only on the chance of a false-positive: saying a composite number is prime, when it really is not.

score 3 · Answer 2 · answered Mar 19 '15 at 21:43

3

For a large known prime b, and for any certainty, b.isProbablePrime(certainty) returns true.

isProbablePrime can only err by returning true when the input is not prime (an example is b=6, certainty=0, which returns true), never the other way (because the Rabin-Miller test, which isProbablePrime uses, can only fail in this direction).

answered Mar 19 '15 at 21:43

fgrieu

2,724
1
23
53

I'd be interested to know where you found out that the method internally uses the Rabin-Miller test. – Brandon Buck Mar 20 '15 at 19:29
@Brandon Buck; see [this](http://developer.classpath.org/doc/java/math/BigInteger-source.html#1284) – fgrieu Mar 20 '15 at 20:52

score 1 · Answer 3 · answered Mar 19 '15 at 21:27

According to the documentation, this method will return

true if this BigInteger is probably prime, false if it's definitely composite.

So any definite (independently verified) prime number will, by definition, return true for any legal (>0) certainty/tolerance value is passed in. The only thing the certainty/tolerance value changes is the occurrence of false-positives (true for composites) and the execution time of the method.

score -1 · Answer 4 · edited Jun 07 '20 at 06:05

-1

import java.util.*;
import java.math.*;
public class Main
{
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        long l = s.nextLong();
        BigInteger b = new BigInteger(String.valueOf(l));
        BigInteger p = b.nextProbablePrime();
        System.out.println(p);
    }
}

edited Jun 07 '20 at 06:05

Ardent Coder

3,777
9
27
53

answered Oct 30 '18 at 23:08

Satyanarayanareddy Tadi

148
9

4

Code is always good, but it also helps to add some comments/context about how this code addresses the original question. – craigcaulfield Oct 30 '18 at 23:29

BigInteger.isProbablePrime

4 Answers4

Linked