How to find the modular reduction of a very large number.

Question

Suppose I want to calculate the modulus of a number raised to a number of powers, as in $$94^{{93}^{92 ^{{...}^1}}} \equiv x \pmod {265}$$

Is there a way to compute x , using a computerized method? (without actually computing the power)

Answer 1

Suppose you have the following problem $$a^n\equiv ?\pmod b,$$ then a technique that often helps in reducing large powers is as follows. Find $\phi(b)$ and express $n$ in the following form $$n=\phi(b)q+r,0\leq r<\phi(b)$$ which is Euclidean Algorithm. Now by Euler's Theorem $$a^{\phi(b)}\equiv 1\pmod b$$ therefore $$a^n\equiv a^{\phi(b)q+r}\equiv a^{r}\pmod b.$$ This should help in reducing the computations.

If you have a tower (eg. $2^{2^2..}$) then a wise thing would be to begin at the top of the tower and apply this algorithm again and again.