Can I calculate ((((a ^ n) ^ n) ^ ...) mod m) and (a ^ (n ^ (n ^ (...))) mod m) (b times n) effectively ?

Revision en3, by SPyofgame, 2020-06-28 03:23:38
##### 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)

#### History

Revisions

Rev. Lang. By When Δ Comment
en3 SPyofgame 2020-06-28 03:23:38 130 Tiny change: '(m)} \pmod m$$\n$$a ^ ' -> '(m)} \pmod(m)$$\n$$a ^ '
en2 SPyofgame 2020-06-28 03:17:37 68
en1 SPyofgame 2020-06-28 03:16:19 989 Initial revision (published)