Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
3  
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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