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

 About This Book

 Cryptography Terminology

 Cryptography Basic Concepts

 Introduction to AES (Advanced Encryption Standard)

 Introduction to DES Algorithm

 DES Algorithm - Illustrated with Java Programs

 DES Algorithm Java Implementation

 DES Algorithm - Java Implementation in JDK JCE

 DES Encryption Operation Modes

 DES in Stream Cipher Modes

 PHP Implementation of DES - mcrypt

 Blowfish - 8-Byte Block Cipher

 Secret Key Generation and Management

 Cipher - Secret Key Encryption and Decryption

 Introduction of RSA Algorithm

RSA Implementation using java.math.BigInteger Class

 java.Math.BigInteger Class

 Generating Prime Number with BigInteger Class

Performance of Prime Number Generation

 RSA Encryption Implementation using BigInteger Class

 RsaKeyGenerator.java for RSA Key Generation

 RSA Keys Generated by RsaKeyGenerator.java

 RsaKeyValidator.java for RSA Key Validation

 64-bit RSA Key Validated by RsaKeyValidator.java

 Converting Byte Sequences to Positive Integers

 Cleartext Block Size for RSA Encryption

 Cleartext Message Padding and Revised Block Size

 Ciphertext Block Size for RSA Encryption

 RsaKeyEncryption.java for RSA Encryption Operation

 RsaKeyDecryption.java for RSA Decryption Operation

 Testing RsaKeyEncryption.java with a 16-bit Key

 Testing RsaKeyEncryption.java with a 64-bit Key

 Testing RsaKeyEncryption.java with a 3072-bit Key

 Introduction of DSA (Digital Signature Algorithm)

 Java Default Implementation of DSA

 Private key and Public Key Pair Generation

 PKCS#8/X.509 Private/Public Encoding Standards

 Cipher - Public Key Encryption and Decryption

 MD5 Mesasge Digest Algorithm

 SHA1 Mesasge Digest Algorithm

 OpenSSL Introduction and Installation

 OpenSSL Generating and Managing RSA Keys

 OpenSSL Managing Certificates

 OpenSSL Generating and Signing CSR

 OpenSSL Validating Certificate Path

 "keytool" and "keystore" from JDK

 "OpenSSL" Signing CSR Generated by "keytool"

 Migrating Keys from "keystore" to "OpenSSL" Key Files

 Certificate X.509 Standard and DER/PEM Formats

 Migrating Keys from "OpenSSL" Key Files to "keystore"

 Using Certificates in IE (Internet Explorer)

 Using Certificates in Firefox

 Using Certificates in Google Chrome

 Outdated Tutorials

 References

 PDF Printing Version