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

• 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 ^ {(...)})})} \mod m}^{b\ times\ n}$$$

• 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

• Can I apply the formula from phi-function -> $$$a ^ n \equiv a ^ {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)