Check if an integer is prime is a good application of Divide and Conquer pattern.
The naïve algorithm is $\Theta(\sqrt{n})$ but we can use a randomized method using a Monte Carlo algorithm that is false-biased (one side error):
- If answer is “not prime”, then $n$ is surely composite (not prime)
- If answer is “ prime”, then probably $n$ is prime
The randomized algorithm is based on Fermat's little theorem: $p$ prime iff for each $a<p-1$ $a^{p-1} \mod{p}=1$.
Remember that there are numbers that are pseudo-primes, this means that some $a$ fool the Primality Test. If during the computation we discover that the number is not prime we return false (and we are sure about that $100%$ ) otherwise we return true but we are not completely sure about that (we should make more tests as possible using the function to reach some confidence about the result).
During the computation of the Primalntiation technique: $a^n=a^{n / 2 *} a^{n / 2}$ (if $n$ is even, otherwise we obviouslyity Test, for computing the power we use fast expone multiply for $a$ another time).
During the fast exponentiation we can do the nontrivial square roots test: iff $p$ is prime and $0<a<p$ then the only solutions to the equation $a^2 \bmod p=1$ are $a=1$ and $a=p-1$ .
During the fast exponentiation computation we already check if it's prime making every time $a^2 \bmod p$ .
Youtube video with good explanation about this