discrete exponential calculating I am interested in discrete exponential calculating.
I know that $a^b = c\mod k$ is calculated as below.  For example $3^4 = 13 \mod 17$.  $3^4 = 81$; $81 \mod 17 = 13$.
I am interested in big numbers. For example $12356423547^{72389478972138} \mod 1239859034832$
This calculation is more difficult . And I don't think it is possible to calculate this expression without any simplification.
I have researched some ways to simplify this equalization. And I found that
$a^b \mod k = a^{(b \mod \log(a,1)) \mod k}$
$\log(a,b)$ is discrete logarithm where $a$ is base.
Of course this is simpler from $a^b$ but not enough simple.
In very big calculations this way isn't useful. For example in $128$ bit public keys $a$ and $b$ will be $128$ bit integers (for example). I am interested in that. Is there any simplification formula to calculate big numbers exponential in real time?
Thank you.
 A: You can calculate $a^b$ with $O(\log b)$ multiplications (using $a^{2k}=a^k\cdot a^k$ and $a^{2k+1}=a^{2k}\cdot a$). Of course, to actually compute $a^b$ you'd need to work with big numbers.
But to compute $a^b\bmod c$, you can work $\bmod c$ throughout and thus don't have to worry about growing intermediate results.
That is: If $a,b,c$ are $128$ bit numbers, then you can get along with $128$-$255$ multiplications of two $128$ bit numbers (producing a $256$ bit intermediate result, which you immediately reduce $\bmod c$ to $128$ bits again).
A: Powers can be calculated quickly by a technique called repeated squaring. For example, \[3^{32} = (((((3^2)^2)^2)^2)^2)\]
When the exponent is not a power of two, you write it as a sum of powers of two, and use the fact that $a^{b + c} = a^b a^c$. So, for example, \[3^{43} = 3^{32} \times 3^{8} \times 3^{2} \times 3\], and since we re-use $3^2$ in calculating $3^8$, we can do the whole calculation in just eight multiplications.
You can also do the squaring with respect to your modulus, as Hagen von Eitzen explained. So to calculate $3^{43} \mod 17$, I'd do the following:


*

*$3^2 = 9$ 

*$3^4 = 9^2 = 81 = -4 \mod 17$ (the only multiplication step here is $9^2 = 81$)

*$3^8 = (-4)^2 = 16 = -1$ (from now on, I'll just leave all the mod-17 implicit)

*$3^{16} = (-1)^2 = 1$

*$3^{32} = 1^2 = 1$


and now:


*

*$3^3 = 3 \times 3^2 = 3 \times 9 = 27 = 10$

*$3^{11} = 3^3 \times 3^8 = 10 \times (-1) = 7$

*$3^{43} = 3^{11} \times 3^{32} = 7 \times 1 = 7$


So the answer is $7$, all through calculations I did in my head. I've set it out so that only one multiplication is done per line.
In fact, I could have used some more theoretical results to determine that $3^{16} = 1$ straight away (Carmichael's Theorem) and hence $3^{43} = 3^{11} \times 3^{16} \times 3^{16} = 3^{11}$, which would have made it even faster. Because of Carmichael's Theorem, you never need to worry about an exponent that's bigger than the modulus.
