# Speeding up modular exponentiation using CRT

This is the fifth post in a series of posts on the Chinese remainder theorem (CRT). When solving a congruence equation with a composite modulus, it is often easier to convert the problem to one of solving several congruence equations with smaller moduli that are primes or powers of primes. Then combine the individual solutions using the Chinese remainder theorem. In this post, we demonstrate this process for modular exponentiation $x \equiv c^d \ (\text{mod} \ m)$ where the exponent $d$ and the modulus $m$ are large. Given $x \equiv c^d \ (\text{mod} \ m)$, the algorithm discussed here is to produce a system of equations with smaller moduli and exponents that give the same answer as for the original problem.

The previous posts in the series on CRT: first post; second post; third post; fourth post

____________________________________________________________________________

Preliminary discussion

The exponentiation $c^d$ is usually programmed using the fast powering algorithm. The CRT method will convert the exponentiation $c^d$ to several exponentiations that involve much smaller exponents and moduli, thus greatly reducing the calculation time, in particular speeding up the fast powering algorithm. One application of the CRT method is to improve the run time of the decryption process in the RSA algorithm (up to four times faster).

As already mentioned, the goal of the algorithm discussed here is to produce an equivalent system of linear congruence equations. Once this system is produced, the Chinese remainder theorem only guarantees a solution and does not actually produce a solution. So we need to know how to Chinese remainder, i.e. using an algorithm for solving a simultaneous linear congruences. We can use the one discussed here (the first method) or here (the second method). The following examples are worked using the second method.

The CRT algorithm discussed here makes use of Euler’s theorem, which states that $a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)$ whenever $a$ and the modulus $m$ are relatively prime where $\phi(m)$ is the phi function evaluated at $m$. For this reason, the algorithm requires the evaluation of the phi function.

When calculating $c^d \ (\text{mod} \ m)$, the use of the phi function $\phi(m)$ is to reduce the exponent $d$ by the largest multiple of $\phi(m)$. For example, since $\phi(17)=16$ and $2^{16} \equiv 1 \ (\text{mod} \ 17)$, the problem of $2^{250} \ (\text{mod} \ 17)$ is converted to finding $2^{10} \ (\text{mod} \ 17)$. Here, the original exponent of 250 is reduced to 10 after taking out the largest multiple of 16. Note that $10 \equiv 250 \ (\text{mod} \ \phi(17)=16)$. In general, we want to replace the original exponent $d$ by a smaller exponent $d_1$ where $d_1 \equiv d \ (\text{mod} \ \phi(m))$.

____________________________________________________________________________

Examples

In the following three examples, we use the algorithm discussed here to solve systems of linear congruence equations (this is the iterative approach). These examples are by no means realistic since the numbers used are small. So they are for demonstration of how CRT works.

Example 1
Calculate $x \equiv 2^{3163} \ (\text{mod} \ 3969)$.

First, factor the modulus $3969=3^4 \times 7^2=81 \times 49$. Now the problem is converted to solving the following system of two equations:

$x \equiv 2^{3163} \ (\text{mod} \ 81)$

$x \equiv 2^{3163} \ (\text{mod} \ 49)$

By CRT, any solution to the two equations is also a solution to the original equation. However, the exponent of 3163 should first be reduced. To this end, calculate the phi function, where $\phi(3^4)=3^2 \cdot (3-1)=54$ and $\phi(7^2)=7 \cdot (7-1)=42$. We should reduce from 3163 the largest multiple of 54 in the first equation and reduce the largest multiple of 42 in the second equation. In other words, reduce the exponent 3163 modulo the two phi function values:

$3163 \equiv 31 \ (\text{mod} \ 54)$

$3163 \equiv 13 \ (\text{mod} \ 42)$

As a result, we solve the following two equations:

$x \equiv 2^{3163} \equiv 2^{31} \equiv 65 \ (\text{mod} \ 81)$

$x \equiv 2^{3163} \equiv 2^{13} \equiv 9 \ (\text{mod} \ 49)$

