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

Do you want to compute `[(p^p)^p]^p ... k times` or `p^(p^[p^...]...) k times`? — IVlad, Apr 24 '17 at 16:21
The problem would be easier if m was prime. You want to use the fact that a^phi(m) = 1 mod m, if gcd(a,m) = 1. — President James K. Polk, Apr 24 '17 at 16:32
I just watched a youtube video on this... [How to Break Cryptography](https://www.youtube.com/watch?v=12Q3Mrh03Gk) — Felix Castor, Apr 24 '17 at 16:34
@JamesKPolk fortunately, our `a` is prime, so `m` doesn't have to be. — IVlad, Apr 24 '17 at 16:36
@JamesKPolk I think that makes it only slightly easier: it reduces the problem to computing p^..^p (k-1 times) mod phi(m), but when you try to solve this, phi(m) won't be prime. But I guess that approach works, and phi(phi(...(m))) will quickly reduce to 1. — Paul Hankin, Apr 24 '17 at 16:36
Does this answer your question? [How to compute a^^b mod m?](https://stackoverflow.com/questions/30713648/how-to-compute-ab-mod-m) — Vesper, Mar 24 '21 at 08:09

score 3 · Answer 1 · edited May 23 '17 at 12:25

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;
}

Without any additional information I think x^x^x is x^(x^x) and NOT (x^x)^x... this would be much simpler. At least if a mathematician writes it, he means the former. — maraca, Apr 24 '17 at 16:39
@maraca yes, he clarified it's the latter. In that case, it's a duplicate of the linked question. I have made my answer CW just in case someone is interested in this version. — IVlad, Apr 24 '17 at 16:40

How do i compute a prime power tower modulo to m

1 Answers1