Generating Prime Number with BigInteger Class

This section provides a tutorial example on how to generate probable prime numbers using the java.math.BigInteger class in Java.

The first thing I want to try with the java.Math.BigInteger Class is to generate probable prime numbers. I am interested how fast large prime numbers can be generated and how good they are. Here is my first Java program using the java.Math.BigInteger Class:

```/* PrimeGenerator.java
#- Copyright (c) 2013, HerongYang.com, All Rights Reserved.
*/
import java.math.BigInteger;
import java.util.Random;
class PrimeGenerator {
public static void main(String[] a) {
if (a.length<2) {
System.out.println("Usage:");
System.out.println("java PrimeGenerator length certainty");
return;
}
int length = Integer.parseInt(a[0]);
int certainty = Integer.parseInt(a[1]);
Random rnd = new Random();

long t1 = System.currentTimeMillis();
BigInteger p = new BigInteger(length,certainty,rnd);
long t2 = System.currentTimeMillis();
boolean ok = p.isProbablePrime(certainty);
long t3 = System.currentTimeMillis();

BigInteger two = new BigInteger("2");
System.out.println("Probable prime: "+p);
System.out.println("Validation: "+ok);
System.out.println("Bit length: "+length);
System.out.println("Certainty: "+certainty);
System.out.println("Probability (%): "
+(100.0-100.0/(two.pow(certainty)).doubleValue()));
System.out.println("Generation time (milliseconds): "+(t2-t1));
System.out.println("Validation time (milliseconds): "+(t3-t2));
}
}
```

Compile and run it on my Windows 7 computer with JDK 1.6 starting with a small bit length and certainty to validate my program:

```C:\herong>javac PrimeGenerator.java

C:\herong>java PrimeGenerator 4 4
Probable prime: 13
Validation: true
Bit length: 4
Certainty: 4
Probability (%): 93.75
Generation time (milliseconds): 1
Validation time (milliseconds): 39
```

Reviewing the output, we can see that prime number generated by the program, 13, does meet specified criteria:

• 13 expressed in binary format is 1101, which is 4-bit long as specified.
• 13 is a true prime number. Its probability is 100%, higher than the specified probability of 93.75%, because probability = 100 - 100/(2**certainty) = 100 - 100/16 = 93.75.
• The generation time is short, only 1 millisecond.
• But the validation time is much longer, took 39 milliseconds.

I think my program works correctly. What do you think?

Last update: 2013.

Table of Contents