MillerRabinAlgorithm.md (520B)
1 # Miller-Rabin Algorithm 2 3 **Source:** Computer and Network Security 4 5 **Chapter:** 2.6 6 7 **Definition:** The Miller-Rabin Algorithm uses the knowledge that if $n$ is prime then either the first element in the list of residues modulo $n$ equals 1; or some element in the list equals ($n-1$); otherwise $n$ is composite. This only guarantees a number is likely prime because this is necessary but not sufficient. 8 9 ## Background 10 11 Any positive odd integer $n \geq 3$ can be stated as $n - 1 = 2^k q$ with $k \gt 0, q$ is odd.