SPyofgame's blog

Can I calculate ((((a ^ n) ^ n) ^ ...) mod m) and (a ^ (n ^ (n ^ (...))) mod m) (b times n) effectively ?
By SPyofgame, history, 6 years ago, In English
In problem $$$\overbrace{(((a ^ n) ^ {{}^n}) ^ {{}^{{}^{...}}})}^{b\ times\ n} \mod m$$$

  • My approach is calculating each part $$$((a ^ n) \mod m)$$$ then $$$(((a ^ n) ^ n) \mod m) = ((t ^ n) \mod m)$$$ ... all together in $$$O(\log n)$$$ each part and $$$O(b \times \log n)$$$ total time complexity

  • Can I improve it somehow faster where $$$b$$$ is large ($$$b \leq 10^{16}$$$) and ($$$m$$$ can be composite number)

In problem $$$\overbrace{a ^ {(n ^ {(n ^ {(...)})})}}^{b\ times\ n} \mod m$$$

  • I only know the way to use bignum to calculate $$$n ^ n$$$ then $$$n ^ {n ^ n}$$$ all together then I just have to calculate the modulo of $$$a ^ {...} \mod m$$$ but the total complexity will be very huge (since the number of digits of bignum will raise very fast)

  • Can I apply these formula from phi-function:

$$$a ^ {\phi(m)} \equiv 1 \pmod m$$$
$$$a ^ n \equiv a ^ {n \mod \phi(m)} \pmod m$$$
$$$a ^ n \equiv a ^ {\phi(m) + (n \mod \phi(m))} \pmod m$$$
  • Can I improve it somehow faster where $$$n$$$ is large ($$$n \leq 10^{16}$$$) and ($$$m$$$ can be composite number)
  • Vote: I like it
  • +76
  • Vote: I do not like it

»
6 years ago, hide # |
← Rev. 3  
Vote: I like it +43 Vote: I do not like it

For the first problem, note that (a^n)^n = a^(n^2). So you just want to compute a^(n^b) = a^(n^b mod totient(m)) mod m, by Euler's theorem. Complexity is $$$O(\log b + \log m)$$$.

For the second problem a^(n^(n^(....))) mod m = a^(n^(n^(....)) mod totient(m)) mod m = a^(n^(n^(....) mod totient(totient(m))) mod totient(m)) mod m, and so on. After about $$$\log m$$$ applications of totient, it becomes 1. (Each application of totient function at least halves the number) So, the complexity is $$$\log^2 m$$$.

→ Reply