Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
please check that I got the formatting correct. –  Amzoti Feb 19 '13 at 21:49
add comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.