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}$

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ It is hard to imagine beating repeated squaring. $\endgroup$
    – Steve Huntsman
    Commented 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$
    – Gerhard Paseman
    Commented 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$
    – Gerhard Paseman
    Commented 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$
    – Gerhard Paseman
    Commented 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$
    – Jeremy Teitelbaum
    Commented Mar 22, 2012 at 15:53

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .