$x_1^{x_2^{x_3}}$ mod $M$ = ?, where $x_i$ and $M$ - integers
Exponentiation by squaring isn't fast enough.
Example: http://www.wolframalpha.com/input/?i=113317^202000^102007+mod+622301
10
-
1$\begingroup$ What is the question? $\endgroup$– François G. DoraisCommented May 8, 2010 at 5:13
-
$\begingroup$ I think it is a request for an algorithm. So, to the person asking: are you actually doing this or are you just curious? $\endgroup$– Will JagyCommented May 8, 2010 at 5:19
-
$\begingroup$ I guess you want $113317^{202000^{102007}}$ modulo 622301. Well, do the inner exponentiation modulo $\phi(622301)$... $\endgroup$– JunkieCommented May 8, 2010 at 5:21
-
3$\begingroup$ @stranger: Just try first $202000^{102007}$ modulo $\phi(622301)=622300$. 1 second computation (in GP-Pari) gives 86500. Then $113317^{86500}\equiv151627$ modulo 622301 takes another second. Isn't it fast enough?! $\endgroup$– Wadim ZudilinCommented May 8, 2010 at 7:12
-
2$\begingroup$ @stranger: All that is due to Euler. He showed that $a^{\phi(m)}\equiv1\pmod m$ for $a$ coprime with $m$. This implies that $a^x\equiv a^{x\pmod{\phi(m)}}\pmod m$ and gives you the grounds of the double exponentiation. I am sorry to see that your question is closed. But I hope that you are satisfied by the knowledge you now have. $\endgroup$– Wadim ZudilinCommented May 8, 2010 at 10:45
|
Show 5 more comments