Modulus algorithm for finding a*b^c mod n, avoiding large numbers?

Question

I know the algorithm finding $ (a^b) mod\;n $ avoiding large numbers so I can code it, but I'm wondering if anyone can help me with a similar algorithm for $$ (a\cdot b^c )mod\;n $$ It's quite hard to search for. I'd like to code it in C++ so not storing numbers bigger than $2^{64}$. I'd be using values of $a,b$ and $c$ between 10 and 100, if that's useful?

Answer 1

A few things come to mind:

• additive inverses of two remainders, have the same product.
• multiplicative inverses of two remainders, multiply to the multiplicative inverse of the product.
• reducing $c$ mod $\varphi(n)$ .
• additive inverse raised to an odd exponent, is the additive inverse of the original power.
• additive inverse raised to an even exponent, is the same as the original power.
• Chinese remainder theorem.
• Polynomial remainder theorem.
• GCD reduction.
• Euler's totient theorem
• Probably a few others I've missed.

Answer 2

You want the method of squaring and multiplying, remembering that you can reduce modulo $n$ after every multiplication (or squaring). You never need a number bigger than $n^2$ at any stage, so your storage restrictions are no hindrance.