MillerRabins

The Miller-Rabin primality test is a probabilistic algorithm used to determine whether a given number is prime. It was developed by Gary L. Miller and Michael O. Rabin in 1976. The algorithm is based on Fermat's Little Theorem, which states that if p is a prime number and a is an integer not divisible by p, then a^(p-1) ≡ 1 (mod p). The Miller-Rabin test extends this theorem by expressing p-1 as 2^s * d, where d is an odd number, and then checking if a^d ≡ 1 (mod p) or if a^(2^r * d) ≡ -1 (mod p) for some r in the range 0 ≤ r < s. If these conditions are not met, then p is composite. The test can be repeated with different values of a to increase the probability of correctly identifying a prime number. The number of iterations can be adjusted based on the desired level of confidence. The Miller-Rabin test is widely used in cryptography and computer science due to its efficiency and effectiveness in identifying prime numbers.