miller_rabin.cpp File Reference

#include <cassert>
#include <iostream>
#include <random>
#include <vector>

Include dependency graph for miller_rabin.cpp:

Functions
template<typename T >
std::vector< T >	reverse_binary (T num)
template<typename T >
T	modular_exponentiation (T base, const std::vector< T > &rev_binary_exponent, T mod)
template<typename T >
bool	miller_test (T d, T num)
template<typename T >
bool	miller_rabin_primality_test (T num, T repeats)
void	tests ()
int	main ()

Detailed Description

Copyright 2020

Author

tjgurwara99

A basic implementation of Miller-Rabin primality test.

Function Documentation

main()

int main

(

)

Main function

           {
    tests();
    return 0;
}

Here is the call graph for this function:

miller_rabin_primality_test()

template<typename T >

bool miller_rabin_primality_test	(	T	num,
		T	repeats
	)

Function that test (probabilistically) whether a given number is a prime based on the Miller-Rabin Primality Test.

Parameters

num	number to be tested for primality.
repeats	number of repetitions for the test to increase probability of correct result.

Returns

'false' if num is composite

'true' if num is (probably) prime

\detail First we check whether the num input is less than 4, if so we can determine whether this is a prime or composite by checking for 2 and 3. Next we check whether this num is odd (as all primes greater than 2 are odd). Next we write our num in the following format \(num = 2^r \cdot d + 1\). After finding r and d for our input num, we use for loop repeat number of times inside which we check the miller conditions using the function miller_test. If miller_test returns false then the number is composite After the loop finishes completely without issuing a false return call, we can conclude that this number is probably prime.

                                                                         {
    if (num <= 4) {
        // If num == 2 or num == 3 then prime
        if (num == 2 || num == 3) {
            return true;
        } else {
            return false;
        }
    }
    // If num is even then not prime
    if (num % 2 == 0) {
        return false;
    }
    // Finding d and r in num = 2^r * d + 1
    T d = num - 1, r = 0;
    while (d % 2 == 0) {
        d = d / 2;
        r++;
    }
 
    for (T i = 0; i < repeats; ++i) {
        if (!miller_test(d, num)) {
            return false;
        }
    }
    return true;
}

Here is the call graph for this function:

miller_test()

template<typename T >

bool miller_test	(	T	d,
		T	num
	)

Function for testing the conditions that are satisfied when a number is prime.

Parameters

d	number such that \(d \cdot 2^r = n - 1\) where \(n = num\) parameter and \(r \geq 1\)
num	number being tested for primality.

Returns

'false' if n is composite

'true' if n is (probably) prime.

                                                   {
    // random number seed
    std::random_device rd_seed;
    // random number generator
    std::mt19937 gen(rd_seed());
    // Uniformly distributed range [2, num - 2] for random numbers
    std::uniform_int_distribution<> distribution(2, num - 2);
    // Random number generated in the range [2, num -2].
    T random = distribution(gen);
    // vector for reverse binary of the power
    std::vector<T> power = reverse_binary(d);
    // x = random ^ d % num
    T x = modular_exponentiation(random, power, num);
    // miller conditions
    if (x == 1 || x == num - 1) {
        return true;
    }
 
    while (d != num - 1) {
        x = (x * x) % num;
        d *= 2;
        if (x == 1) {
            return false;
        }
        if (x == num - 1) {
            return true;
        }
    }
    return false;
}

Here is the call graph for this function:

modular_exponentiation()

template<typename T >

T modular_exponentiation	(	T	base,
		const std::vector< T > &	rev_binary_exponent,
		T	mod
	)

Function for modular exponentiation. This function is an efficient modular exponentiation function. It can be used with any big integer library such as Boost multiprecision to give result any modular exponentiation problem relatively quickly.

Parameters

base	number being raised to a power as integer
rev_binary_exponent	reverse binary of the power the base is being raised to
mod	modulo

Returns

r the modular exponentiation of \(a^{n} \equiv r \mod{m}\) where \(n\) is the base 10 representation of rev_binary_exponent and \(m = mod \) parameter.

                                {
    if (mod == 1)
        return 0;
    T b = 1;
    if (rev_binary_exponent.size() == 0)
        return b;
    T A = base;
    if (rev_binary_exponent[0] == 1)
        b = base;
 
    for (typename std::vector<T>::const_iterator it =
             rev_binary_exponent.cbegin() + 1;
         it != rev_binary_exponent.cend(); ++it) {
        A = A * A % mod;
        if (*it == 1)
            b = A * b % mod;
    }
    return b;
}

reverse_binary()

template<typename T >

std::vector<T> reverse_binary

(

T

num

)

Function to give a binary representation of a number in reverse order

Parameters

num	integer number that we want to convert

Returns

result vector of the number input in reverse binary

                                                         {
    std::vector<T> result;
    T temp = num;
    while (temp > 0) {
        result.push_back(temp % 2);
        temp = temp / 2;
    }
    return result;
}

Here is the call graph for this function:

tests()

void tests

(

)

Functions for testing the miller_rabin_primality_test() function with some assert statements.

             {
    // First test on 2
    assert(((void)"2 is prime but function says otherwise.\n",
            miller_rabin_primality_test(2, 1) == true));
    std::cout << "First test passes." << std::endl;
    // Second test on 5
    assert(((void)"5 should be prime but the function says otherwise.\n",
            miller_rabin_primality_test(5, 3) == true));
    std::cout << "Second test passes." << std::endl;
    // Third test on 23
    assert(((void)"23 should be prime but the function says otherwise.\n",
            miller_rabin_primality_test(23, 3) == true));
    std::cout << "Third test passes." << std::endl;
    // Fourth test on 16
    assert(((void)"16 is not a prime but the function says otherwise.\n",
            miller_rabin_primality_test(16, 3) == false));
    std::cout << "Fourth test passes." << std::endl;
    // Fifth test on 27
    assert(((void)"27 is not a prime but the function says otherwise.\n",
            miller_rabin_primality_test(27, 3) == false));
    std::cout << "Fifth test passes." << std::endl;
}

Here is the call graph for this function: