Difference between BigInteger.probablePrime() and other primality algorithms in java

7
votes

I am implementing an RSA encryption program using Java. Right now I am using BigInteger.probablePrime(1024, rnd) to get prime numbers. Here rnd is a random number generated by Random rnd = new Random() . I need to test various speeds of encryption.

My questions are:

  1. what algorithm does the BigInteger.probablePrime(1024, rnd) use?

  2. what is the difference between the algorithm above and other algorithms: like Rabin-Miller, Fermats, Lucas-Lehmer?

Thank you.

2
javaencryptioncryptographyrsabiginteger
Could you specify the language? I'm presuming Java, but presumptions... It would not hurt to read your post and remove errors before posting either. – Maarten Bodewes
Apologies, yes java. And by errors i presume you mean the way i state bigint. I tried to shorthand it I do understand that is not how to use the method in java – user1132346
I'm aware that not everybody will be able to write English at the same level, but if even the methods are spelled wrong, it will be hard to look up anything from that. Also, please use the code tags for methods. If you cannot spell "BigInteger.probablePrime()", you could revert to copy/pasting it from the online JavaDoc. Now it looks like you are not spending any time on the question, and we will return the favor of not spending any time on the answer. – Maarten Bodewes
Once again I apologize for not responding and a caring manner. This is my first post and I am not familiar with the syntax and manner in which i am to write my questions. It has been noted for future reference. – user1132346
It takes some time to get used to that, all my links were badly written so far. Meta stackoverflow has lots of useful tips about markup. And you can hit edit on your question and check the changes from mikej. – Maarten Bodewes

2 Answers

5
votes

BigInteger's probable prime methods use both the Miller-Rabin and Lucas-Lehmer algorithms to test primality.

See the internal method BigInteger.primeToCertainty.

2
votes

The Java source code is available for download, so you can look at it yourself. Here is the code for BigInteger.probablePrime(int, Random):

public static BigInteger probablePrime(int bitLength, Random rnd) {

    if (bitLength < 2)
        throw new ArithmeticException("bitLength < 2");

    // The cutoff of 95 was chosen empirically for best performance

    return (bitLength < SMALL_PRIME_THRESHOLD ?
            smallPrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd) :
            largePrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd));
}

The actual tests are contained in the smallPrime() and largePrime() methods, which follow directly in the source code.