How to calc $ a^{2^n}$ mod $m$ in less than O(n) time?

Question

a,m are positive integers. if needed, you can assume m is a prime.

Is there any fast algorithm?

I'm sorry for my not clear description.

Answer 1

If $m$ is a prime, you can reduce the exponent $$ \large a^{2^n}\equiv a^{2^n \operatorname{mod} (m-1)} \pmod m$$ where the $mod$ means the modulo - operator, defined as $ \operatorname{mod}$ in many programming languages. The topmost exponent can even be reduced modulo $\varphi(m-1)$, but here we have possibly to respect initial corrections for small $n$ if $\varphi(m-1)$ and $2^n$ have a common factor (which is always true if $m$ is an odd prime).

For instance, if $m=7$ then $ \varphi(7-1) = \varphi(6) = 2$ and $$a^{2^n} \operatorname{mod} 7 \equiv a^{2^n \operatorname{mod} 6} \operatorname{mod} 7$$ so either $n$ is zero, then $$a^{2^n} \equiv a^1 \pmod 7$$ or $n$ is odd, then $$a^{2^n} \equiv a^2 \pmod 7$$ or $n$ is even $\gt 0$, then $$a^{2^n} \equiv a^4 \pmod 7$$ because $2^n \pmod 6$ is $1$ if $n=0$ or else $2\cdot 2^{n \operatorname{mod} \varphi(6)} = 2\cdot 2^{n \operatorname{mod} 2}$

This reduces the load of computation much...