How do i compute a prime power tower modulo to m

Question

Here is the problem - i have been given a prime number P and a number K. I need to compute P ^ P ^ P ... k times modulo to m.

Here P is a prime number.

(P ^ (P ^ (P ^ P .... k times))) % m

Few examples

for P = 2, K = 3, m = 3

2 ^ 2 ^ 2 % 3 = 1

for P = 5, K = 3, m = 3

5 ^ 5 ^ 5 % 3 = 2

I can do a brute force but the problem is the numbers can become very large.

here are the contraints

2 <= p < 10 ^ 8
1 <= k < 10 ^ 8 
1 <= m <= 10 ^ 8

Answer 1

Assuming the exponentiation is left associative, meaning you have to compute:

[(p^p)^p]^p ... k times

---

Note: if this is a wrong assumption, then your question is a duplicate of this question. In fact, yours is easier, since p is prime.

---

Then this is equal to:

p^(p*p*p*... k times)

Which is equal to:

p^(p^k)

Using exponentiation by squaring this is doable in O(log p^k) = O(k log p)

But, this is still too much for your stated limits of p, k < 10^8.

In order to make it better, you can use some information from this answer by Douglas Zare:

you could say that a^k mod m = a^(k mod phi(m)) mod m. However, this is not always true when a and m are not relatively prime

Fortunately, a = p in our case, and p is prime, so that holds.

So your problem reduces to computing:

p^(p^k mod phi(m)) mod m

Requiring two exponentiations by squaring, which is easily doable.

See how to compute the totient function efficiently:

int phi(int n)
{    
    int result = n;   // Initialize result as n

    // Consider all prime factors of n and subtract their
    // multiples from result
    for (int p=2; p*p<=n; ++p)
    {
        // Check if p is a prime factor.
        if (n % p == 0)
        {
            // If yes, then update n and result 
            while (n % p == 0)
                n /= p;
            result -= result / p;
        }
    }

    // If n has a prime factor greater than sqrt(n)
    // (There can be at-most one such prime factor)
    if (n > 1)
        result -= result / n;
    return result;
}