Handy snippets of code

Prime numbers have many applications. For example, in cryptography. The RSA algorithm for public-key cryptography uses large prime numbers for generating keys. Quote:

The RSA algorithm works as follows: take two large primes, p and q, and compute their product n = pq; n is called the modulus. Choose a number, e, less than n and relatively prime to (p-1)(q-1), which means e and (p-1)(q-1) have no common factors except 1. Find another number d such that (ed – 1) is divisible by (p-1)(q-1). The values e and d are called the public and private exponents, respectively. The public key is the pair (n, e); the private key is (n, d). The factors p and q may be destroyed or kept with the private key.

Large prime numbers can be found with a primality test. A primality test will determine whether a number is prime or composite. The C# console application below is able to check whether a supplied number is prime or composite and able to randomly produce large prime numbers. Two methods for primality testing are used. Namely, Fermat’s little theorem for pseudo primality testing and the Miller-Rabin primality test.

The primality test based on Fermat’s little theorem is probabilistic and will produce errors for numbers such as 341 and 645 whereas the Miller-Rabin primality test is deterministic.

The theory in chapter 31.8 of Introduction to Algorithms has been used for the implementation. Thus, major credits to Thomas H. Cormen, Clifford Stein, Ronald L. Rivest and Charles E. Leiserson.

Read More »