0

Is there a way to calculate $2^n \pmod{14^8}$ faster than binary exponentiation? The $n$ values in question are very large, for example $2^{65536}$, and the calculations have to be done around $14^8$ times. The ultimate goal is to calculate numbers that use Knuth's up-arrow notation. Maybe the Chinese Remainder Theorem can be used here to reduce the problem space from $14^8$ to $7^8$ or further, as I am using arrays to memoize values.

qwr
  • 10,716
  • 1
    You could at least use the chinese remainder theorem to reduce it to a $\mod 7^8$ problem. – zibadawa timmy Jul 17 '15 at 22:21
  • @zibadawatimmy Any method to reduce the modulus, especially on the order of $10^6$, will be very useful in computation – qwr Jul 17 '15 at 22:24
  • http://guan.cse.nsysu.edu.tw/note/expn.pdf There are several algorithms listed here. Most of them are modified versions of the binary method, but they might help some. As was pointed out by @zibadawatimmy you could reduce the numbers somewhat based on their factors. – Terra Hyde Jul 18 '15 at 00:42
  • Binary exponentiation would only require 16 steps; that's not too much... – msinghal Jul 18 '15 at 05:18
  • @MihirSinghal I don't think that is correct. I am dealing with $ 2^{2^{65536}} $ here. – qwr Jul 19 '15 at 01:22
  • Roughly on what time frame do the ~$14^{8}$ calculations need to be completed? –  Jul 19 '15 at 02:46

1 Answers1

1

I've found the answer given here. In summary, divide $14^8$ by $2^8$, and use Euler's theorem to find the exponent $\mod \varphi(7^8)$.

Community
  • 1
qwr
  • 10,716