The Miller-Rabin Algorithm

Fermat’s Little Theorem: For a prime number $p$, for any integer $a$, if $\gcd(a,b)=1$, then $a^{p-1}\equiv1(mod p)$

If you want to judge whether p is a prime number, then randomly x in $[2,p-1]$ every time, if $x^{p-1}\not\equiv1$ then $p$ is not a prime number.

But this is not precise enough. Introducing the second detection theorem, for an odd prime number $p$, if $a^2\equiv1(mod p)$, then $a\equiv1(mod p)$ or $a \equiv p-1 (mod p)$

We can decompose $p-1$ into $2^t*u$, and then set $x[0]=a^u mod p$, $x[i]=x[i-1]^2 mod p$, Then $x[t]=a^{p-1}$ If $x[i]=1$, then $x[i-1]$ must be equal to $1$ or $p-1$, otherwise p is not a prime number . If $x[t]\neq 1$, $p$ is also not a prime number.

Of course 2 must be judged specially. The error rate of each judgment is $\frac{1}{4}$, and the error rate after judgments of $s$ times is $(\frac{1}{4})^{s}$.

The time complexity is $O(slog_3n)$. If $p$ is large, the multiplication should be calculated using “quasi-fast powers”.

Leave a Reply

Your email address will not be published. Required fields are marked *