Modular arithmetic for large values

Question

Form: $A\cdot B^C \mod p$

Example: $882\cdot (49^{2491}) \mod{2591}$

Trivial division seems like a hassle to do for this, likewise with fermat factorization. Are there any other methods I'm missing to complete this?

Answer 1

We have that $p=2591$ is prime, so we know that $a^{2590}\equiv 1$ for any $a$ that's not a multiple of $p$. We can write $49^{2491}$ as $7^{2\cdot 2491}=7^{4982}\equiv 7^{4982-2590}\equiv 7^{2392}$. Meanwhile, $882=2\cdot 3^2\cdot 7^2$. Thus, the left-hand side is congruent to $2\cdot 3^2\cdot 7^{2394}$. Clearly, the power of $7$ is the tricky part.

I would write the exponent in binary: $2394_{10}=100101011010_2$. This tells us that $$7^{2394}=7^{2^1+2^3+2^4+2^6+2^8+2^{11}}=7^2\cdot7^8\cdots7^{2048}$$

These power-of-two powers of $7$ can be found by repeatedly squaring, and reducing by the modulus when necessary. Thus:

$7^2=49\\ 7^4=49^2=2401\equiv -190\\ 7^8\equiv(-190)^2\equiv 36100\equiv 2417\equiv-174$

...etc. (This part of the calculation can be really quick and efficient if you use a spreadsheet.)

Once you have all the desired powers of $7$, you can multiply them together, along with your $2\cdot 3^2$, reducing modulo $2591$ anytime the numbers get big.

Answer 2

Calculations can be made in various ways, which depend on the values of $ A, B, C $. For the given case, we have in the finite field $\mathbb F_{2591}$

$$882\cdot49^{2491}= \pmod{25}\iff 18\cdot49^{2492}=x\iff 18= 49^{98} x$$ $$18= 49^{98} x=(((49)^2)^7)^7 x=((2401)^7)^7 x=(532)^7 x=730\space x\iff9=365\space x$$ $$9=365\space x\iff9\cdot365^{-1}= x$$ What remains is to calculate the inverse of $365$. Calculation analogue gives $2087$ and finally $$9\cdot365^{-1}=9\cdot2087=18783=\color{red}{646= x}$$