SPyofgame's blog

Can I calculate ((((a ^ n) ^ n) ^ ...) mod m) and (a ^ (n ^ (n ^ (...))) mod m) (b times n) effectively ?
By SPyofgame, history, 4 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

»
4 years ago, # |
← 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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your solution ^^ New things to learn ^^

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Curiously to know what would happen if $$$n$$$ is negative, we have to use modular inverse right ?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Each application of totient atleast halves the number It's not true ig, for example consider powers of 3.Can you provide another argument for $$$\log m$$$ bound?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      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.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Euler's theorem only applies to coprime $$$a$$$ and $$$m$$$. What do we do if they are not coprime?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Use CRT with some casework.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your solution but how to calculate totient(m) in log(m)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      by precomputing smallest prime factors using sieve and prime factorizing in $$$log2(m)$$$.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        A number is Pn * P(n-1) (Pn is biggest prime less than 10^6) and what complexity to prime factorizing ?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          See this.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            can this algorithm can calculate totient(m) in m <= 10^12 ?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              No, we can't declare an array of that size. In this case we need to prime factorize it in $$$O(sqrt(N))$$$

              → Reply