discrete exponential calculating

Question

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.

Answer 1

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.

Answer 2

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).