Richard Liu
Richard Liu

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

textsms
account_circle
email

Richard Liu

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 r…
Scan QR code to continue reading
2021-05-30