Copyright 2020
- Author
- tjgurwara99
A basic implementation of 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.
125 {
126 if (num <= 4) {
127
128 if (num == 2 || num == 3) {
129 return true;
130 } else {
131 return false;
132 }
133 }
134
135 if (num % 2 == 0) {
136 return false;
137 }
138
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) {
147 return false;
148 }
149 }
150 return true;
151}
bool miller_test(T d, T num)
Definition miller_rabin.cpp:73