Note that the original exponentiation $2^{3163}$ is turned into the easier ones of $2^{31}$ and $2^{13}$. The following gives the solution to the above two equations.

\displaystyle \begin{aligned} x_0&=65+81 \cdot 23 \cdot (9-65) \ (\text{mod} \ 3969) \\&\equiv -104263 \ (\text{mod} \ 3969) \\&\equiv 2900 \ (\text{mod} \ 3969) \end{aligned}

where 23 is obtained by solving for $y$ in $81y \equiv 1 \ (\text{mod} \ 49)$

By CRT, the answer to the original problem is $2^{3163} \equiv 2900 \ (\text{mod} \ 3969)$. $\square$

Example 2
Calculate $x \equiv 3^{3163} \ (\text{mod} \ 3969)$.

In this example, the number 3 and the modulus 3969 are not relatively prime. The CRT method still applies. As in Example 1, the problem can be reduced in the following way:

$x \equiv 3^{3163} \equiv 3^{31} \equiv 0 \ (\text{mod} \ 81)$

$x \equiv 2^{3163} \equiv 3^{13} \equiv 10 \ (\text{mod} \ 49)$

The first equation is congruent to 0 since $3^{31}$ contains 81 as a factor. The following gives the solution to the above two equations:

\displaystyle \begin{aligned} x_0&=0+81 \cdot 23 \cdot (10-0) \ (\text{mod} \ 3969) \\&\equiv 18630 \ (\text{mod} \ 3969) \\&\equiv 2754 \ (\text{mod} \ 3969) \end{aligned}

By CRT, the answer to the original problem is $3^{3163} \equiv 2754 \ (\text{mod} \ 3969)$. $\square$

Example 3
The above 2 examples use small numbers to illustrate the CRT technique. In this example, we use slightly larger numbers. Calculate $x \equiv 355^{d} \ (\text{mod} \ m)$ where $d=\text{1,759,695,794}$ and $m=\text{3,055,933,789}=1277 \cdot 1439 \cdot 1663$.

As in the other examples, we break up the problem in three congruences. The three factors of the modulus are prime numbers. Thus we reduce the exponent $d$ by multiples of a prime factor less one.

$\text{1,759,695,794} \equiv 1198 \ (\text{mod} \ 1276)$

$\text{1,759,695,794} \equiv 814 \ (\text{mod} \ 1438)$

$\text{1,759,695,794} \equiv 110 \ (\text{mod} \ 1662)$

Then the original problem is transformed to solving the following three equations.

$x \equiv 355^{d} \equiv 355^{1198} \equiv 189 \ (\text{mod} \ 1277)$

$x \equiv 355^{d} \equiv 355^{814} \equiv 1010 \ (\text{mod} \ 1439)$

$x \equiv 355^{d} \equiv 355^{110} \equiv 315 \ (\text{mod} \ 1663)$

Notice that the original exponentiation is transformed to the smaller ones of $355^{1198}$, $355^{814}$ and $355^{315}$. The remaining task is to solve the system of three equations. One way to find to solution to the above three equations is to use the iterative approach, starting with the solution $x_1=189$ to the first equation. Then find the solution $x_2$ to the first two equations and then the solution $x_3$ to all three equations.

\displaystyle \begin{aligned} x_2&=189+1277 \cdot 151 \cdot (1010-189) \ (\text{mod} \ 1277 \cdot 1439) \\&\equiv 158311156 \ (\text{mod} \ 1837603) \\&\equiv 277298 \ (\text{mod} \ 1837603) \end{aligned}

where 151 is obtained by solving for $y$ in $1277y \equiv 1 \ (\text{mod} \ 1439)$

\displaystyle \begin{aligned} x_3&=277298+(1277 \cdot 1439) \cdot 970 \cdot (315-277298) \ (\text{mod} \ 1277 \cdot 1439 \cdot 1663) \\&\equiv 277298+1782474910 \cdot (-276983) \ (\text{mod} \ m) \\&\equiv 277298+1414954310 \ (\text{mod} \ m) \\&\equiv 1415231608 \ (\text{mod} \ m) \end{aligned}

