logarithms - discrete exponential calculating

I am interesting in about 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 interesting about 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 I have researched some ways to simplification 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 more simply from $a^b$ but not enough simply .

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 interesting about that .Is there any simplification formula to calculate big numbers exponential in real time?
thank you

Answer

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.