5
$\begingroup$

Hi.

There are well-known algorithms for cryptography to compute modular exponentiation $a^b\%c$ (like Right-to-left binary method here : http://en.wikipedia.org/wiki/Modular_exponentiation).

But do algorithms exist to compute modular exponentiation of the form $a^{\left(2^N\right)}\%m$ faster than with "classical" algorithms ?

Thank you very much !

Notes :

1) $m$ has no particular property

2) $N < 2^{32}$

$\endgroup$
6
  • 3
    $\begingroup$ It is hard to imagine beating repeated squaring. $\endgroup$ Mar 22, 2012 at 9:33
  • $\begingroup$ You could start with repeated fourth powers. Gerhard "Does Like Repeated Squaring Though" Paseman, 2012.03.22 $\endgroup$ Mar 22, 2012 at 10:21
  • $\begingroup$ In fact, repeated squaring of 2 mod p-1 for prime powers p dividing m could have some speed advantage for large N. Gerhard "Really Does Like Repeated Squaring" Paseman, 2012.03.22 $\endgroup$ Mar 22, 2012 at 10:27
  • $\begingroup$ I think I mean mod phi(p) instead of mod p-1 above. Gerhard "Going Back To Sleep Now" Paseman, 2012.03.22 $\endgroup$ Mar 22, 2012 at 10:31
  • $\begingroup$ This might be helpful. Note the reference to Knuth. He discusses computing x^n mod p faster than repeated squaring by algorithms depending on n. stackoverflow.com/questions/101439/… $\endgroup$ Mar 22, 2012 at 15:53

1 Answer 1

5
$\begingroup$

I am not sure I understand the question, but if $m \ll 2^N,$ the obvious thing to do is to compute $x = 2^N \mod \phi(m)$ [by repeated squaring], and then compute $a^x \mod m.$ If $2^N$ is not huge compared to $m$ then factoring $m$ might dominate.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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