Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

5 Answers 5

up vote 4 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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
share|improve this answer
    
This is just the square-and-multiply algorithm... –  Brandon Carter Mar 14 '11 at 1:31

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$.

share|improve this answer

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. enter image description here

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.