How do I efficiently compute $a^b\,\bmod c$:
Are there any other tricks for evaluating exponents in modular arithmetic?
This is being asked in an effort to cut down on duplicates, see here: Coping with *abstract* duplicate questions.
and here: List of Generalizations of Common Questions
Wikipage on modular arithmetic is not bad.
When $b$ is huge, and $a$ and $c$ are coprime, Euler’s theorem applies:
$$
a^b \equiv a^{b \, \bmod \, \phi(c)} \, \bmod c
$$
For the example at hand, $\phi(21) = \phi(3) \times \phi(7) = 2 \times 6 = 12$. $ 844325 \bmod 12 = 5$, so $5^5 = 5 \times 25^2 \equiv 5 \times 4^2 = 80 \equiv 17 \mod 21$.
When $a$ and $c$ are coprime, but $0<b<\phi(c)$, repeated squaring (or using other compositions of powers) is the fastest way to go (manually):
$$
\begin{eqnarray}
5^4 \equiv 5 \times 5^3 \equiv 5 \times 24 \equiv 19 &\pmod{101}\\
19^4 \equiv (19^2)^2 \equiv 58^2 \equiv (-43)^2 \equiv 1849 \equiv 31 &\pmod{101} \\
31^4 \equiv (31^2)^2 \equiv (961)^2 \equiv 52^2 \equiv 2704 \equiv 78 &\pmod{101} \\
5^{69} \equiv 5 \times 5^4 \times ((5^4)^4)^4 \equiv 5 \times 19 \times 78 \equiv 5 \times 19 \times (-23)\\
\equiv 19 \times (-14) \equiv -266 \equiv 37 & \pmod{101}
\end{eqnarray}
$$
When $a$ and $c$ are not coprime, let $g = \gcd(a,c)$. Let $a = g \times d$ and $c = g \times f$, then, assuming $b > 1$:
$$
a^b \bmod c = g^b \times d^b \bmod (g \times f) = ( g \times (g^{b-1} d^b \bmod f) ) \bmod c
$$
In the example given, $\gcd(6,14) = 2$. So $2^{102} \times 3^{103} \mod 7$, using Euler’r theorem, with $\phi(7) = 6$, and $102 \equiv 0 \mod 6$, $2^{102} \times 3^{103} \equiv 3 \mod 7$, so $6^{103} \equiv (2 \times 3) \equiv 6 \mod 14 $.
Let’s try $5^{844325} \bmod 21$:
$$
\begin{align}
5^0 & & & \equiv 1 \\
5^1 & & &\equiv 5 \\
5^2 & \equiv 25 & & \equiv 4 \\
5^3 & \equiv 4\cdot 5 & & \equiv 20 \\
5^4 & \equiv 20\cdot 5 & & \equiv 16 \\
5^5 & \equiv 16\cdot 5 & & \equiv 17 \\
5^6 & \equiv 17\cdot 5 & & \equiv 1
\end{align}
$$
So multiplying by $5$ six times is the same as multiplying by $1$. We want to multiply by $5$ a large number of times: $844325$. How many times do we multiply by $5$ six times? The number of times $6$ goes into $844325$ is $140720$ with a remainder of $5$. That remainder is what matters. Multiply by $5^6$ exactly $140720$ times and that’s the same as multiplying by $1$ that many times. Then multiply by $5$ just $5$ more times, and get $17$.
So $5^{844325} \equiv 17 \bmod 21$.
Here are two examples of the square and multiply method for $5^{69} \bmod 101$:
$$ \begin{matrix}
5^{69} &\equiv& 5 &\cdot &(5^{34})^2 &\equiv & 37
\\ 5^{34} &\equiv& &&(5^{17})^2 &\equiv& 88 &(\equiv -13)
\\ 5^{17} &\equiv& 5 &\cdot &(5^8)^2 &\equiv& 54
\\ 5^{8} &\equiv& &&(5^4)^2 &\equiv& 58
\\ 5^{4} &\equiv& &&(5^2)^2 &\equiv& 19
\\ 5^{2} &\equiv& &&(5^1)^2 &\equiv& 25
\\ 5^{1} &\equiv& 5 &\cdot &(1)^2 &\equiv& 5
\end{matrix} $$
The computation proceeds by starting with $5^{69}$ and then working downward to create the first two columns, then computing the results from the bottom up. (normally you’d skip the last line; I put it there to clarify the next paragraph)
As a shortcut, the binary representation of $69$ is $1000101_2$; reading the binary digits from left to right tell us the operations to do starting from the value $1$: $0$ says “square” and $1$ says “square and multiply by $5$”.
The other way is to compute a list of repeated squares:
$$ \begin{matrix}
5^1 &\equiv& 5
\\ 5^2 &\equiv& 25
\\ 5^4 &\equiv& 19
\\ 5^8 &\equiv& 58
\\ 5^{16} &\equiv& 31
\\ 5^{32} &\equiv& 52
\\ 5^{64} &\equiv& 78
\end{matrix} $$
Then work out which terms you need to multiply together:
$$ 5^{69} \equiv 5^{64 + 4 + 1} \equiv 78 \cdot 19 \cdot 5 \equiv 37 $$
Some tricks which are useful for modular exponentiation
The intention of this post is to collect various tricks which can sometimes simplify computations of this type. (Especially when done by hand and not using computer or calculator.) This post is community-wiki, so feel free to edit it if you have some ideas for improvements.
Using complement: $(c-a) \equiv (-a) \pmod c$
If the given number is close to $c$ (but smaller than $c$), replacing it by $c-a$ my help us – we will work with smaller numbers. Some examples:
If you can find a power which is close to the modulo, try to use it
Some examples:
Using Euler’s criterion
Euler’s criterion can tell us about value of $a^{\frac{p-1}2}$ modulo a prime $p$. However, we need to know whether $a$ is a quadratic residue modulo $p$. For some numbers this can be guessed. Sometimes this can be checked using quadratic reciprocity (Of course, this is not much of an improvement in comparison with Fermat’s little theorem, which gives us $a^{p-1}\equiv1\pmod p$.)
In general, squared exponentiation is used, this is $O(\log(b) \cdot \log(n))$ if multiplication $\bmod n$ is $O(\log (n))$.
powmod(a,b,n){
res=1;
fact=a;
while(b>0){
res=(res*(b%2)==1?fact:1)%n;
fact=(fact*fact)%n;
b=floor(b/2);
}
}
when $b$ is huge (much larger than $n$) you can (attempt) to find the rank of the ring ($\varphi(n)$) and find the remainder of $b \pmod {\varphi(n)}$ because $a^b \bmod n= a^{b \mod \varphi(n)} \bmod n$ (for $21$, it is $(3-1) \cdot (7-1)=12$) this requires finding the prime factors of $n$.
In general the rank for $n = \prod{(p_i)^{k_i-1} \cdot (p_i-1)}$ with $p_i^{k_i}$ the prime factors of $n$.
The Chinese remainder theorem can reduce the computation needed. For example, we can factor $21 = 3 \cdot 7$, and have
$$ 1 \cdot 7 – 2 \cdot 3 = 1$$
(in general, we can use the extended Euclidean algorithm to produce this formula)
Consequently, if
$$x \equiv a \pmod 3 \qquad x \equiv b \pmod 7 $$
then
$$ x \equiv a \cdot (1 \cdot 7 ) + b \cdot (-2 \cdot 3) \pmod{21} $$
Thus, we can compute $5^{844325} \bmod 21$ by using our favorite means to compute:
$$ 5^{844325} \equiv 2 \pmod 3 \qquad 5^{844325} \equiv 3 \pmod 7 $$
and thus
$$ 5^{844325} \equiv 2 \cdot 7 + 3 \cdot (-6) \equiv -4 \equiv 17 \pmod{21} $$
For the first question: use $a^{\Phi(c)}=1 \mod c$, where $\Phi(c)$ is the number of coprimes to $c$ below $c$. For $c=21=7\cdot 3$ we have $\Phi(c)=(7-1)\cdot(3-1)=12$
second question: Use $a^4=(a^2)^2, a^8=(a^4)^2$ and so on. Decompose the exponent into powers of 2 and combine them using $a^n\cdot a^m=a^{n+m}$ E.g. $a^{69}=a^{64}\cdot a^4\cdot a^1$