calculating $a^b \!\mod c$ [duplicate]

What is the fastest way (general method) to calculate the quantity $a^b \!\mod c$? For example $a=2205$, $b=23$, $c=4891$.

Solution 1:

Let's assume that a,b,c referred to here are positive integers, as in your example.

For a specific exponent b, there may be a faster (shorter) method of computing a^b than binary exponentiation. Knuth has a discussion of the phenomenon in Art of Computer Programming Vol. 2 (Semi-numerical Algorithms), Sec. 4.6.3 and the index term "addition chains". He cites b=15 as the smallest case where binary exponentiation is not optimal, in that it requires six multiplication but a^3 can be computed in two multiplications, and then (a^3)^5 in three more for a total of five multiplications.

For the specific exponent b=23 the parsimonious addition chain involves the exponents (above 1) 2,3,5,10,13, at which point a^23 = (a^10)*(a^13), for a total of six multiplications. Binary exponentiation for b=23 requires seven multiplications.

Another approach that can produce faster results when b is large (not in your example) depends on knowing something about the base a and modulus c. Recall from Euler's generalization of Fermat's Little Thm. that if a,c are coprime, then a^d = 1 mod c for d the Euler phi function of c (the number of positive integers less than c and coprime to it). In particular if c is a prime, then by Fermat's Little Thm. either c divides a and a^b = 0 mod c or else a^b = a^e mod c where e = b mod (c-1) since phi(c) = c-1 for a prime c.

If the base a and modulus c are not coprime, then it might be advantageous to factor a into its greatest common factor with c and its largest factor that is coprime to c.

Also it might be advantageous if c is not prime to factor it into prime powers and do separate exponentiations for each such factor, piecing them back together via the Chinese Remainder Thm. In your example c = 4891 = 67*73, so you might compute a^b mod 67 and a^b mod 73 and combine those results to get a^b mod c. This is especially helpful if you are limited in the precision of integer arithmetic you can do.

Solution 2:

The square-and-multiply algorithm is generally the fastest way to do modular exponentiation.

Solution 3:

The Russian peasant's method is pretty straightforward for computing $a^b\bmod m$:

c=a;d=b;r=1;
while d≠0
if d is odd then r=(cr) mod m;
d=d div 2; \\ integer division; one usually right-shifts bits in practice
c=c^2 mod m;
endwhile
r

Solution 4:

One common way of fast exponentiation, either in modular arithmetic or in general, is exponentiation by squaring. Here is the section where they talk specifically about $a^b\bmod c$.

Solution 5:

Generally repeated squaring works well. It deserves to be better known that this arises simply from writing the exponent in binary radix in Horner polynomial form, i.e. $\rm\ d_0 + x\ (d_1 + x\ (d_2\ +\:\cdots))\:.\ $ Below is an example of computing $\rm\ a^{101}\ $ by repeated squaring. Note that the repeated square form arises simply from performing various substitutions into the binary polynomial Horner form namely $\rm\ 1\to a,\ \ 0\to 1,\ \ (x)\:2\to (x)^2\ $ into $101_{10} = 1100101_2\ $ expanded into Horner form, viz.