Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
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 >
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 ( void  )

Main function

183  {
184  tests();
185  return 0;
186 }
Here is the call graph for this function:

◆ miller_rabin_primality_test()

template<typename T >
bool miller_rabin_primality_test ( num,
repeats 
)

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

Parameters
numnumber to be tested for primality.
repeatsnumber 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.

125  {
126  if (num <= 4) {
127  // If num == 2 or num == 3 then prime
128  if (num == 2 || num == 3) {
129  return true;
130  } else {
131  return false;
132  }
133  }
134  // If num is even then not prime
135  if (num % 2 == 0) {
136  return false;
137  }
138  // Finding d and r in num = 2^r * d + 1
139  T d = num - 1, r = 0;
140  while (d % 2 == 0) {
141  d = d / 2;
142  r++;
143  }
144 
145  for (T i = 0; i < repeats; ++i) {
146  if (!miller_test(d, num)) {
147  return false;
148  }
149  }
150  return true;
151 }
Here is the call graph for this function:

◆ miller_test()

template<typename T >
bool miller_test ( d,
num 
)

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

Parameters
dnumber such that \(d \cdot 2^r = n - 1\) where \(n = num\) parameter and \(r \geq 1\)
numnumber being tested for primality.
Returns
'false' if n is composite
'true' if n is (probably) prime.
73  {
74  // random number seed
75  std::random_device rd_seed;
76  // random number generator
77  std::mt19937 gen(rd_seed());
78  // Uniformly distributed range [2, num - 2] for random numbers
79  std::uniform_int_distribution<> distribution(2, num - 2);
80  // Random number generated in the range [2, num -2].
81  T random = distribution(gen);
82  // vector for reverse binary of the power
84  // x = random ^ d % num
85  T x = modular_exponentiation(random, power, num);
86  // miller conditions
87  if (x == 1 || x == num - 1) {
88  return true;
89  }
90 
91  while (d != num - 1) {
92  x = (x * x) % num;
93  d *= 2;
94  if (x == 1) {
95  return false;
96  }
97  if (x == num - 1) {
98  return true;
99  }
100  }
101  return false;
102 }
Here is the call graph for this function:

◆ modular_exponentiation()

template<typename T >
T modular_exponentiation ( base,
const std::vector< T > &  rev_binary_exponent,
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
basenumber being raised to a power as integer
rev_binary_exponentreverse binary of the power the base is being raised to
modmodulo
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.
44  {
45  if (mod == 1)
46  return 0;
47  T b = 1;
48  if (rev_binary_exponent.size() == 0)
49  return b;
50  T A = base;
51  if (rev_binary_exponent[0] == 1)
52  b = base;
53 
54  for (typename std::vector<T>::const_iterator it =
55  rev_binary_exponent.cbegin() + 1;
56  it != rev_binary_exponent.cend(); ++it) {
57  A = A * A % mod;
58  if (*it == 1)
59  b = A * b % mod;
60  }
61  return b;
62 }
Here is the call graph for this function:

◆ reverse_binary()

template<typename T >
std::vector<T> reverse_binary ( num)

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

Parameters
numinteger number that we want to convert
Returns
result vector of the number input in reverse binary
19  {
20  std::vector<T> result;
21  T temp = num;
22  while (temp > 0) {
23  result.push_back(temp % 2);
24  temp = temp / 2;
25  }
26  return result;
27 }
Here is the call graph for this function:

◆ tests()

void tests ( )

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

157  {
158  // First test on 2
159  assert(((void)"2 is prime but function says otherwise.\n",
160  miller_rabin_primality_test(2, 1) == true));
161  std::cout << "First test passes." << std::endl;
162  // Second test on 5
163  assert(((void)"5 should be prime but the function says otherwise.\n",
164  miller_rabin_primality_test(5, 3) == true));
165  std::cout << "Second test passes." << std::endl;
166  // Third test on 23
167  assert(((void)"23 should be prime but the function says otherwise.\n",
168  miller_rabin_primality_test(23, 3) == true));
169  std::cout << "Third test passes." << std::endl;
170  // Fourth test on 16
171  assert(((void)"16 is not a prime but the function says otherwise.\n",
172  miller_rabin_primality_test(16, 3) == false));
173  std::cout << "Fourth test passes." << std::endl;
174  // Fifth test on 27
175  assert(((void)"27 is not a prime but the function says otherwise.\n",
176  miller_rabin_primality_test(27, 3) == false));
177  std::cout << "Fifth test passes." << std::endl;
178 }
Here is the call graph for this function:
std::uniform_int_distribution
miller_rabin_primality_test
bool miller_rabin_primality_test(T num, T repeats)
Definition: miller_rabin.cpp:125
std::vector
STL class.
std::vector::size
T size(T... args)
reverse_binary
std::vector< T > reverse_binary(T num)
Definition: miller_rabin.cpp:19
power
void power(int x, int n)
Definition: power_for_huge_numbers.cpp:56
std::mt19937
std::vector::push_back
T push_back(T... args)
std::random_device
std::cout
modular_exponentiation
T modular_exponentiation(T base, const std::vector< T > &rev_binary_exponent, T mod)
Definition: miller_rabin.cpp:43
miller_test
bool miller_test(T d, T num)
Definition: miller_rabin.cpp:73
std::endl
T endl(T... args)
std::vector::cbegin
T cbegin(T... args)
std::vector::cend
T cend(T... args)
tests
void tests()
Definition: miller_rabin.cpp:157