where 970 is obtained by solving for $y$ in $(1277 \cdot 1439) y \equiv 1 \ (\text{mod} \ 1663)$

By CRT, the answer to the original problem is $355^{d} \equiv 1415231608 \ (\text{mod} \ m)$. $\square$

____________________________________________________________________________

The CRT algorithm to speed exponentiation

Suppose we wish to evaluate $x \equiv c^{d} \ (\text{mod} \ m)$ where the prime factorization of $m$ is $m=p_1^{n_1} \cdot p_2^{n_2} \cdots p_t^{n_t}$. The numbers $p_i$ are distinct prime numbers and each exponent $n_i \ge 1$. To prepare for the calculation, do the following:

Let $m_i=p_i^{n_i}$ for each $i$.

Calculate $\phi(m_i)$ for each $i$.

Case 1. The base $c$ and the modulus $m$ are relatively prime.
Then the answer to the original exponentiation problem is identical to the solution to the following system of $t$ congruence equations:

$x \equiv c^{d_1} \ (\text{mod} \ m_1)$

$x \equiv c^{d_2} \ (\text{mod} \ m_2)$

$\cdots$

$x \equiv c^{d_t} \ (\text{mod} \ m_t)$

where $d_i \equiv d \ (\text{mod} \ \phi(m_i))$ for each $i$. If possible, each $c^{d_i}$ should be reduced modulo $m_i$.

Case 2. The base $c$ and the modulus $m$ are not relatively prime.
In this case, $c$ and $m$ have prime factors in common (at least one $p_i$). The idea here is that for any $p_i$ that is a prime factor of $c$, the equation $x \equiv c^{d_i} \ (\text{mod} \ m_i)$ in Case 1 is replaced by $x \equiv 0 \ (\text{mod} \ m_i)$. Then solve the resulting system of equations (see Example 2). Essentially, Case 2 can fall under Case 1 with $c^{d_i}$ being congruent to zero. We call out Case 2 for the sake of clarity.

The original exponentiation $c^d$ boils down to solving an appropriate system of CRT congruences as described above. Once the equivalent system of congruences is set up, use the algorithm discussed here or here to do Chinese remaindering.

Comment
Both Case 1 and Case 2 produce a system of linear congruence equations that have identical solution to the original equation. This is a result of using CRT (see Theorem D and Theorem G here). The savings in the calculation come in the form of the smaller exponentiations in the resulting congruence equations.

In Case 2, some of the congruence equations are $x \equiv 0$. This is because the base $c$ and some moduli $m_i$ are not relatively prime. For these moduli, $c^{d_i}$ would contain $p_i^{n_i}$ as a factor (assuming that $d_i \ge n_i$). Hence, $x \equiv c^{d_i} \equiv 0 \ (\text{mod} \ m_i)$.

The two-equation case
When the modulus is the product of two factors that are relatively prime, the CRT algorithm involves only two equations. We write out the solution explicitly for this case. To evaluate $x \equiv c^{d} \ (\text{mod} \ m)$ where $m=m_1 \cdot m_2$ and $m_1$ and $m_2$ are relatively prime, solve the following system of two equations,

$x \equiv c^{d_1} \ (\text{mod} \ m_1)$

$x \equiv c^{d_2} \ (\text{mod} \ m_2)$

The solution is $x \equiv c^{d_1}+m_1 \cdot v_1 \cdot (c^{d_2}-c^{d_1}) \ (\text{mod} \ m)$ where $v_1$ is the multiplicative inverse of $m_1$ modulo $m_2$. If possible, each $c^{d_i}$ should be reduced modulo $m_i$.

____________________________________________________________________________

RSA application

The algorithm to speed the exponentiation is possible because the factorization of the modulus $m$ is known (as a result, the values of $\phi(m_i)$ are known). Knowing the values of $\phi(m_i)$ makes it possible to reduce the large exponent $d$. For this reason, the decryption process in the RSA algorithm is a perfect place to apply the CRT technique described here.

