What is the big-$\Omega$ complexity of Fermat's Little Theorem?
Modular exponents can be computed efficiently using repeated squaring. This is a recursive method (which can also be implemented iteratively) that relies on the following two identities:
$$
a^{2k} = (a^k)^2, \qquad a^{2k+1} = a(a^k)^2.
$$
This allows us to give a recurrence for $f(a,b,n) = a^b \bmod n$:
$$
f(a,b,n) = 
\begin{cases}
1 &amp; \text{if } b = 0, \\
f(a,b/2,n)^2 \bmod n &amp; \text{if $b$ is even}, \\
af(a,(b-1)/2,n)^2 \bmod n &amp; \text{if $b$ is odd}.
\end{cases}
$$
This shows that $a^b \bmod n$ can be computed using $O(\log b)$ many multiplications. Since we keep reducing modulo $n$ in each step, each of these multiplications takes time polynomial in $O(\log n)$ (naively, $O(\log^2 n)$, but this can be significantly improved using fast integer multiplication methods). In total, we obtain an algorithm running in polynomial time.