Finding big exponential value How to find the following most efficiently
$$
A^{x} \bmod M
$$
where $A,x\le10^{10}$ and $M$ is a quite big prime number.
 A: One posibility is to use exponentiation by squaring. Let us start with an example: suppose you want to compute $A^5$ for some $A$. The naive method requires $4$ multiplications: $A \cdot A \cdot A \cdot A \cdot A$. The smart method writes the exponent in base $2$ as $5 = 2^2 + 1$ and then $A^5 = {(A^2)}^2 A$, which only requires $3$ multiplications.
In general, one may define exponentiation recursively: $exp(A,x) = 1$ if $x=0$, $exp(A,x)=exp(A,\frac x 2) exp(A,\frac x 2)$ if $x$ is even and finally $exp(A,x)=exp(A,x-1) A$ (if $x$ is odd). Note that all multiplications are modular!
So now you need an efficient algorithm for multiplication. Binary multiplication is a good choice (but not the only one possible). Assume that you want to compute $mul(A,B) = A \cdot B \mod M$. First, test which number is the smallest (let us assume it is $B$). Now, use recursion on $B$: $mul(A,B) = 0$ if $B=0$, $mul(A,B)=mul(A,\frac B 2) + mul(A,\frac B 2)$ if $B$ is even and finally $mul(A,B) = mul(A,B-1) + A$ (if $B$ is odd). Sometimes the step for $B$ even can be replaced with a "shift left" which is usually implemented in hardware and thus faster. Note that all additions are modular!
Therefore, everything that you need to implement is an algorithm for modular addition (usually you may find this in libraries).
If your language permits, rewrite the above recursive functions in tail-recursive style for a small speed-up.
The biggest slowdown will come from the fact that, if your number are larger than $64$ bits, you will have to store them as "big numbers" (i.e. lists), and memory accesses are the real time penalty here, not the CPU. You may find "big numbers" ("big ints") already implemented as libraries or even built in, depending on your language.
Finally, some scientific languages (such as Wolfram Mathematica) already implement all these smart algorithms, so at this basic level just use their functions without worrying about optimizations.
A: You can always use Montgomery modular exponentation. If $n$ is the number of digits of M, we have that the running time is $O(n \ln n \cdot 2^{\log^*n})$. (Assuming you use Fürer's algortihm for multiplication)
