What is the best algorithm for finding the last digit of an enormous exponent? I found most answers here not clear enough for my case such as
$$
123155131514315^{4515131323164343214547}
$$
I wrote the $n\bmod10$ in Python and execution time ran out. So I need a faster algorithm or method. Sometimes, the result is incorrect as it failed the test case.
 A: First of all, you can replace the base with its $\pmod{10}$ residue. 
Then you can use the Euler-Fermat theorem: $a^{\varphi(n)}\equiv 1 \pmod{n}$ iff $\gcd(a,n)=1$. 
In particular, to determine $a^k \pmod{10}$, you have to first take $a \pmod{10}$. If it is $0$ or $5$, then you are very lucky. If it is $2,4,6,8$, then you are still lucky: the powers of these are also periodic with period $4$, so this case can be treated similarly as the next one (the reason is $\varphi(5)=4$, think about it). 
If the residue is reduced, then apply the Euler-Fermat theorem. 
Then you just need to calculate the exponent mod $\varphi(10)=4$, and replace the exponent by that number. 
In fact, there is a typical problem when you need to compute the residue of a tower like $a^{b^{c^\ldots}}$ $\pmod n$. Then you can use the Euler-Fermat theorem iteratively.
A: The other answers are good for specifically the problem of finding the last digit; and more generally, for modular exponentiation where the divisor is not too large.
But if you want more generally to calculate powers with large exponents, you need to be familiar with Exponentiation by squaring. It works whenever you have a power with an integer exponent, assuming you can do a multiplication relatively fast. The multiplication can be on any group, it needn't be integers or modular numbers. It can handle exponents like 4515131323164343214547 with ease.
Specifically, the complexity is logarithmic in the exponent, rather than linear as in naive exponentiation.
As an added bonus, if multiplication is relatively expensive and the exponent is not too large, you may want to consider optimal Addition-Chain Exponentiation.
A: If $a=10q+b$, then $a^n \equiv b^n \bmod 10$, and so it suffices to consider $b^n$, for $b = 0, 1, \dots, 9$.
These powers repeat as follows:
$0^n = 0, 0, \dots $
$1^n = 1, 1, \dots $
$2^n = 2, 4, 8, 6, 2, 4, 8, 6, \dots $
$3^n = 3, 9, 7, 1, 3, 9, 7, 1, \dots $
$4^n = 4, 6, 4, 6, \dots $
$5^n = 5, 5, \dots $
$6^n = 6, 6, \dots $
$7^n = 7, 9, 3, 1, 7, 9, 3, 1,\dots $
$8^n = 8, 4, 2, 6, 8, 4, 2, 6, \dots $
$9^n = 9, 1, 9, 1, \dots $
So, you only have to compute $n \bmod m$, where $m$ is the period corresponding to $b$, and look up the answer in the list above.
