Primality testing with Fermat’s little theorem and Miller-Rabin in C#

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:
This entry was posted in C# and tagged , , , , , , , , , , , , , , , , , . Bookmark the permalink. Trackbacks are closed, but you can post a comment.

2 Comments

  1. mustafa
    Posted May 28, 2014 at 5:39 pm | Permalink

    very good …

  2. hasan
    Posted June 16, 2014 at 5:19 pm | Permalink

    Thanks, good work!!

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Why ask?