How to find fast modular exponentiation?

Question

I need to find $$5448^{5^3} \pmod{11251}$$ and $$6909^{5^3} \pmod{11251}$$ fast? I couldn't calculate it with normal tricks.

Answer 1

Notice that $11251$ is prime and equal to $5^3 \cdot 90 + 1$.

$$\left(5448^{5^3}\right)^{90} \equiv 5448^{11250} \pmod{11251}$$

$$\left(6909^{5^3}\right)^{90} \equiv 6909^{11250} \pmod{11251}$$

By Fermat's little theorem,

$$\left(6909^{5^3}\right)^{90} \equiv 1 \pmod{11251}$$

$$\left(5448^{5^3}\right)^{90} \equiv 1 \pmod{11251}$$

Now we have that your two expressions are solutions $x$ to the equation

$$x^{90} \equiv 1 \pmod{11251}$$

See this answer by André Nicolas on another Math.SE question for how to finish the beast. Reducing the problem to an equation to the above form probably isn't the best way to do it, but it should work.