The Miller–Rabin test can determine if a number is not prime but cannot determine if a number is prime. How can such an algorithm be used to test for primality?
The Miller-Rabin primality test is a probabilistic algorithm that can effectively determine if a number is composite (not prime) with a high probability. While it cannot definitively prove primality, it can be used as a reliable primality test by running the algorithm multiple times.
Here's how the Miller-Rabin test works:
Given a number "n" to be tested for primality, choose a random integer "a" such that 1 < a < n-1.
Compute "r" and "s" such that n-1 = 2r * s, where "s" is an odd number.
Perform the modular exponentiation of "a" raised to the power of "s" modulo "n": x = as mod n.
If x is congruent to 1 modulo "n" or x is congruent to -1 modulo "n" (which is equivalent to x being congruent to n-1 modulo "n"), then the test is inconclusive, and "n" may be prime.
Otherwise, repeatedly square x and check if the result is congruent to -1 modulo "n." If it is, the test is inconclusive. Otherwise, continue squaring until reaching 1 modulo "n" or completing "r" iterations.
If the final result is not congruent to 1 modulo "n," then "n" is composite.
By choosing multiple random values for "a" and running the Miller-Rabin test with each value, the probability of falsely identifying a composite number as prime can be significantly reduced. The more iterations of the test are performed, the higher the confidence level in the primality determination.
While the Miller-Rabin test does not provide a deterministic proof of primality like certain algorithms such as the AKS primality test or elliptic curve primality proving, it is highly efficient and widely used in practice due to its speed and reliability. By repeating the test with different random bases, the chances of misclassifying a composite number as prime become extremely low.