In this repo miller rabin primality test is discussed.
Algorithm:
// Reurn false is n is non prime and returns true if n
// is probably prime. value is an input parameter that determines
// accuracy level. Higher value of value indicates more accuracy.
bool isPrime(int n, int value)
1) Handle base cases for n < 3
2) If n is even, becuase even number will be divisible by 2 return false.
3) Find any odd number d such that n-1 can be express or written as d*2r.
Note that since n is odd, (n-1) must be even and r must be
greater than 0.
4) Do following k times
if (millerTest(n, d) == false)
return false
5) Return true.
// This function is called for all value trials. It returns
// false if n is non prime or composite number and returns true if n is probably
// prime.
// d is an odd number such that d*2r = n-1 for some r >= 1
bool millerTest(int n, int d)
- Select number 'a' between range [2, n-2]
- Compute: x = pow(a, d) % n
- If x == 1 or x == n-1, return true.
// Below loop mainly runs 'r-1' times.
4) Do following while d doesn't become n-1.
a) x = (x*x) % n.
b) If (x == 1) return false.
c) If (x == n-1) return true.
Example:
Input: n = 13, value = 2.
- Compute d and r such that d*2r = n-1, d = 3, r = 2.
- Call millerTest value times.
1st Iteration:
Select number 'a' between range [2, n-2] Suppose a = 4
Compute: x = pow(a, d) % n x = 43 % 13 = 12
Since x = (n-1), return true.
IInd Iteration:
Pick a random number 'a' in range [2, n-2] Suppose a = 5
Compute: x = pow(a, d) % n x = 53 % 13 = 8
x neither 1 nor 12.
Do following (r-1) = 1 times a) x = (x * x) % 13 = (8 * 8) % 13 = 12 b) Since x = (n-1), return true.
Since both iterations return true, we return true.