# Miller-Rabin primality test a method for testing if a given number is prime with high probability. It is enhancement to Fermat's little theorem. The idea[^1] is to combine Fermat's little theorem and a simple exercise that for prime $p$, (1) if $x^2\equiv 1 \bmod p$ then $x\equiv 1 \bmod p$ or $x\equiv -1 \bmod p$. If $x$ satisfies Fermat little theorem for prime $p$, then $x^{p-1}\equiv 1\bmod p$ . Let $p-1=2^st$ where $t$ is odd. We have, $1\equiv x^{p-1}=x^{2^st}=\big({x^{2^{s-1}t}\big)^2}\bmod p$And so by (1) $x^{2^{s-1}t}\equiv \pm 1\bmod p$ . if $x^{2^{s-1}t}\equiv -1\bmod p$ this means $p$ can be a prime. and if $x^{2^{s-1}t}\equiv 1\bmod p$, then we can repeat the argument until we get -1 for the first $i$ or reaching $x^t\equiv \pm 1\bmod p$. The more we are able to iterate the larger the probability that p is prime. Repeating this test for multiple random values of $x$ increase the probability that p is prime. The algorithm is based on this analysis only it starts from bottom of $x^t$ and continue by squaring until we reach $x^{2^st}$ . if $x^t\equiv\pm 1$ then it's squaring should be 1 so we terminate that $p$ might be a prime. Otherwise, if $x^t\not\equiv\pm 1$ then squaring it need to reach -1 for some $s-i$ as we know that after $s$ squaring it must be 1 and so its square root is $\pm1$ and if it is -1 we done and if not we can continue. as we know $x^t\not\equiv\pm 1$ then some s must exist. So, we keep squaring and checking by increasing $s$ values and check if $x^{2^{s-1}t}\equiv -1\bmod p$ . otherwise, we continue squaring and checking. Tag: #math #tech #random ## Created 2024-10-22 19:07 [^1]: [[@prime numbers a computation perspective]]