With the RSA cryptosystem, a public key consists of $N$ and $e$, where $N$ is a large modulus that is a product of two large primes $p$ and $q$ (the two primes are not published) and $e$ is the encryption exponent. Say Bob is the originator of the RSA public key. Bob also generates a private key, which is a number $d$ that is used for decrypting any messages that he receives. The number $d$ must be kept private. The prime factors $p$ and $q$ must also be kept secret since knowing $p$ and $q$ can derive $d$.

Suppose that Alice has a message to send to Bob. She can do so using the published key of $N$ and $e$ through the exponentiation $c \equiv m^e \ (\text{mod} \ N)$. Here, $m$ is the plaintext (the message to be sent) and $c$ is the ciphertext (the encrypted message). Upon receiving the ciphertext $c$, Bob can then decrypt through the exponentiation $m \equiv c^d \ (\text{mod} \ N)$ where $d$ is the decryption exponent. In realistic RSA calculation, the public modulus $N$ and the private decryption exponent $d$ are large integers ($N$ is at minimum a 2048-bit number). With CRT, the decryption can be reduced to two much smaller exponentiations. The effect can be at least four times faster.

We illustrate this with an example. This is a toy example since the numbers used are small. It is only intended as an illustration.

Example 4
Suppose the public key consists of $N=\text{17,086,049}$ and $e=65537$. Bob has the additional information of $N=p \cdot q$ where $p=3863$ and $q=4423$, which are kept secret. Knowing $p$ and $q$ allows Bob to compute $d=\text{5,731,241}$. Suppose that Bob receives a message $c=$ 4831984 from Alice. Use the CRT approach to find the plaintext $m$.

The exponentiation is $m \equiv 4831984^{5731241} \ (\text{mod} \ N)$, which is equivalent to the following two equations by CRT:

$m \equiv 4831984^{5731241} \ (\text{mod} \ 3863)$

$m \equiv 4831984^{5731241} \ (\text{mod} \ 4423)$

which is further simplified to:

$m \equiv 4831984^{5731241} \equiv 4831984^{33} \equiv 3084 \ (\text{mod} \ 3863)$

$m \equiv 4831984^{5731241} \equiv 4831984^{329} \equiv 1436 \ (\text{mod} \ 4423)$

where $33 \equiv 5731241 \ (\text{mod} \ 3862)$ and $329 \equiv 5731241 \ (\text{mod} \ 4422)$. Then the following is the plaintext (the original message).

\displaystyle \begin{aligned} m&=3084+3863 \cdot 1319 \cdot (1436-3084) \ (\text{mod} \ 3863 \cdot 4423) \\&\equiv 3084+5095297 \cdot (-1648) \ (\text{mod} \ N) \\&\equiv 9289736 \ (\text{mod} \ N) \end{aligned}

where 1319 is obtained by solving for $y$ in $3683y \equiv 1 \ (\text{mod} \ 4423)$

The answer is $4831984^{5731241} \equiv 9289736 \ (\text{mod} \ N)$. $\square$

____________________________________________________________________________

Closing comment

In conclusion, we state the explcit formula for providing the CRT answer to the RSA decryption.

$m \equiv c^{d_p}+p \cdot p_{inv} \cdot (c^{d_q}-c^{d_p}) \ (\text{mod} \ p \cdot q) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

where $d_p \equiv d \ (\text{mod} \ p-1)$, $d_q \equiv d \ (\text{mod} \ q-1)$ and $p_{inv}$ is the multiplicative inverse of $p$ modulo $q$.

The decryption formula of (1) represends tremendous saving in calculation (up to four times faster). It is possible only for the holder of the RSA private key. It requires knowledge of the decryption exponent $d$, which is calculated from the factors $p$ and $q$ of the modulus $N$.
____________________________________________________________________________
$\copyright \ 2015 \text{ by Dan Ma}$