6
$\begingroup$

Let $a\uparrow^{n} b $ denote the indexed version of Knuth's up-arrow notation ($a \uparrow\uparrow \dots \uparrow b$ with $n$ arrows), with $a, b, n$ positive integers.

Is there a generalized algorithm to compute $a\uparrow^{n} b$ modulo a prime efficiently? How does the complexity of such an algorithm depend on $n$? What if we restrict $a$ and $b$ to also be prime, or if we remove the requirement for $p$ to be prime?

$\endgroup$
2
$\begingroup$

Maybe.

Consider the problem of calculating $a^{a^b} \bmod p$. What we do here is calculate $x = a^b \bmod (p-1)$, which is the exponent we need to do $a^x \bmod p$, which is our answer. This is due to Fermat's Little Theorem, which states that for prime $p$:

$a^{p-1} \equiv 1 \bmod p$

You may notice that this intermediate exponential is smaller. Also, given a composite modulus, we can break it into factors, calculate for each of the those factors separately and combine with the Chinese Remainder Theorem. So the modulus can shrink pretty fast.

This means that a power tower can only grow to a certain size, beyond which the modulus used to calculate the upper parts of the tower is zero, so the part of the tower above that threshold has no effect on the result.

So tetration at least may be easier than it would at first appear. That said, there is also the requirement that you can swiftly factorize p, which makes large p difficult to work with.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.