The **Miller–Rabin primality test** or **Rabin–Miller primality test** is a probabilistic primality test: an algorithm which determines whether a given number is a *strong probable prime*. > [!NOTE] Definition (Miller–Rabin test algorithm) > **Input**: $n>2$, an odd [[Natural Numbers|natural number]] to be tested for primality. $k,$ the number of rounds of testing to perform > >**Output**: “composite” if $n$ is found to be composite, “_probably prime_” otherwise. > >**Procedure**: >1. Let $s>0$ and $q$ odd so that $n-1=2^{s}q.$ >2. Pick a random $a\in[2,3,\dots,n-1]$ >3. If $a^{q} \equiv 1 \pmod{n}$ then $n$ passes, otherwise it is composite >4. If $n$ passes, for $i=0,\dots,s-1$ see if $a^{2^{i}q}\equiv -1 \pmod{n}.$ If so $n$ passes >5. Repeat (2)-(4) $k-1$ more times. > .... > [!NOTE] Proposition (Odd Primes are strong probable primes) > vnm Proof. ... # Properties Time complexity: Implementation in python: ```run-python ```