How can I efficiently calculate $a^k \bmod m$ where $a,k,m$ are very large numbers and $k$ might be up to $10^9$ or more, $a$ might be up to $10^6$.
Here $a$ is a prime but $k$ and $m$ might not be primes.
Is my only option to calculate $a^1 \bmod m$, $a^2 \bmod m$, $a^4 \bmod m$ etc or is there any way to reduce $k$ to a smaller number?