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:
- Can I improve it somehow faster where $$$n$$$ is large ($$$n \leq 10^{16}$$$) and ($$$m$$$ can be composite number)
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$$$.
Thanks for your solution ^^ New things to learn ^^
Curiously to know what would happen if $$$n$$$ is negative, we have to use modular inverse right ?
Each application of totient atleast halves the numberIt's not true ig, for example consider powers of 3.Can you provide another argument for $$$\log m$$$ bound?For each odd prime, the first totient gets 2. From that onwards, that keeps on happening (it's always even or 1) and some 2 disappears from the prime factorization.
Euler's theorem only applies to coprime $$$a$$$ and $$$m$$$. What do we do if they are not coprime?
Use CRT with some casework.
There's a generalized version which applies regardless of them being coprime or not while preserving the same complexity. It's well-explained in here.
Thanks for your solution but how to calculate totient(m) in log(m)
by precomputing smallest prime factors using
sieveand prime factorizing in $$$log2(m)$$$.A number is Pn * P(n-1) (Pn is biggest prime less than 10^6) and what complexity to prime factorizing ?
See this.
can this algorithm can calculate totient(m) in m <= 10^12 ?
No, we can't declare an array of that size. In this case we need to prime factorize it in $$$O(sqrt(N))$$$