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.
Primality class
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Collections;
namespace PrimalityTest
{
public class Primality
{
public enum NumberType
{
Composite,
Prime
}
public bool IsPrimeMillerRabin(BigInteger integer)
{
NumberType type = MillerRabin(integer, 400);
return type == NumberType.Prime;
}
public bool IsPrimePseudo(BigInteger integer)
{
NumberType type = PseudoPrime(integer);
return type == NumberType.Prime;
}
// Primality testing based on Miller-Rabin
public NumberType MillerRabin(BigInteger n, int s)
{
BigInteger nMinusOne = BigInteger.Subtract(n, 1);
for (int j = 1; j <= s; j++)
{
BigInteger a = Random(1,nMinusOne);
if (Witness(a, n))
{
return NumberType.Composite;
}
}
return NumberType.Prime;
}
// Generates a random BigInteger between min and max
public BigInteger Random(BigInteger min, BigInteger max)
{
byte[] maxBytes = max.ToByteArray();
BitArray maxBits = new BitArray(maxBytes);
Random random = new Random(DateTime.Now.Millisecond);
for (int i = 0; i < maxBits.Length; i++)
{
// Randomly set the bit
int randomInt = random.Next();
if ((randomInt % 2) == 0)
{
// Reverse the bit
maxBits[i] = !maxBits[i];
}
}
BigInteger result = new BigInteger();
// Convert the bits back to a BigInteger
for (int k = (maxBits.Count - 1); k >= 0; k--)
{
BigInteger bitValue = 0;
if (maxBits[k])
{
bitValue = BigInteger.Pow(2, k);
}
result = BigInteger.Add(result, bitValue);
}
// Generate the random number
BigInteger randomBigInt = BigInteger.ModPow(result, 1, BigInteger.Add(max, min));
return randomBigInt;
}
// Pseudo primality testing with Fermat's theorem
public NumberType PseudoPrime(BigInteger n)
{
BigInteger modularExponentiation =
ModularExponentiation(2,
BigInteger.Subtract(n, 1),
n);
if (!modularExponentiation.IsOne)
{
return NumberType.Composite;
}
else
{
return NumberType.Prime;
}
}
public bool Witness(BigInteger a, BigInteger n)
{
KeyValuePair<int, BigInteger> tAndU = GetTAndU(BigInteger.Subtract(n, 1));
int t = tAndU.Key;
BigInteger u = tAndU.Value;
BigInteger[] x = new BigInteger[t+1];
x[0] = ModularExponentiation(a, u, n);
for (int i = 1; i <= t; i++)
{
// x[i] = x[i-1]^2 mod n
x[i] = BigInteger.ModPow(BigInteger.Multiply(x[i - 1], x[i - 1]), 1, n);
BigInteger minus = BigInteger.Subtract(x[i-1],BigInteger.Subtract(n,1));
if (x[i] == 1 && x[i - 1] != 1 && !minus.IsZero)
{
return true;
}
}
if (!x[t].IsOne)
{
return true;
}
return false;
}
public KeyValuePair<int, BigInteger> GetTAndU(BigInteger nMinusOne)
{
// Convert n - 1 to a byte array
byte[] nBytes = nMinusOne.ToByteArray();
BitArray bits = new BitArray(nBytes);
int t = 0;
BigInteger u = new BigInteger();
int n = bits.Count -1;
bool lastBit = bits[n];
// Calculate t
while (!lastBit)
{
t++;
n--;
lastBit = bits[n];
}
for (int k = ((bits.Count-1)-t); k >= 0; k--)
{
BigInteger bitValue = 0;
if (bits[k])
{
bitValue = BigInteger.Pow(2, k);
}
u = BigInteger.Add(u, bitValue);
}
KeyValuePair<int, BigInteger> tAndU = new KeyValuePair<int, BigInteger>(t, u);
return tAndU;
}
public BigInteger ModularExponentiation(BigInteger a, BigInteger b, BigInteger n)
{
// a^b mod n
return BigInteger.ModPow(a, b, n);
}
}
}
The main program
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
namespace PrimalityTest
{
class Program
{
static Random random = new Random(DateTime.Now.Millisecond);
static void Main(string[] args)
{
Primality primality = new Primality();
while (true)
{
Console.Write("Number: ");
string number = Console.ReadLine();
if (!string.IsNullOrEmpty(number))
{
// Check if the supplied number is prime
BigInteger integer = BigInteger.Parse(number);
bool isPrime = primality.IsPrimeMillerRabin(integer);
Console.WriteLine("Prime: " + isPrime);
}
else
{
// Generate a random prime number with a large number of decimal digits
BigInteger prime = GenerateLargePrime(150);
Console.WriteLine(prime);
}
}
}
static BigInteger GenerateLargePrime(int length)
{
Primality primality = new Primality();
string numbers = "";
for (int i = 0; i < length; i++)
{
numbers += random.Next(0, 10);
}
BigInteger number = BigInteger.Parse(numbers);
if (primality.IsPrimeMillerRabin(number))
{
return number;
}
else
{
return GenerateLargePrime(length);
}
}
}
}
Output:
Primality testing using Fermat's little theorem: Number: 17 Prime: True Number: 18 Prime: False Number: 453454545 Prime: False Number: 78678345567 Prime: False Number: 8191 Prime: True Number: 618970019642690137449562111 (10th Mersenne prime) Prime: True Number: Error: Number: 645 Prime: True Number: Primality testing using the Miller-Rabin primality test Number: 17 Prime: True Number: 18 Prime: False Number: 900 Prime: False Number: 1800 Prime: False Number: 89 Prime: True Number: 89 Prime: True Number: 645 Prime: False Number: 618970019642690137449562111 (10th Mersenne prime) Prime: True Number: 162259276829213363391578010288127 (11th Mersenne prime) Prime: True Number: Randomly generating large prime numbers: Number: 76943351066149825284122442112924798151756455829361679375340123913234177353876761 2740254423701622441585283215508689848887791707191522502755703892501277 Number: 62988093228754492626395684946535587265720407595114331487739414668227722789599708 8722203090435315738278491641897921531348917779158016980033165110240477 Number: 66225084039091898674368798835428416565022755589454176670753724851058523355251210 8380251836711307904531921821329543986726874842124461866636942041726841 Number: