Performance of Prime Number Generation

This section describes the performance of prime number generation using the java.math.BigInteger class. Larger prime numbers and higher certainties requires longer generation time.

Since my program is working, I want to use it to do more tests to see the impact on the generation time when I increase the bit length of the prime number.

In the first set of tests, I fixed the certainty to 16, which gives a probability of 99.99847412109375%. Testing results of different bit lengths are summarized in the table below:

```                                Gen.   Val.
Bits Cert.  Probability         time   time  Prime
16   16  99.99847412109375       1     32  64063
32   16  99.99847412109375       2     40  4229630129
64   16  99.99847412109375       3     34  18000105070399368923
128   16  99.99847412109375      19     36  323465175613040279975...
256   16  99.99847412109375      17     38  917924135915163081716...
512   16  99.99847412109375     121     62  966939251609260746850...
1024   16  99.99847412109375     343    126  160235677041735401079...
2048   16  99.99847412109375    6746    743  322355788576903895186...
3072   16  99.99847412109375   24545   2362  553613219309114846316...
```

As you can see, generating a prime number with 1024 or less bits is pretty fast, taking less than 1 second. But it took 6.7 seconds to generate a 2048-bit prime number, and 24.5 seconds to generate a 3072-bit prime number.

In the second set of tests, I fixed the bit length to 3072. Testing results of different certainty levels are summarized in the table below:

```                                Gen.   Val.
Bits Cert.  Probability         time   time  Prime
3072   16  99.99847412109375   34824   2344  565702937028652677653...
3072   32  99.99999997671694   57465   2334  481349137981705251267...
3072   64  100.0                8763   2341  353663618372094331380...
3072  128  100.0               63645   2413  430259008059707049953...
3072  256  100.0               34017   2352  440736874159753618303...
3072  512  100.0                7039   2357  486492819926034358966...
3072 1024  100.0              120450   2337  567519578195425341872...
```

It is interesting to see that probability rounds up to 100% when the certainty is 64 or higher.

Also the prime number generation time is not truly proportional to the certainty. For example, it took much less time for certainty=512 than certainty=16. This could be caused by the randomness of the algorithm.

Last update: 2013.

Table of Contents