Many of the cryptography based techniques involves handling large numbers, specially large prime numbers. It is obvious from experience that our computers cannot handle such huge numbers(Here, huge refers to numbers involving 300 digits and even more!!!).

Set your computer for this task!!

There are many libraries and extensions out there to handle huge numbers. My choice from them is GNU Multiple Precision (GMP). It is very easy to understand and offers a lot of functionality including efficient number theoretic algorithms.

You can download gmp at this link. It is a library for C. It has its own data types(mpz_t, mpz_f etc.) defined in the library.

Using gmp in C may be a bit frustrating due to the data types and initialization of the declared variables. There is a python extension for this library: gmpy. This makes your task a lot easier.

Assuming, you have gmp and gmpy let us see how to generate large prime numbers.

There are few methods to generate(test, to be more precise) prime numbers apart from the trivial method of checking for its divisibility.

The available methods can be classified into two types:

1) Probabilistic

2)  Deterministic

1) Probabilistic: Algorithms falling in this category are probabilistic, in simple words they cannot be trusted. There is chance of the algorithms giving a wrong answer. Some of these are

a) Primality test based on Fermat’s little theorem

b) Solovay – Strassen test

c) Miller – Rabin Test

2) Deterministic approach: Algorithms of this class always give exact answers. There is no chance of error.

a) Algorithm due to AKS( Agarwal, Kayal, Saxena IIT Kanpur)

We heavily rely upon probabilistic test though we have an implementation for the deterministic test mentioned above. This is due to the fact that the running time of AKS is pretty huge.

Fermat’s little theorem by itself is not a very good method for testing primality because there are composite numbers which do satisfy the theorem.

Compared to Miller – Rabin, Solovay – Strassen has higher probability of error. Hence Miller – Rabin is used. More explanation regarding Miller – Rabin can be found here.

Following is a python program for Miller – Rabin Test:



More Explanation about the code in my upcoming posts.