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