# Fastest algorithm to compute (a^(2^N))%m?

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

-
It is hard to imagine beating repeated squaring. –  Steve Huntsman Mar 22 '12 at 9:33
You could start with repeated fourth powers. Gerhard "Does Like Repeated Squaring Though" Paseman, 2012.03.22 –  Gerhard Paseman Mar 22 '12 at 10:21
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 –  Gerhard Paseman Mar 22 '12 at 10:27
I think I mean mod phi(p) instead of mod p-1 above. Gerhard "Going Back To Sleep Now" Paseman, 2012.03.22 –  Gerhard Paseman Mar 22 '12 at 10:31
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/… –  Jeremy Teitelbaum Mar 22 '12 at 15:53
show 1 more comment

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.