Miller-Rabin Test for Primes is one of the most popular methods for testing for prime numbers used in RSA. Given an odd number (\(n\)), we will have an odd number of (\(n-1\)), of which we can calculate the power of 2 with a value of \(s\) so that \(n-1 = 2^s d\). For example, if \(n\) is 25, \((n-1)\) will be 24, and which is \(2 \times 2 \times 2 \times 3\) and which is \(2^3 \times 3\). We then select a random value of \(a\) and which is between 1 and \((n-1)\). We may have a prime if one of the following is true:
- \(a^{d} \pmod{n} \equiv 1\)
- \(a^{2^r \cdot d} \equiv -1 \pmod n\)
and where \(r\) is a value between 0 and \(s-1\).