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

Question

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 algorithm exist to compute modular exponentiation of the form (a^(2^N))%m faster than with "classical" algorithms ?

Thank you very much !

Note :

1) m can be a very large prime ... or not (so no optimization depending on m)

2) N can be as large as 2^32-1 (N < 2^32)

Answer 1

If m is a prime, you can compute this much faster.

You start with computing of p = 2^N % (m-1) with right-to-left binary method.

Then you use right-to-left binary method to compute a^p % m, which is equal to the original expression because of Fermat's little theorem.

---

If m is not prime, but small enough, so that it can be factored, you can compute Euler's totient function and use Euler's Theorem.

If no optimization depending on m is possible, probably the best you can do is using Montgomery reduction.

Answer 2

Also, as a generalization to Evgeny's answer: if you know the factorization of m: m = p1 * p2 * ... * p{n}, you can use Euler's theorem:

Calculate the totient phi(m)= (p1-1)*(p2-1)*...*(p{n}-1).

Then you can compute p = 2^N % phi(m) and find that a^(2^N) % m = a^p % m.

None of this uses the special form of 2^N, however.