most recent 30 from http://mathoverflow.net 2013-05-20T03:52:50Z http://mathoverflow.net/feeds/question/91891 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91891/fastest-algorithm-to-compute-a2nm Vincent 2012-03-22T07:54:04Z 2012-03-22T13:33:49Z

<p>Hi. </p> <p>There are well-known algorithms for cryptography to compute modular exponentiation $a^b\%c$ (like Right-to-left binary method here : <a href="http://en.wikipedia.org/wiki/Modular_exponentiation" rel="nofollow">http://en.wikipedia.org/wiki/Modular_exponentiation</a>).</p> <p>But do algorithms exist to compute modular exponentiation of the form $a^{\left(2^N\right)}\%m$ faster than with "classical" algorithms ?</p> <p>Thank you very much !</p> <p>Notes :</p> <p>1) $m$ has no particular property</p> <p>2) $N &lt; 2^{32}$</p>

http://mathoverflow.net/questions/91891/fastest-algorithm-to-compute-a2nm/91910#91910 Igor Rivin 2012-03-22T13:33:49Z 2012-03-22T13:33:49Z

<p>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.</p>