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)
If m is a prime, you can compute this much faster.
You start with computing of p = 2N % (m-1) with right-to-left binary method.
Then you use right-to-left binary method to compute ap % 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.