Solving quadratic congruences with odd prime moduli

The goal of this post is to show how to solve the quadratic congruence equation

    x^2 \equiv a \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

where p is an odd prime and a is an integer that is relatively prime to p. When equation (1) has a solution, the number a is said to be a quadratic residue modulo p. Any solution of equation (1) is called a square root of a modulo p. When the equation has no solutions, the number a is said to be a quadratic nonresidue modulo p. For both theoretical and practical reasons, it is important to solve quadratic congruence equation (1) (or to find square roots modulo an odd prime). This post expands on the previous post called Solving Quadratic Congruences.

____________________________________________________________________________

Background

If the modulus p is small (prime or composite), then it is easy to solve equation (1). Simply square each element in the set \left\{1,2,\cdots,p-1 \right\} modulo p and look for the value a. We need a systematic method only when the modulus is large to the point that checking for solutions by squaring one number at a time cannot be done in a reasonable amount of time using modern supercomputers.

The moduli discussed here are prime numbers p. The case p=2 is easy to deal with. Thus in solving equations described in (1), the focus is on odd primes p and on integers a that are relatively prime to p.

In solving the quadratic congruence equation (1), for that matter any other type of equations, three natural questions arise: given an equation of the form in (1), how do I know if it has a solution? If it has a solution, how many solution does it have? How do I compute a solution of one exists? It turns out that for quadratic congruence equations with odd prime moduli as described in (1), there are clear and definite answers for all three questions.

There is an effective algorithm for checking whether a is a quadratic residue modulo p. The algorithm is to evaluate the Legendre symbol \displaystyle  \biggl(\frac{a}{p}\biggr) (see these two previous posts: Legendre symbol and Jacobi symbol). As for the second question (the number of solutions), the equation (1) either has no solutions or has exactly two solutions (see the post called Solving Quadratic Congruences). Thus for an odd prime p, exactly half of the elements in the set \mathbb{Z}_p^*=\left\{1,2,\cdots,p-1 \right\} are quadratic residues modulo p. In other words, modulo an odd prime p, there are (p-1)/2 many quadratic residues and (p-1)/2 many quadratic nonresidues. To answer the third question, we discuss algorithms that can be used to solve quadratic congruences with odd prime moduli.

Any odd prime is congruent to either 1 or 3 modulo 4. For odd prime p \equiv 3 \ (\text{mod} \ 4), there is an explicit formula that gives the solutions to equation (1). For odd prime p \equiv 1 \ (\text{mod} \ 4), no explicit formula exists. For the case of p \equiv 1 \ (\text{mod} \ 4), we demonstrate how to use the Tonelli-Shanks algorithm to iteratively find the solutions. We describe the algorithm and show how it works with some examples. We also present a proof of why the algorithm works.

The Tonelli-Shanks algorithm was invented in 1972 by Dan Shanks. He called it RESSOL (RESidues SOLver). The algorithm is very similar to one described much earlier by Tonelli, hence the name Tonelli-Shanks algorithm.

____________________________________________________________________________

Odd primes congruent to 3 modulo 4

Let’s take care of the easy case first, i.e. p \equiv 3 \ (\text{mod} \ 4). In this case, the solutions to equation (1) are given by \pm R where

    \displaystyle R \equiv a^{\frac{p+1}{4}} \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

To see that the R gives a solution to the equation (1), consider the following derivation:

    \displaystyle \begin{aligned} R^2&\equiv (a^{\frac{p+1}{4}})^2 \\&\equiv a^{\frac{p+1}{2}} \\&\equiv a \cdot a^{\frac{p-1}{2}} \\&\equiv a \cdot \biggl(\frac{a}{p}\biggr) \\&\equiv a \cdot 1  \\&\equiv a \ (\text{mod} \ p) \end{aligned}

On the surface, it appears that the above derivation works for all primes. Note that the exponent (p+1)/4 must be an integer. The assumption p \equiv 3 \ (\text{mod} \ 4) makes it an integer. Using Euler’s Criterion, the quantity \displaystyle a^{\frac{p-1}{2}} is replaced by the Lengendre symbol, which is a 1 since a is a quadratic residue modulo p.

As a quick example, let’s solve the equation x^2 \equiv 19 \ (\text{mod} \ 431). The prime 431 is congruent to 3 modulo 4. The number 19 is a quadratic residue modulo 431. One solution is given by 19^{432/4} \equiv 19^{108} \equiv 197 \ (\text{mod} \ 431). The other solution is given by 234 (= 431-197).

____________________________________________________________________________

Odd primes congruent to 1 modulo 4

The focus of the remainder of the post is on using the Tonelli-Shanks algorithm to solve the quadratic equation (1). We describe the algorithm in the next section and demonstrate with examples. To follow along the algorithm and the examples, it would be helpful to have a calculator (or a software package) that can handle modular exponentiation and the evaluation of Legendre symbol and Jacobi symbol. The algorithm also requires the finding of a quadratic nonresidue modulo the odd prime p. Obviously, we need to check that the number a is a quadratic residue modulo p. This can be done by evaluating the Legendre symbol \displaystyle  \biggl(\frac{a}{p}\biggr).

____________________________________________________________________________

Tonelli-Shanks Algorithm

Objective: to solve the equation x^2 \equiv a \ (\text{mod} \ p) where p is an odd prime satisfying p \equiv 1 \ (\text{mod} \ 4) and a is a quadratic residue modulo p, i.e. the Legendre symbol \displaystyle  \biggl(\frac{a}{p}\biggr)=1.

Steps:

  1. Factor out the largest power of 2 from the even integer p-1, i.e. obtain p-1=2^{S} \cdot Q where Q is odd.
  2. Find a positive integer y that is a quadratic nonresidue modulo p, i.e. find y such that \displaystyle  \biggl(\frac{y}{p}\biggr)=-1.
  3. Calculate the following four quantities:
    • \displaystyle R \equiv a^{\frac{Q+1}{2}} \ (\text{mod} \ p)
    • \displaystyle c \equiv y^Q \ (\text{mod} \ p)
    • \displaystyle t \equiv a^{Q} \ (\text{mod} \ p)
    • \displaystyle E=S
  4. Loop
    1. If \displaystyle t \equiv 1 \ (\text{mod} \ p), then the algorithm stops and output R and p-R, the two solutions of the equation. If \displaystyle t \not \equiv 1 \ (\text{mod} \ p), then perform the following two steps.
    2. Find the least i such that 0<i<E and such that \displaystyle t^{2^i} \equiv 1 \ (\text{mod} \ p).
    3. Calculate \displaystyle b \equiv c^{2^{E-i-1}} \ (\text{mod} \ p) and replace the quantities R, c, t and E as follows:
      • \displaystyle R \equiv Rb \ (\text{mod} \ p)
      • \displaystyle c \equiv b^2 \ (\text{mod} \ p)
      • \displaystyle t \equiv b^2 \cdot t \ (\text{mod} \ p)
      • \displaystyle E=i

      Go back to Step A.

The initial value of \displaystyle R \equiv a^{\frac{Q+1}{2}} is an initial estimate of the solution to the equation. The rest of the algorithm is to repeatedly refine this estimate to reach a solution. Note that Step 4-B is to determine the order of the number t. Each time a new value of t is calculated, the order of the new t is smaller than the order of the previous t. The goal is to reach a t of order 1, which means that the number t itself would be \equiv 1, at which point the estimate R becomes a solution. Let’s consider some examples.

____________________________________________________________________________

Examples

Example 1
Solve the equation x^2 \equiv 381 \ (\text{mod} \ 593).

The following shows the steps in carrying out the Tonelli-Shanks algorithm.

Step 1. S=4 and Q=37 since 592 = 16 x 37.

Step 2. y=3 is a quadratic nonresidue modulo 593.

Step 3. Calculate the following four quantities:

  • \displaystyle R \equiv 381^{\frac{37+1}{2}} \equiv 381^{19} \equiv 218 \ (\text{mod} \ 593)
  • \displaystyle c \equiv 3^{37} \equiv 384 \ (\text{mod} \ 593)
  • \displaystyle t \equiv 381^{37} \equiv 201 \ (\text{mod} \ 593)
  • \displaystyle E=4

_______________________________________
The above t is obviously t \not \equiv 1. We now find the least i, 0<i<E, such that t^{2^i} \equiv 1. In other words, repeatedly square t until reaching the value of 1. The result is i=3. Let b \equiv c^{2^{E-i-1}} \equiv 384^{2^{4-3-1}} \equiv 384 \ (\text{mod} \ 593). Replace the quantities R, c, t and E as follows:

  • \displaystyle R \equiv 218 \cdot 384 \equiv 99 \ (\text{mod} \ 593)
  • \displaystyle c \equiv 384^{2} \equiv 392 \ (\text{mod} \ 593)
  • \displaystyle t \equiv 201 \cdot 392 \equiv 516 \ (\text{mod} \ 593)
  • \displaystyle E=3

_______________________________________
The last t is obviously t \not \equiv 1. We now find the least i, 0<i<E, such that t^{2^i} \equiv 1. The result is i=2. Note that the order of t goes from 2^3 previously to 2^2.

Let b \equiv c^{2^{E-i-1}} \equiv 392^{2^{3-2-1}} \equiv 392 \ (\text{mod} \ 593). Replace the quantities R, c, t and E as follows:

  • \displaystyle R \equiv 99 \cdot 392 \equiv 263 \ (\text{mod} \ 593)
  • \displaystyle c \equiv 392^{2} \equiv 77 \ (\text{mod} \ 593)
  • \displaystyle t \equiv 516 \cdot 77 \equiv 1 \ (\text{mod} \ 593)
  • \displaystyle E=2

Now we reach t \equiv 1. The solutions to the equations are: 263 and 330 (=593 – 263). \square

Example 2
Solve the equation x^2 \equiv a \ (\text{mod} \ p) where p= 2795830049 and a= 2262876953.

The number p is a prime and the value of the Legendre symbol is \displaystyle  \biggl(\frac{a}{p}\biggr)=1. The following shows the steps.

Step 1. S=5 and Q= 87369689.

Step 2. y=3 is a quadratic nonresidue modulo p. This is the result of a search starting with 2.

Step 3. Calculate the following four quantities. All calculations are modulo p.

  • \displaystyle R \equiv a^{\frac{Q+1}{2}} \equiv 2075434035
  • \displaystyle c \equiv 3^{Q} \equiv 268289123
  • \displaystyle t \equiv a^{Q} \equiv 2666735226
  • \displaystyle E=5

The above t is obviously not 1. So we need to perform the loop several times.

_______________________________________
Iteration 1

  • i=4, the least i such that t^{2^i} \equiv 1.
  • b \equiv c^{2^{E-i-1}} \equiv c^{2^{5-4-1}} \equiv c \equiv 268289123
  • \displaystyle R_1 \equiv R \cdot b \equiv 2438491248
  • \displaystyle c_1 \equiv b^2 \equiv 717416975
  • \displaystyle t_1 \equiv c_1 \cdot t \equiv 2569006270
  • \displaystyle E_1=4

_______________________________________
Iteration 2

  • i=2, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_1^{2^{E_1-i-1}} \equiv c_1^{2^{4-2-1}} \equiv c_1^2 \equiv 17652213
  • \displaystyle R_2 \equiv R_1 \cdot b \equiv 2519954933
  • \displaystyle c_2 \equiv b^2 \equiv 2569006270
  • \displaystyle t_2 \equiv c_2 \cdot t_1 \equiv 2795830048
  • \displaystyle E_2=2

_______________________________________
Iteration 3

  • i=1, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_2^{2^{E_2-i-1}} \equiv c_2^{2^{2-1-1}} \equiv c_2 \equiv 2569006270
  • \displaystyle R_3 \equiv R_2 \cdot b \equiv  1147516973
  • \displaystyle c_3 \equiv b^2 \equiv 2795830048
  • \displaystyle t_3 \equiv c_3 \cdot t_2 \equiv 1
  • \displaystyle E_3=1

_______________________________________
Solutions

  • \displaystyle R \equiv 1147516973
  • \displaystyle p-R \equiv 1648313076

____________________________________________________________________________

Why the algorithm works

To prove that the algorithm produces the solutions to the given equation, we need the following lemma.

Lemma
Suppose that both g and h are relatively prime to an odd prime number p. Suppose that the order of g modulo p is 2^j with j being a positive integer. Suppose that the order of h modulo p is also 2^j. Then the order of g \cdot h modulo p is 2^k where k<j.

Proof
Since the order of g is 2^j, \displaystyle y=g^{2^{j-1}} \not \equiv 1 \ (\text{mod} \ p). Note that \displaystyle y^2 \equiv g^{2^{j}} \equiv 1 \ (\text{mod} \ p). Then it must be that y \equiv -1 \ (\text{mod} \ p) since the equation x^2 \equiv 1 \ (\text{mod} \ p) has only two solutions. By a similar argument, h^{2^{j-1}} \equiv -1 \ (\text{mod} \ p). Consider the following:

    \displaystyle (gh)^{2^{j-1}} \equiv g^{2^{j-1}} \cdot h^{2^{j-1}} \equiv (-1) (-1) \equiv 1 \ (\text{mod} \ p)

This means that the order of g \cdot h divides 2^{j-1}. Thus the order of g \cdot h modulo p must be 2^{k} for some k \le j-1 < j. \square

Proof of Tonelli-Shanks algorithm
Since p is an odd prime, we set p-1=Q \cdot 2^{S} where Q is odd. We also select a positive integer y that is a quadratic nonresidue modulo p. To start the calculation, obtain the following four quantities:

  • \displaystyle R \equiv a^{\frac{Q+1}{2}} \ (\text{mod} \ p)
  • \displaystyle c \equiv y^Q \ (\text{mod} \ p)
  • \displaystyle t \equiv a^{Q} \ (\text{mod} \ p)
  • \displaystyle E=S

The quantity R is an initial estimate of the desired solution since

    \displaystyle R^2 \equiv a^{Q+1} \equiv a \cdot a^Q \equiv a \cdot t \ (\text{mod} \ p)

If t \equiv 1 \ (\text{mod} \ p), then R would be a solution and the algorithm stops. So assume that t \not \equiv 1 \ (\text{mod} \ p). Then we begin a loop to fine tune R until reaching a step with t \equiv 1 \ (\text{mod} \ p).

To make sense of the loop in the algorithm, consider the quantity c and the quantity t. First of all, the integer c has order 2^S modulo p, as shown below.

    \displaystyle c^{2^S} \equiv (y^{Q})^{2^S} \equiv y^{p-1} \equiv (y^{\frac{p-1}{2}})^2 \equiv (-1)^2 \equiv 1 \ (\text{mod} \ p)

    \displaystyle c^{2^{S-1}} \equiv (y^{Q})^{2^{S-1}} \equiv y^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)

Furthermore, the order of t modulo p is less or equal to 2^S since \displaystyle t^{2^S} \equiv 1 \ (\text{mod} \ p) as shown below.

    \displaystyle t^{2^S} \equiv (a^{Q})^{2^S} \equiv a^{p-1} \equiv (a^{\frac{p-1}{2}})^2 \equiv (1)^2 \equiv 1 \ (\text{mod} \ p)

Let 2^{S_1} be the order of t where S_1 \le S. Now begin the calculation for the first iteration of the loop. First, calculate \displaystyle b_1 \equiv c^{2^{E-S_1-1}} \ (\text{mod} \ p).

  • \displaystyle R_1 \equiv R \cdot b_1 \ (\text{mod} \ p)
  • \displaystyle c_1 \equiv b_1^2 \ (\text{mod} \ p)
  • \displaystyle t_1 \equiv c_1 \cdot t \ (\text{mod} \ p)
  • \displaystyle E_1=S_1

One important point to make is that the order of c_1 modulo p is the same as the order of t, which is 2^{S_1}. The following shows why.

    \displaystyle c_1^{2^{S_1}} \equiv (b_1^2)^{2^{S_1}} \equiv b_1^{2^{S_1+1}} \equiv (c^{2^{E-S_1-1}})^{2^{S_1+1}} \equiv c^{2^S} \equiv 1 \ (\text{mod} \ p)

    \displaystyle c_1^{2^{S_1-1}} \equiv (b_1^2)^{2^{S_1-1}} \equiv b_1^{2^{S_1}} \equiv (c^{2^{E-S_1-1}})^{2^{S_1}} \equiv c^{2^{S-1}} \equiv -1 \ (\text{mod} \ p)

By the lemma, the order of \displaystyle t_1 \equiv c_1 \cdot t \ (\text{mod} \ p) is 2^{S_2} for some S_2<S_1. Note that

    \displaystyle R_1^2 \equiv R^2 \cdot b_1^2 \equiv a \cdot t \cdot c_1 \equiv a \cdot t_1 \ (\text{mod} \ p)

In light of the above, if \displaystyle t_1 \equiv 1 \ (\text{mod} \ p), then R_1 is a solution and the algorithm stops. Even if \displaystyle t_1 \not \equiv 1 \ (\text{mod} \ p), there is progress since the order of t_1 is less than the previous t with 2^{S_2}<2^{S_1}. Repeat the loop to obtain t_2, \cdots, t_k with the order of t_k being 2^{S_{k+1}}=1 where S_{k+1}=0. When the order of t_k is 1, t_k=1. When the modulus is a prime, there is only one element with order 1, namely the element 1. Then the quantity R_j is a solution to the given equation.

To further illustrate, we perform one more iteration of the loop. Let \displaystyle b_2 \equiv c_1^{2^{E_1-S_2-1}} \ (\text{mod} \ p). Calculate the following four quantities:

  • \displaystyle R_2 \equiv R_1 \cdot b_2 \ (\text{mod} \ p)
  • \displaystyle c_2 \equiv b_2^2 \ (\text{mod} \ p)
  • \displaystyle t_2 \equiv c_2 \cdot t_1 \ (\text{mod} \ p)
  • \displaystyle E_2=S_2

Similar to the previous step, the order of c_2 is the same as the order of t_1 as shown below:

    \displaystyle C_2^{2^{S_2}} \equiv (b_2^2)^{2^{S_2}} \equiv b_2^{2^{S_2+1}} \equiv (c_1^{2^{E_1-S_2-1}})^{2^{S_2+1}} \equiv c_1^{2^{E_1}} \equiv c_1^{2^{S_1}} \equiv 1 \ (\text{mod} \ p)

    \displaystyle C_2^{2^{S_2-1}} \equiv (b_2^2)^{2^{S_2-1}} \equiv b_2^{2^{S_2}} \equiv (c_1^{2^{E_1-S_2-1}})^{2^{S_2}} \equiv c_1^{2^{E_1-1}} \equiv c_1^{2^{S_1-1}} \equiv -1 \ (\text{mod} \ p)

By the lemma, the order of \displaystyle t_2 \equiv c_2 \cdot t_1 \ (\text{mod} \ p) is 2^{S_3} for some S_3<S_2. Note the following:

    \displaystyle R_2^2 \equiv R_1^2 \cdot b_2^2 \equiv a \cdot t_1 \cdot c_2 \equiv a \cdot t_2 \ (\text{mod} \ p)

Now we reach the same decision point. If t_2 \equiv 1, then R_2 is a solution and the algorithm stops. Even if t_2 \not \equiv 1, the order of t_2 is smaller than previously. Continue to execute the loop until the step where the order of t_k is 1. \square

____________________________________________________________________________

Comments

The Tonelli-Shanks algorithm works correctly (as the proof indicated) and works efficiently (as the examples show). The speed of the algorithm is a function of the inputs. The inputs to the Tonelli-Shanks algorithm are the odd prime p and the quadratic residue a modulo p. The two inputs are translated to the three quantities m, k and S where m is the number of digits in the binary representation of the odd prime p, k is the number of ones in the binary representation of p and S is the largest power of 2 in the factor of p-1. These three numbers determine the amount of calculations. According to this source, the average number of modular multiplications required by the Tonelli-Shanks algorithm is:

    \displaystyle 2m+2k+\frac{S(S-1)}{4}+\frac{1}{2^{S-1}}-9

Another consideration is the selection of y, a quadratic nonresidue modulo p, which can be found by checking random selections from the set \mathbb{Z}_p^*=\left\{1,2,\cdots,p-1 \right\}. Since half the elements in the set are quadratic residues, it takes on average two random selections from this set (hence two computations of the Legendre symbol). One way to see this is that the number of Bernoulli trials until the first success has a geometric distribution. The probability of success in each trial is 0.5. Then the mean of the geometric distribution is 1/0.5 = 2.

Overall, the Tonelli-Shanks algorithm works efficiently in solving the quadratic congruence equation (1). Along with the explicit formula (2) that handles the case of odd prime congruent to 3 modulo 4, the quadratic congruence equations are completely and efficiently solved. As a result, it is not possible to hide secrets using quadratic congruence equations with odd prime moduli. If a message is embedded as a solution of such equation, then it can be easily recovered using the Tonelli-Shanks algorithm or the explicit formula (2). On the other hand, the equation

    x^2 \equiv a \ (\text{mod} \ n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

is difficult to solve where the modulus n is the product of two large primes p and q. In fact the Rabin cryptosystem is based on the difficulty of solving equation (3). However, if the factoring of n is known, equation (3) is solvable and the Tonelli-Shanks algorithm along with the Chinese remainder theorem play a crucial role.

____________________________________________________________________________

Another example

Example 3
This is a slightly larger example than the ones given earlier. Solve the equation x^2 \equiv a \ (\text{mod} \ p) where p= 3825123056546413057 and a= 1347234680313589343.

The number p is a prime and the value of the Legendre symbol is \displaystyle  \biggl(\frac{a}{p}\biggr)=1. The following shows the steps.

Step 1. S=9 and Q= 7470943469817213.

Step 2. y=5 is a quadratic nonresidue modulo p. This is the result of a search starting with 2.

Step 3. Calculate the following four quantities. All calculations are modulo p.

  • \displaystyle R \equiv a^{\frac{Q+1}{2}} \equiv 2098778229504385555
  • \displaystyle c \equiv 5^{Q} \equiv 945046778698092498
  • \displaystyle t \equiv a^{Q} \equiv 3356211917617579979
  • \displaystyle E=9

The above t is obviously not 1. So we need to perform the loops several times.

_______________________________________
Iteration 1

  • i=8, the least i such that t^{2^i} \equiv 1.
  • b \equiv c^{2^{E-i-1}} \equiv c^{2^{9-8-1}} \equiv c \equiv 945046778698092498
  • \displaystyle R_1 \equiv R \cdot b \equiv 852974818860733646
  • \displaystyle c_1 \equiv b^2 \equiv 777225398785777536
  • \displaystyle t_1 \equiv c_1 \cdot t \equiv 3130593564544117824
  • \displaystyle E_1=8

_______________________________________
Iteration 2

  • i=7, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_1^{2^{E_1-i-1}} \equiv c_1^{2^{8-7-1}} \equiv c_1 \equiv 777225398785777536
  • \displaystyle R_2 \equiv R_1 \cdot b \equiv 1437578878907258220
  • \displaystyle c_2 \equiv b^2 \equiv 872612747799733789
  • \displaystyle t_2 \equiv c_2 \cdot t_1 \equiv 3053369905528253481
  • \displaystyle E_2=7

_______________________________________
Iteration 3

  • i=2, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_2^{2^{E_2-i-1}} \equiv c_2^{2^{7-2-1}} \equiv c_2^{2^5} \equiv 2409792470045159888
  • \displaystyle R_3 \equiv R_2 \cdot b \equiv 1136125891705727966
  • \displaystyle c_3 \equiv b^2 \equiv 3053369905528253481
  • \displaystyle t_3 \equiv c_3 \cdot t_2 \equiv 3825123056546413056
  • \displaystyle E_3=2

_______________________________________
Iteration 4

  • i=1, the least i such that t^{2^i} \equiv 1.
  • b \equiv c_3^{2^{E_3-i-1}} \equiv c_3^{2^{2-1-1}} \equiv c_3^{2^0} \equiv c_3 \equiv 3053369905528253481
  • \displaystyle R_4 \equiv R_3 \cdot b \equiv  3727993796269536942
  • \displaystyle c_4 \equiv b^2 \equiv 3825123056546413056
  • \displaystyle t_4 \equiv c_4 \cdot t_3 \equiv 1
  • \displaystyle E_4=1

_______________________________________
Solutions

  • \displaystyle R \equiv 3727993796269536942
  • \displaystyle p-R \equiv 97129260276876115

____________________________________________________________________________

Exercises

We close with some exercises. Use Tonelli-Shanks algorithm to solve the equation x^2 \equiv a \ (\text{mod} \ p) for each of the following choices of a and p.

  1. p=193 and a = 67
  2. p=569 and a = 367
  3. p=34369 and a = 19170
  4. p=50753 and a = 12957
  5. p=97241 and a = 47861
  6. p=2773676993 and a = 1342865413

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

\text{ }

Solutions are:

  1. 35 and 158
  2. 103 and 466
  3. 19136 and 15233
  4. 30781 and 19972
  5. 45733 and 51508
  6. 1056882643 and 1716794350

____________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}

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}

Using Fermat’s Little Theorem to Test Primality

Fermat’s little theorem describes a property that is common to all prime numbers. This property can be used as a way to detect the “prime or composite” status of an integer. Primality testing using Fermat’s little theorem is called the Fermat primality test. In this post, we explain how to use this test and to discuss some issues surrounding the Fermat test.

___________________________________________________________________

Describing the test

The Fermat primality test, as mentioned above, is based on Fermat’s little theorem. The following is the statement of the theorem.

    Fermat’s little theorem
    If n is a prime number and if a is an integer that is relatively prime to n, then the following congruence relationship holds:

      a^{n-1} \equiv 1 (\text{mod} \ n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

The above theorem indicates that all prime numbers possess a certain property. Therefore if a given positive integer does not possess this property, we know for certain that this integer is not prime. Suppose that the primality of an integer n is not known. If we can find an integer a that is relatively prime to n such that a^{n-1} \not \equiv 1 \ (\text{mod} \ n), then we have conclusive proof that n is composite. Such a number a is said to be a Fermat witness for (the compositeness of) n.

The Fermat test is closedly linked to the notations of probable primes and pseudoprimes. If the congruence relation (1) is true for n and a, then n is said to be a probable prime to base a. Furthermore, if n happens to be a composite number, then n is said to be a pseudoprime to base a. Pseudoprime prime is a composite number that possesses the prime-like property as indicated by (1) for one base a.

The Fermat primality test from a compositeness perspective is about looking for Fermat witnesses. If a Fermat witness is found, the number being tested is proved to be composite. On the other hand, the Fermat primality test, from a primality perspective, consists of checking the congruence relation (1) for several bases that are randomly selected. If the number n is found to be a probable prime to all the randomly chosen bases, then n is likely a prime number.

If the number n is in reality a prime number, then the Fermat test will always give the correct result (as a result of Fermat’s little theorem). If the number n is in reality a composite number, the Fermat test can make the mistake of identifying the composite number n as prime (i.e. identifying a pseudoprime as a prime). For most composite numbers this error probability can be made arbitrarily small (by testing a large number of bases a). But there are rare composite numbers that evade the Fermat test. Such composite numbers are called Carmichael numbers. No matter how many bases you test on a Carmichael number, the Fermat test will always output Probably Prime. Carmichael numbers may be rare but there are infinitely many of them over the entire number line. More about Carmichael numbers below.

The following describes the steps of the Fermat primality test.

    Fermat primality test
    The test is to determine whether a large positive integer n is prime or composite. The test will output one of two results: n is Composite or n is Probably Prime.

  • Step 1. Choose a random integer a \in \left\{2,3,\cdots,n-1 \right\}.
  • Step 2. Compute \text{GCD}(a,n). If it is greater than 1, then stop and output n is Composite. Otherwise go to the next step.
  • Step 3. Compute a^{n-1} \ (\text{mod} \ n).
    • If a^{n-1} \not \equiv 1 \ (\text{mod} \ n), then stop and output n is Composite.
    • If a^{n-1} \equiv 1 \ (\text{mod} \ n), then n may be a prime number. Do one of the following:
      • Return to Step 1 and repeat the process with a new a.
      • Output n is Probably Prime and stop.

    \text{ }

The exponentiation in Step 3 can be done by the fast powering algorithm. This involves a series of squarings and multiplications. Even for numbers that have hundreds of digits, the fast powering algorithm is efficient.

One comment about Step 2 in the algorithm. Step 2 could be called the GCD test for primality. If you can find an integer a such that 1<a<n and such that \text{GCD}(a,n) \ne 1, then the integer n is certainly composite. Such a number a is called a GCD witness for the compositeness of n. So the Fermat test as described above combines the GCD test and the Fermat test. We can use the Euclidean algorithm to find the GCD. If we happen to stumble upon a GCD witness, then we can try another n for a candidate of a prime number. For most composite numbers, it is not likely to stumble upon a GCD witness. Thus when using the Fermat test, it is likely that Step 3 in the algorithm is used.

An example of Fermat primality testing is the post called A primality testing exercise from RSA-100.

____________________________________________________________________________

More about the test

When using the Fermat test, what is the probability of the test giving the correct result? Or what is the probability of making an error? Because the Fermat test is not a true probabilistic primality test, the answers to these questions are conditional. In one scenario which covers most of the cases, the test works like an efficient probabilistic test. In another scenario which occurs very rarely, the Fermat test fails miserably.

As with most diagnostic tests, the Fermat test can make two types of mistakes – false positives or false negatives. For primality testing discussed in this post, we define a positive result as the outcome that says the number being tested is a prime number and a negative result as the outcome that says the number being tested is a composite number. Thus a false positive is identifying a composite number as a prime number and a false negative is identifying a prime number as a composite number.

For the Fermat test, there is no false negative. If n is a prime number in reality, the statement of Fermat’s little theorem does not allow the possibility that n be declared a composite number. Thus if the Fermat test gives a negative result, it would be a true negative. In other words, finding a Fermat witness for n is an irrefutable proof that n is composite.

However, there can be false positives for the Fermat test. This is where things can get a little tricky. A composite number n is said to be a Carmichael number if the above congruence relationship (1) holds for all bases a relatively prime to n. In other words, n is a Carmichael number if a^{n-1} \equiv 1 (\text{mod} \ n) for all a that are relatively prime to n. Saying it in another way, n is a Carmichael number if there exists no Fermat witness for n.

The smallest Carmichael number is 561. Carmichael numbers are rare but there are infinitely many of them. The existence of such numbers poses a challenge for the Fermat test. If you apply the Fermat test on a Carmichael number, the outcome will always be Probably Prime. So the Fermat test will always give a false positive when it is applied on a Carmichael number. To put it in another way, with respect to Carmichael numbers, the error probability of the Fermat test is virtually 100%!

So should a primality tester do? To keep things in perspective, Carmichael numbers are rare (see this post). If the primality testing is done on randomly chosen numbers, choosing a Carmichael number is not likely. So the Fermat test will often give the correct results. For those who are bothered by the nagging fear of working with Carmichael numbers, they can always switch to a Carmichael neutral test such as the Miller-Rabin test.

___________________________________________________________________

One bright spot about the Fermat test

There is one bright spot about the Fermat test. When applying the Fermat test on numbers that are not Carmichael numbers, the error probability can be made arbitrarily small. In this sense the Fermat test works like a true probabilistic primality test. Consider the following theorem.

    Theorem 1
    Let n be a composite integer such that it is not a pseudoprime to at least one base (i.e. n has a Fermat witness). In other words, n is not a Carmichael number. Then n is not a pseudoprime to at least half of the bases a (1<a<n) that are relatively prime to n. In other words, n is a pseudoprime to at most half of the bases a (1<a<n) that are relatively prime to n.

Theorem 1 means that the Fermat test can be very accurate on composite numbers that are not Carmichael numbers. As long as there is one base to which the composite number is not a pseudoprime (i.e. as long as there is a Fermat witness for the composite number in question), there will be enough of such bases (at least 50% of the possible bases). As a result, it is likely that the Fermat test will find a witness, especially if the tester is willing to use enough bases to test and if the bases are randomly chosen. When a base is randomly chosen, there is at least a 50% chance that the number n is not a pseudoprime to that base (i.e. the Fermat test will detect the compositeness) or putting it in another way, there is at most a 50% chance that the Fermat test will not detect the compositeness of the composite number n. So if k values of a are randomly selected, there is at most 0.5^k probability that the Fermat test will not detect the compositeness of the composite number n (i.e. making a mistake). So the probability of a false positive is at most 0.5^k. For a large enough k, this probability is practically zero.

Proof of Theorem 1
A base to which n is a pseudoprime or not a pseudoprime should be a number in the interval 1<a<n that is relatively prime to n. If n is a pseudoprime to base a, then a raised to some power is congruent to 1 modulo n. For this to happen, a must be relatively prime to the modulus n. For this reason, when we consider a base, it must be a number that is relatively prime to the composite integer n (see the post on Euler’s phi function).

Let a be a base to which n is not a pseudoprime. We make the following claim.

    Claim
    If b is a number such that 1<b<n and such that n is a pseudoprime to base b, then n is not a pseudoprime to base a \cdot b.

Since both integers a and b are assumed to be relatively prime to n, the product a \cdot b is also relatively prime to n (see Lemma 4 in this post). Now consider the congruence (ab)^{n-1} \ (\text{mod} \ n), which is derived as follows:

    (ab)^{n-1} \equiv a^{n-1} \cdot b^{n-1} \equiv a^{n-1} \not \equiv 1 \ (\text{mod} \ n)

In the above derivation, we use the fact that n is not a pseudoprime to base a and n is a pseudoprime to base b. The above derivation shows that n is not a pseudoprime to base ab.

If n is not a pseudoprime to all bases in 1<w<n, then we are done. So assume that n is a pseudoprime to at least one base. Let b_1,b_2,\cdots,b_k enumerate all bases to which n is a pseudoprime. We assume that the b_j are all distinct. So b_i \not \equiv b_j \ (\text{mod} \ n) for all i \ne j. By the above claim, the composite number n is not a pseudoprime to all the following k numbers:

    a \cdot b_1, \ a \cdot b_2, \cdots, \ a \cdot b_k

It is also clear that a \cdot b_i \not \equiv a \cdot b_j \ (\text{mod} \ n) for i \ne j. What we have just shown is that there are at least as many bases to which n is not a pseudoprime as there are bases to which n is a pseudoprime. This means that n is not a pseudoprime to at least 50% of the bases that are relatively prime to n. In other words, as long as there exists one Fermat witness for n, at least 50% of the bases are Fermat witnesses for n. It then follows that n is a pseudoprime to no more than 50% of the bases relatively prime to n. \blacksquare

There is another way to state Theorem 1. Recall that Euler’s phi function \phi(n) is defined to be the number of integers a in the interval 1<a<n that are relatively prime to n. With this in mind, Theorem 1 can be restated as the following:

    Corollary 2
    Let n be a composite integer such that it is not a pseudoprime to at least one base. Then n is not a pseudoprime to at least \displaystyle \frac{\phi(n)}{2} many bases in the interval 1<a<n.

___________________________________________________________________

Concluding remarks

Of course, Theorem 1 works only for the composite numbers that are not pseudoprime to at least one base (i.e. they are not Carmichael numbers). When you test the compositeness of a number, you do not know in advance if it is Carmichael or not. On the other hand, if the testing is done on randomly chosen numbers, it is not likely to randomly stumble upon Carmichael numbers. The Fermat test works well for the most part and often give the correct results. If one is concerned about the rare chance of a false positive in the form of a Carmichael number, then the Miller-Rabin test will be a good alternative.

Note:
The original post was written in August 10, 2013. On March 29, 2015, this post is replaced with a blog post called The Fermat primality test from the companion math crypto blog.

___________________________________________________________________
\copyright \ \ 2013 - 2015 \ \text{Dan Ma}

Congruence Arithmetic and Fast Powering Algorithm

In some cryptography applications such as RSA algorithm, it is necessary to compute \displaystyle a^w modulo m where the power w and the modulus m are very large numbers. We discuss and demonstrate an efficient algorithm that can handle such calculations. This general algorithm has various names such as fast powering algorithm, square-and-multiply algorithm and exponentiation by squaring.

The problem at hand is to compute a^w \ (\text{mod} \ m). The naïve approach is to compute by repeatedly multiplying by a and reducing modulo m. When the power w is large (e.g. an integer with hundreds of digits), this approach is difficult or even impossible (given the current technology). In this post we discuss an alternative that is known as the fast powering algorithm.

___________________________________________________________________________________________________________________

An Example

Compute 1286^{1171} modulo 1363.

Using the naïve approach described earlier, we would do something like the following:

    \displaystyle \begin{aligned} 1286^{1171} &=(1286 \cdot 1286) \cdot 1286^{1269} \equiv 477 \cdot 1286^{1269} \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&=(477 \cdot 1286) \cdot 1286^{1268} \equiv 72 \cdot 1286^{1268} \  \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&=(72 \cdot 1286) \cdot 1286^{1267} \equiv 1271 \cdot 1286^{1267} \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\text{     }\cdots \\&\text{     }\cdots \\&\text{     }\cdots \end{aligned}

In this naïve approach, we would multiply two numbers at a time and then reduce the result modulo 1363 so that the numbers do not get too large. The above example would involve 1170 multiplications and then 1170 divisions for the reduction modulo 1363. Great difficulty comes when the power is not 1171 and instead is an integer with hundreds or even thousands of digits.

Note that in the above naïve approach, the power is reduced by one at each step. In the fast power alternative, the power comes down by an exponent of two in each step. The idea is to use the binary expansions of the exponent 1171 to transform the computation of 1286^{1171} into a series of squarings and multiplications. To this end, we write 1171 as a sum of powers of two as follows:

    (1) \ \ \ \ \ \ \ \ \ 1171=2^0+2^1+2^4+2^7+2^{10}

Next we compute 1286^{2^0},1286^{2^1},1286^{2^2},1286^{2^3},\cdots,1286^{2^{10}} modulo 1363. Note that each term is the square of the preceding term, hence the word square in the name “square-and-multiply”. To make it easier to see, we put the results in the following table.

    \displaystyle (2) \ \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ i }&\text{ }&1286^{2^i}&\text{ }&\text{squaring}&\text{ }&\text{modulo } 1363&\text{ }&\text{ }  \\\text{ }&\text{ }&\text{ } \\ 0&\text{ }&1286^{2^0}&\text{ }&\text{ }&\text{ }&\equiv 1286&\text{ }&*  \\ 1&\text{ }&1286^{2^1}&\text{ }&\equiv 1286^2&\text{ }&\equiv 477&\text{ }&*  \\ 2&\text{ }&1286^{2^2}&\text{ }&\equiv 477^2&\text{ }&\equiv 1271&\text{ }&\text{ }  \\ 3&\text{ }&1286^{2^3}&\text{ }&\equiv 1271^2&\text{ }&\equiv 286&\text{ }&\text{ }  \\ 4&\text{ }&1286^{2^4}&\text{ }&\equiv 286^2&\text{ }&\equiv 16&\text{ }&*  \\ 5&\text{ }&1286^{2^5}&\text{ }&\equiv 16^2&\text{ }&\equiv 256&\text{ }&\text{ } \\ 6&\text{ }&1286^{2^6}&\text{ }&\equiv 256^2&\text{ }&\equiv 112&\text{ }&\text{ } \\ 7&\text{ }&1286^{2^7}&\text{ }&\equiv 112^2&\text{ }&\equiv 277&\text{ }&* \\ 8&\text{ }&1286^{2^8}&\text{ }&\equiv 277^2&\text{ }&\equiv 401&\text{ }&\text{ } \\ 9&\text{ }&1286^{2^9}&\text{ }&\equiv 401^2&\text{ }&\equiv 1330&\text{ }&\text{ } \\ 10&\text{ }&1286^{2^{10}}&\text{ }&\equiv 1330^2&\text{ }&\equiv 1089&\text{ }&*  \end{bmatrix}

Note that the rows marked by * in the above table are the results that we need. In the above table, there are 10 multiplications for the squarings and 10 divisions for the reduction modulo 1363.

Now 1286^{1171} is calculated as follows:

    \displaystyle \begin{aligned} (3) \ \ \ \ \ \ \ \ \ 1286^{1171} &=1286^{2^0} \cdot 1286^{2^1} \cdot 1286^{2^4} \cdot1286^{2^7} \cdot 1286^{2^{10}} \\&\equiv 1286 \ \ \cdot 477 \ \ \ \ \cdot 16 \ \ \ \ \ \cdot 277 \ \ \ \ \cdot 1089 \ \ \text{mod} \ 1363 \\&\equiv 72 \ \ \ \ \cdot 16 \ \ \ \ \ \cdot 277 \ \ \ \ \cdot 1089 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\equiv 1152 \ \ \cdot 277 \ \ \cdot 1089 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\equiv 162 \ \ \cdot 1089 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\equiv 591 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \end{aligned}

We have the answer 1286^{1171} \equiv 591 \ (\text{mod} \ 1363). The calculation in (3) is the step that gives the word “multiply” in the name “square-and-multiply”. In this step, we multiply the results obtained from the previous step.

We now tally up the amount of work that is done. The calculation in table (2) requires 10 multiplications for the squaring and 10 divisions for the reduction modulo 1363. The calculation in (3) requires 4 multiplications and 4 divisions for the reduction modulo 1363. Together, there are 14 multiplications and 14 divisions. In contrast, the naïve approach would require 1170 multiplications and 1170 divisions!

___________________________________________________________________________________________________________________

Description of Fast Powering Algorithm

To compute a^w \equiv (\text{mod} \ m), use the following steps. The following steps correspond with the steps in the above example.

Step (1)

Compute the binary expansions of the power w.

    \displaystyle w=C_0 +C_1 \cdot 2^{1}+C_2 \cdot 2^{2}+\cdots+C_{k-1} \cdot 2^{k-1}+C_k \cdot 2^{k}

where each j, C_j=0 or C_j=1. In particular, we assume that C_k=1.

Step (2)

For each j=0,1,2,\cdots,k, compute \displaystyle a^{2^j} \equiv A_j modulo m. Note that each \displaystyle a^{2^j} \equiv A_j is the result of squaring the previous term \displaystyle a^{2^{j-1}} \equiv A_{j-1}. We arrange the calculation in the following table.

    \displaystyle (2) \ \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ i }&\text{ }&a^{2^i}&\text{ }&\text{squaring}&\text{ }&\text{modulo } m&\text{ }&\text{ }  \\\text{ }&\text{ }&\text{ } \\ 0&\text{ }&a^{2^0}&\text{ }&\text{ }&\text{ }&A_0\equiv a&\text{ }&\text{ }  \\ 1&\text{ }&a^{2^1}&\text{ }&\equiv A_0^2&\text{ }&\equiv A_1&\text{ }&\text{ }  \\ 2&\text{ }&a^{2^2}&\text{ }&\equiv A_1^2&\text{ }&\equiv A_2&\text{ }&\text{ }  \\ 3&\text{ }&a^{2^3}&\text{ }&\equiv A_2^2&\text{ }&\equiv A_3&\text{ }&\text{ }  \\ \text{ }&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ }  \\ \text{ }&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ } \\ \text{ }&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ } \\ k-1&\text{ }&a^{2^{k-1}}&\text{ }&\equiv A_{k-2}^2&\text{ }&\equiv A_{k-1}&\text{ }&\text{ } \\ k&\text{ }&a^{2^k}&\text{ }&\equiv A_{k-1}^2&\text{ }&\equiv A_k&\text{ }&\text{ }   \end{bmatrix}

Step (3)

Compute a^w \equiv (\text{mod} \ m) using the following derivation.

    \displaystyle \begin{aligned}(3) \ \ \ \ \ \ \ \ \  a^{w}&=a^{C_0 +C_1 \cdot 2^{1}+C_2 \cdot 2^{2}+\cdots+C_{k-1} \cdot 2^{k-1}+C_k \cdot 2^{k}} \\&=a^{C_0} \cdot a^{C_1 \cdot 2^{1}} \cdot a^{C_2 \cdot 2^{2}} \cdots a^{C_{k-1} \cdot 2^{k-1}} \cdot a^{C_k \cdot 2^{k}} \\&=a^{C_0} \cdot (a^{2^{1}})^{C_1} \cdot (a^{2^{2}})^{C_2} \cdots (a^{2^{k-1}})^{C_{k-1}} \cdot (a^{2^{k}})^{C_k} \\&\equiv A_0^{C_0} \cdot (A_1)^{C_1} \cdot (A_2)^{C_2} \cdots (A_{k-1})^{C_{k-1}} \cdot (A_k)^{C_k} \ \ \ \ \ (\text{mod} \ m) \end{aligned}

The last line in (3) is to be further reduced modulo m. In the actual calculation, only the terms with C_j=1 need to be used.

We now establish an upper bound for the number multiplications. Step (2) requires k multiplications and k divisions to reduce modulo m. Step (3) requires at most k many multiplications since some of the C_j many be zero. Step (3) also requires at most k many divisions to reduce modulo m. So altogether, the algorithm requires at most 2k multiplications and 2k divisions.

From Step (1), we know that \displaystyle 2^k \le w. Take natural log of both sides, we have \displaystyle k \le \frac{\text{ln}(w)}{\text{ln}(2)} and \displaystyle 2 \cdot k \le \frac{2 \cdot \text{ln}(w)}{\text{ln}(2)}. So the fast powering algorithm requires at most

    \displaystyle \frac{2 \cdot \text{ln}(w)}{\text{ln}(2)}

many multiplications and at most that many divisions to compute the congruence calculation a^w \equiv (\text{mod} \ m).

For example, when the power w=2^{127}-1, which is a Mersenne prime, which has 39 digits. Now w \approx 2^{127}. By the above calculation, the fast powering algorithm would take at most 254 multiplications and at most 254 divisions to do the power congruence computation.

The fast powering calculations demonstrated in this post can be done by hand (using a hand-held calculator). In real applications, such calculations should of course be done in a computer.

___________________________________________________________________________________________________________________

Another Example

Use the fast power algorithm to show that

    4030^{2657} \equiv 21144 \ (\text{mod} \ 55049)

    21144^{79081} \equiv 4030 \ (\text{mod} \ 55049)

Note that one congruence is encryption and the other one is decryption. We demonstrate the second calculation.

In doing the second calculation, we use a little bit of help from Fermat’s little theorem. The modulus 55049 is a prime number. So 21144^{55048} \equiv 1 \ (\text{mod} \ 55049). Thus we have:

    21144^{79081}=21144^{24033} \cdot 21144^{55048} \equiv 21144^{24033} \ (\text{mod} \ 55049)

Step (1)

The binary expansions of 24033 are:

    24033=2^0+2^5+2^6+2^7+2^8+2^{10}+2^{11}+2^{12}+2^{14}

Step (2)

Compute 21144^{2^j} modulo 55049 for each j. The computation is displayed in the following table. The rows with * are the results that we need for Step (3).

    \displaystyle \begin{bmatrix} \text{ i }&\text{ }&21144^{2^i}&\text{ }&\text{squaring}&\text{ }&\text{modulo } 55049&\text{ }&\text{ }  \\\text{ }&\text{ }&\text{ } \\ 0&\text{ }&21144^{2^0}&\text{ }&\text{ }&\text{ }&\equiv 21144&\text{ }&*  \\ 1&\text{ }&21144^{2^1}&\text{ }&\equiv 21144^2&\text{ }&\equiv 15807&\text{ }&\text{ }  \\ 2&\text{ }&21144^{2^2}&\text{ }&\equiv 15807^2&\text{ }&\equiv 48887&\text{ }&\text{ }  \\ 3&\text{ }&21144^{2^3}&\text{ }&\equiv 48887^2&\text{ }&\equiv 41483&\text{ }&\text{ }  \\ 4&\text{ }&21144^{2^4}&\text{ }&\equiv 41483^2&\text{ }&\equiv 7549&\text{ }&\text{ }  \\ 5&\text{ }&21144^{2^5}&\text{ }&\equiv 7549^2&\text{ }&\equiv 11686&\text{ }&* \\ 6&\text{ }&21144^{2^6}&\text{ }&\equiv 11686^2&\text{ }&\equiv 41076&\text{ }&* \\ 7&\text{ }&21144^{2^7}&\text{ }&\equiv 41076^2&\text{ }&\equiv 40975&\text{ }&* \\ 8&\text{ }&21144^{2^8}&\text{ }&\equiv 40975^2&\text{ }&\equiv 11174&\text{ }&* \\ 9&\text{ }&21144^{2^9}&\text{ }&\equiv 11174^2&\text{ }&\equiv 7144&\text{ }&\text{ } \\ 10&\text{ }&21144^{2^{10}}&\text{ }&\equiv 7144^2&\text{ }&\equiv 6313&\text{ }&* \\ 11&\text{ }&21144^{2^{11}}&\text{ }&\equiv 6313^2&\text{ }&\equiv 53542&\text{ }&* \\ 12&\text{ }&21144^{2^{12}}&\text{ }&\equiv 53542^2&\text{ }&\equiv 14040&\text{ }&* \\ 13&\text{ }&21144^{2^{13}}&\text{ }&\equiv 14040^2&\text{ }&\equiv 46180&\text{ }&\text{ } \\ 14&\text{ }&21144^{2^{14}}&\text{ }&\equiv 46180^2&\text{ }&\equiv 49189&\text{ }&* \end{bmatrix}

Step (3)

Compute 21144^{79081} \ (\text{mod} \ 55049).

    \displaystyle \begin{aligned} 21144^{24033} &=21144^{2^0} \cdot 21144^{2^5} \cdot 21144^{2^6} \cdot 21144^{2^7} \cdot 21144^{2^{8}} \cdot 21144^{2^{10}} \cdot 21144^{2^{11}} \cdot 21144^{2^{12}} \cdot 21144^{2^{14}} \\&\equiv 21144 \cdot 11686 \cdot 41076 \cdot 40975 \cdot 11174 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \text{mod} \ 55049 \\&\equiv 25665 \cdot 40975 \cdot 11174 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 22328 \cdot 11174 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 11004 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 51463 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 9300 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 50821 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 4030 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049   \end{aligned}

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

How to toss a coin

In this post, we demonstrate how to simulate a random coin toss using a cryptographic algorithm that was proposed by Rivest, Shamir and Adlemen in 1982 (the creators of the RSA algorithm). Tossing a coin using a cryptographic algorithm is an example of a game of mental poker.

The term mental poker refers to the game of poker played over long distance that has a mechanism for ensuring a fair game without the need for a trusted third party. Mental poker can also refer to other cryptographic games played over long distance without the need for a trusted third party (e.g. tossing a coin over long distance).

___________________________________________________________________________________________________________________

Setting the Algorithm

A full discussion of the algorithm used here can be found in the previous post Fermat’s Little Theorem and Mental Poker.

Andy and Becky are in different locations and they would like to simulate a random coin toss. First they need to agree on two positive integers that are to represent head and tail, say m_h for head and m_t for tail. These two numbers should be less than the prime number p discussed in the next paragraph.

They now need to encrypt the numbers before tossing the coin. Both players agree on a large prime number p. If the goal of preventing or minimizing cheating is important, the players should choose a prime number that is as large as feasible computationally speaking.

With the prime number p decided, each of the players chooses an encryption-decryption key, which is a pair of positive integers x_0 and x_1 such that

    x_0 \cdot x_1 \equiv 1 \ (\text{mod} \ p-1),

meaning that x_0 \cdot x_1=1+(p-1) \cdot k for some integer k.

Each of the players chooses such a pair of numbers. In terms of notation, Andy chooses a_0 and a_1. Becky chooses b_0 and b_1. Each player chooses the number pair independently and keeps it secret from the other player.

The number with the 0-subscript is the encryption key and the number with the 1-subscript is the decryption key. The following are the encryption functions, expressed in congruence modulo p, for Andy and Becky, respectively.

    f_a(m) \equiv m^{a_0} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Andy}

    f_b(m) \equiv m^{b_0} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Becky}

For example, if Andy wants to encrypt the number m, he raises m to the power of a_0 and looks for the remainder upon division by p. The remainder will be denoted by f_a(m). The function f_b(m) works similarly for Becky.

The following are the decryption functions, expressed in congruence modulo p, for Andy and Becky, respectively.

    g_a(c) \equiv c^{a_1} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Andy}

    g_b(c) \equiv c^{b_1} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Becky}

For example, if Andy wants to decrypt the number c=f_a(m), he raises c to the power of a_1 and looks for the remainder upon division by p. The remainder will be denoted by g_a(m), which will be the original number m. The proof of this fact is based on the Fermat’s Little Theorem (see the previous post Fermat’s Little Theorem and Mental Poker).

The function g_b(m) works similarly for Becky.

___________________________________________________________________________________________________________________

A Numerical Example

For illustration, we use a small prime number. We use p=7919. We emphasize that this is just for illustration. In an application where the chance for cheating is to be minimized, a large prime number should be used.

Andy and Becky use the following assignment for Head and Tail.

    \displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Head}&\text{ }&\text{Tail}  \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Original}&\text{ }&\text{2,500}&\text{ }&\text{5,000}    \end{bmatrix}

For this illustration, Andy chooses a_0=\text{47} and a_1=\text{52,899} by letting k=\text{314} in the equation below. Becky chooses b_0=\text{71} and b_1=\text{26,319} by letting k=\text{236} in the following equation.

    x_0 \cdot x_1=1+7918 \cdot k

Andy and Becky choose these keys independently and they keep them secret without letting the other person know. Andy encrypts both the head and tail numbers as follows:

    2500^{47} \equiv 7518=f_a(2500) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

    5000^{47} \equiv 698=f_a(5000) \ (\text{mod} \ 7919)  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

The encrypted numbers and the original numbers are displayed in the following table.

    \displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Head}&\text{ }&\text{Tail}  \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Original}&\text{ }&\text{2,500}&\text{ }&\text{5,000} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Andy}&\text{ }&\text{7,518}&\text{ }&\text{698}   \end{bmatrix}

Of course, the above table is kept secret from Becky. However, the encrypted numbers (just the encrypted numbers) are sent to Becky for random selection.

Becky selects one of the encrypted numbers for herself (perhaps thru a coin toss). Then the other encrypted number is the choice for Andy. Suppose Becky selects 7518. Becky then encrypted the number 7518 using her key.

    7518^{71} \equiv 1341=f_b(7518) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

Becky passes the encrypted number 1341 (her selection) and 698 (Andy’s selection) back to Andy. The following table lists out the numbers received by Andy.

    \displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Andy}&\text{ }&\text{Becky}  \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Becky's selection}&\text{ }&\text{698}&\text{ }&\text{7,518} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{1,341}   \end{bmatrix}

Andy decrypts his number 698 and gets back 2500, which is tail. He also decrypts 1341 and obtains 223, which he passes back to Becky.

    698^{52899} \equiv 5000=g_a(698) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)

    1341^{52899} \equiv 223=g_a(1341) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (5)

The following summarizes the results up to this point.

    \displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Andy}&\text{ }&\text{Becky}  \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Becky's selection}&\text{ }&\text{698}&\text{ }&\text{7,518} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{1,341}  \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Decrypted by Andy}&\text{ }&\text{5,000}&\text{ }&\text{223} \end{bmatrix}

Once Becky gets the decrypted number 223 from Andy, she decrypts it using her own key to obtain 2500, which is a head.

    223^{26319} \equiv 2500=g_b(223) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6)

The following table summarizes the results of the coin toss.

    \displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Andy}&\text{ }&\text{Becky}  \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Becky's selection}&\text{ }&\text{698}&\text{ }&\text{7,518} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{1,341}  \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Decrypted by Andy}&\text{ }&\text{5,000}&\text{ }&\text{223} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Decrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{2,500} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Results of Coin Toss}&\text{ }&\text{5,000}&\text{ }&\text{2,500} \end{bmatrix}

___________________________________________________________________________________________________________________

Numerical Calculation

We now show some of the calculations involved in the above encryption and decryption. We show three calculations.

    5000^{47} \equiv 698=f_a(5000) \ (\text{mod} \ 7919)  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

    698^{52899} \equiv 5000=g_a(698) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)

    223^{26319} \equiv 2500=g_b(223) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6)

Even with the small prime number p=7919, the calculation is not done directly. For example, unless special software is used, f_a(5000) is not found by calculating 5000^{47} and then finding the remainder upon division by 7919. The following demonstrates a “divide and conquer” approach for the calculation for (2) where in each step the exponent is reduced by half.

    \displaystyle \begin{aligned} 5000^{47}&\equiv (5000^2)^{23} \cdot 5000 \ (\text{mod} \ 7919) \\&\text{ } \\&=7636^{23} \cdot 5000 \equiv (7636^2)^{11} \cdot 7636 \cdot 5000 \\&\text{ } \\&\equiv 899^{11} \cdot 7636 \cdot 5000 \\&\text{ } \\&\equiv 899^{11} \cdot 2501 \equiv (899^2)^5 \cdot 899 \cdot 2501 \\&\text{ } \\&\equiv 463^5 \cdot 899 \cdot 2501 \\&\text{ } \\&\equiv 463^5 \cdot 7322 \equiv (463^2)^2 \cdot 463 \cdot 7322 \\&\text{ } \\&\equiv 556^2 \cdot 463 \cdot 7322 \\&\text{ } \\&\equiv 556^2 \cdot 754 \\&\text{ } \\&\equiv 295 \cdot 754  \\&\text{ } \\&\equiv 698 \ (\text{mod} \ 7919) \end{aligned}

In each step in the above calculation, we use the division algorithm to obtain the remainder. For example, to go from the first line to the second line, divide 5000^2 by 7919 to obtain the remainder of 7636. The number 698 in the last step is the remainder when 295 \cdot 754 is divided by 7919. These calculations are tedious if done by hand and should be done by computer.

The calculation for (4) is that 698^{52899} \equiv 5000 \ (\text{mod} \ 7919). In other word, decrypting the encrypted number of 698 recovers the original number of 5000. This calculation can be shortened by using Fermat’s Little Theorem, which implies that 698^{7919-1} \equiv 1 \ (\text{mod} \ 7919). Thus we have:

    698^{47508} \equiv 698^{6 \cdot 7918} \equiv 1 \ (\text{mod} \ 7919)

So we can reduce 47508 from the exponent 52899, leaving the exponent 5391. We have:

    698^{52899} \equiv 698^{47508} \cdot 698^{5391} \equiv 1 \cdot 698^{5391} \ (\text{mod} \ 7919)

The following uses the “divide and conquer” approach to compute 698^{5391} modulo 7919.

    \displaystyle \begin{aligned} 698^{5391}&\equiv (698^2)^{2695} \cdot 698 \ (\text{mod} \ 7919) \\&\text{ } \\&=4145^{2695} \cdot 698 \equiv (4145^2)^{1347} \cdot 4145 \cdot 698 \\&\text{ } \\&\equiv 4714^{1347} \cdot 4145 \cdot 698 \\&\text{ } \\&\equiv 4714^{1347} \cdot 2775 \equiv (4714^2)^{673} \cdot 4714 \cdot 2775 \\&\text{ } \\&\equiv 1082^{673} \cdot 4714 \cdot 2775 \\&\text{ } \\&\equiv 1082^{673} \cdot 7081 \equiv (1082^2)^{336} \cdot 1082 \cdot 7081 \\&\text{ } \\&\equiv 6631^{336} \cdot 1082 \cdot 7081 \\&\text{ } \\&\equiv 6631^{336} \cdot 3969 \equiv (6631^2)^{168} \cdot 3969 \\&\text{ } \\&\equiv 3873^{168} \cdot 3969 \equiv (3873^2)^{84} \cdot 3969 \\&\text{ } \\&\equiv 1543^{84} \cdot 3969 \equiv (1543^2)^{42} \cdot 3969 \\&\text{ } \\&\equiv 5149^{42} \cdot 3969 \equiv (5149^2)^{21} \cdot 3969\\&\text{ } \\&\equiv 7308^{21} \cdot 3969 \equiv (7308^2)^{10} \cdot 7308 \cdot 3969 \\&\text{ } \\&\equiv 1128^{10} \cdot 7308 \cdot 3969 \\&\text{ } \\&\equiv 1128^{10} \cdot 6074 \equiv (1128^2)^{5} \cdot 6074\\&\text{ } \\&\equiv 5344^5 \cdot 6074 \equiv (5344^2)^2 \cdot 5344 \cdot 6074 \\&\text{ } \\&\equiv 2422^2 \cdot 5344 \cdot 6074 \\&\text{ } \\&\equiv2422^2 \cdot 7394 \\&\text{ } \\&\equiv 6024 \cdot 7394    \\&\text{ } \\&\equiv 5000 \ (\text{mod} \ 7919) \end{aligned}

The calculation for (6) is 223^{26319} \equiv 2500 \ (\text{mod} \ 7919). We can also get an assist from the Fermat’s Little Theorem. In this particular case, 223^{7918} \equiv 1 \ (\text{mod} \ 7919). With 26319=3 \cdot 7918+2565, we only need to calculate 223^{2565} \ (\text{mod} \ 7919), which is done below.

    \displaystyle \begin{aligned} 223^{2565}&\equiv (223^2)^{1282} \cdot 223 \ (\text{mod} \ 7919) \\&\text{ } \\&=2215^{1282} \cdot 223 \equiv (2215^2)^{641} \cdot 223 \\&\text{ } \\&\equiv 4364^{641} \cdot 223 \equiv (4364^2)^{320} \cdot 4364 \cdot 223 \\&\text{ } \\&\equiv 7220^{320} \cdot 4364 \cdot 223 \\&\text{ } \\&\equiv 7220^{320} \cdot 7054 \equiv (7220^2)^{160} \cdot 7054 \\&\text{ } \\&\equiv 5542^{160} \cdot 7054 \equiv (5442^2)^{80} \cdot 7054 \\&\text{ } \\&\equiv 3882^{80} \cdot 7054 \equiv (3882^2)^{40} \cdot 7054 \\&\text{ } \\&\equiv 67^{40} \cdot 7054 \equiv (67^2)^{20} \cdot 7054 \\&\text{ } \\&\equiv 4489^{20} \cdot 7054 \equiv (4489^2)^{10} \cdot 7054\\&\text{ } \\&\equiv 5185^{10} \cdot 7054 \equiv (5185^2)^{5} \cdot 7054  \\&\text{ } \\&\equiv 7139^{5} \cdot 7054 \equiv (7139^2)^{2} \cdot 7139 \cdot 7054 \\&\text{ } \\&\equiv 6556^2 \cdot 7139 \cdot 7054 \\&\text{ } \\&\equiv 6556^2 \cdot 1585  \\&\text{ } \\&\equiv 4723 \cdot 1585    \\&\text{ } \\&\equiv 2500 \ (\text{mod} \ 7919) \end{aligned}

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Fermat’s Little Theorem and Mental Poker

In this post we demonstrate another use of the Fermat’s Little Theorem.

How can two people play poker when they are not sitting face to face from each other? If the game of poker is played over long distance (e.g. via a telephone line or some electronic communication channel), there will be a need to ensure a fair game. For example, the two players must use the same deck of cards (ensuring that there will be no duplicates). The deck of cards will need to be well shuffled. Each player cannot see the cards of the other player. One solution is to use a trusted third party to do the shuffling and selecting of cards. If a third party cannot be found or it is felt that the third party cannot be trusted to be fair, then one should consider the cryptographic solution described in this post. This soultion was proposed by Rivest, Shamir and Adlemen in 1982 (the creators of the RSA algorithm).

The term mental poker refers to the game of poker played over long distance that has a mechanism for ensuring a fair game without the need for a trusted third party. Mental poker can also refer to other cryptographic games played over long distance without the need for a trusted third party (e.g. tossing a coin over long distance).

___________________________________________________________________________________________________________________

Setting Up the Deck of Cards

Let’s say that the players are Andy and Becky. Since they are not using a physical deck of cards, they need to represent the cards by numbers. Let’s say that they agree to number the cards as follows:

    \displaystyle \heartsuit 2=1020 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit 2=2020  \ \ \ \ \ \ \ \ \ \ \ \spadesuit 2=3020 \ \ \ \ \ \ \ \ \ \ \ \clubsuit 2=4020

    \displaystyle \heartsuit 3=1030 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit 3=2030  \ \ \ \ \ \ \ \ \ \ \ \spadesuit 3=3030 \ \ \ \ \ \ \ \ \ \ \ \clubsuit 3=4030

    \displaystyle \heartsuit 4=1040 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit 4=2040  \ \ \ \ \ \ \ \ \ \ \ \spadesuit 4=3040 \ \ \ \ \ \ \ \ \ \ \ \clubsuit 4=4040

      \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots

      \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots

      \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots

    \displaystyle \heartsuit Q=1120 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit Q=2120  \ \ \ \ \ \ \ \ \ \ \spadesuit Q=3120 \ \ \ \ \ \ \ \ \clubsuit Q=4120

    \displaystyle \heartsuit K=1130 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit K=2130  \ \ \ \ \ \ \ \ \ \spadesuit K=3130 \ \ \ \ \ \ \ \ \clubsuit K=4130

    \displaystyle \heartsuit A=1140 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit A=2140  \ \ \ \ \ \ \ \ \ \ \spadesuit A=3140 \ \ \ \ \ \ \ \ \ \clubsuit A=4140

___________________________________________________________________________________________________________________

Setting Up the Pad Locks

The card numbers need to be encrypted before they can be passed between the two players. Here’s how it works.

Both players agree to choose a large prime number p. This number p needs to be larger than all the card numbers and the encrypted card numbers. The larger p is, the harder it will be for any one of the players to cheat.

Now each of the players needs to choose an encryption-decryption key (a padlock) that the player keeps secret. Let’s start with Andy. He chooses a pair of positive numbers a_0 and a_1 such that the following holds:

    a_0 \cdot a_1 \equiv 1 \ (\text{mod} \ p-1)

Equivalently the pair a_0 and a_1 satisfies the equation a_0 \cdot a_1=1+(p-1) \cdot k for some integer k. The number a_0 will be used for locking (encryption) and the number a_1 will be used for unlocking (decryption). Andy will also keep this pair of numbers away from Becky.

How will Andy use this padlock? Suppose that m is a number to be encrypted. To encrypt the number, Andy raises m to the power of a_0 and then finds the remainder upon division by p. He will call the remainder f_a(m). Using congruence notation, the following is the encryption function:

    f_a(m) \equiv m^{a_0} \ (\text{mod} \ p)

If Andy needs to recover m from the encrypted card number c=f_a(m), all he has to do is to raise c to the power of a_1 and then find the remainder upon division by p. Call the remainder g_a(c), which will be the original card number m. Using congruence notation, the following is the decryption function:

    g_a(c) \equiv c^{a_1} \ (\text{mod} \ p)

The decrypted number is the original number. Thus we have g_a(c)=m. A proof of this relies on the Fermat’s Little Theorem (see proof).

Because the numbers involved are usually large, no one will try to raise m to the power of a_0 and then divides by p to find the remainder. Instead, Andy should use special software. If software is not available, Andy can rely on congruence modulo arithmetic, which should also be done by a computer. See below for a demonstration of the congruence modulo arithmetic.

The other player Becky also needs a padlock. Specifically, she chooses a pair of numbers b_0 and b_1 that satisfy the following:

    b_0 \cdot b_1 \equiv 1 \ (\text{mod} \ p-1)

This pair of number serves the same purpose as the pair that belongs to Andy. Of course, b_0 and b_1 need to be kept secret from Andy. The following shows the encryption and decryption functions for Becky’s padlock.

    f_b(m) \equiv m^{b_0} \ (\text{mod} \ p)

    g_b(c) \equiv c^{b_1} \ (\text{mod} \ p)

___________________________________________________________________________________________________________________

How to Play the Game

Suppose the card numbers are m_1, m_2, m_3, \cdots, m_{52} (the above is one example of card number assigment). Andy then encrypts the card number using his encryption function f_a(m). The following lists the encrypted card numbers.

    \displaystyle f_a(m_1),\ f_a(m_2), \ f_a(m_3),\cdots,f_a(m_{52})

Andy then passes these encrypted card numbers to Becky. She shuffles the encrypted deck thorughly. She then chooses a 5-card hand for Andy. Becky then chooses another 5-card hand for herself. Becky uses her key to encrypt her 5-card hand. Becky passes both 5-card hands to Andy. The following shows what Becky passes to Andy.

    Andy’s 5-card hand: f_a(m_i) \equiv m_i^{a_0} \ (\text{mod} \ p) for 5 distinct values of i.

    Becky’s 5-card hand: f_b(f_a(m_j)) \equiv f_a(m_j)^{b_0} \ (\text{mod} \ p) for 5 distinct values of j.

Once Andy gets the two 5-card hands, he decrypts his own 5-card hand and gets back the original card numbers. He also decrypts Becky’s 5-card hand and passes that back to Becky.

    Andy’s 5-card hand: g_a(f_a(m_i)) \equiv (m_i^{a_0})^{a_1} \equiv m_i \ (\text{mod} \ p)

    Becky’s 5-card hand: g_a(f_b(f_a(m_j))) \equiv (f_a(m_j)^{b_0})^{a_1}=(f_a(m_j)^{a_1})^{b_0} \equiv m_j^{b_0} \ (\text{mod} \ p), which Andy passes back to Becky.

Once Becky’s recieves her 5-card hand back from Andy, she decrypts the cards immediately and gets back the original card numbers.

    Becky’s 5-card hand: g_b(m_j^{b_0}) \equiv (m_j^{b_0})^{b_1} \equiv m_j \ (\text{mod} \ p)

Now each of the players has a 5-card hand that is only known to himself or herself. If they need to select new cards from the deck, they can follow the same back-and-forth procedures of encrypting and decrypting.

How fair is the poker game played in this manner? How secure is the game? It is very fair and secure if the players follow the rules and do not cheat. It is obviously possible to cheat. When Andy passes the 52 encrypted card numbers to Becky, Becky certainly can try to break Andy’s lock by figuring out Andy’s a_0. When Becky passes her encrypted cards to Andy, he can try to figure out Becky’s b_0. For that to happen, the player who wants to cheat will need to have enormous amount of computational resources at the ready. Thus the prime number p should be large enough to make cheating an intractable problem. On the other hand, even when the prime number is of a moderate size, there has to be a fair amount of computational resources in order to play the game efficiently, with all the encrypting and decrypting that have to be done.


___________________________________________________________________________________________________________________

Fermat’s Little Theorem

We now use Fermat’s Little Theorem to show that the encryption-decryption key works correctly and accurately. We show the following:

    (m^{a_0})^{a_1} \equiv m \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

For the descriptions of the numbers m, p, a_0 and a_1, see the above section Setting Up the Padlocks. First we state the Fermat’s Little Theorem.

Fermat’s Little Theorem
Let q be a prime number. Then for any integer a, a^q-a is an integer multiple of q (or q divides a^q-a). Using congruence notation, the theorem can be expressed as:

    a^q \equiv a \ (\text{mod} \ q)

If the integer a is not divisible by q, then we can divide out a and the theorem can be expressed as:

    a^{q-1} \equiv 1 \ (\text{mod} \ q)

For a proof and a fuller discussion of Fermat’s little theorem, see this post.

We now prove the property (1). Recall that the pair of positive integers a_0 and a_1 are keys to lock and unlock a number m. They are chosen such that a_0 \cdot a_1 \equiv 1 \ (\text{mod} \ p-1), or equivalently a_0 \cdot a_1=1+(p-1) \cdot k for some integer k. This integer k must be positive since a_0 and a_1 are both positive.

In the derivation below, we repeated use the fact that m^p \equiv m \ (\text{mod} \ p) (applying the Fermat’s Little Theorem).

    \displaystyle \begin{aligned} m&\equiv m^p \ (\text{mod} \ p)=m \cdot m^{p-1} \\&\equiv m^p \cdot m^{p-1} \ (\text{mod} \ p)=m \cdot m^{2(p-1)} \\&\equiv m^p \cdot m^{2(p-1)} \ (\text{mod} \ p)=m \cdot m^{3(p-1)} \\&\cdots \\&\cdots \\&\cdots \\&\equiv m^p \cdot m^{(k-1)(p-1)} \ (\text{mod} \ p)=m \cdot m^{k(p-1)} \\&=m \cdot m^{k(p-1)} \equiv m^{a_0 \cdot a_1} \ (\text{mod} \ p) \end{aligned}


___________________________________________________________________________________________________________________

Example of Congruence Calculation

For a numerical example, we use a small prime number p=55,049. Though a small prime number, it is large enough to make the illustration meaningful. Andy chooses a_0 \cdot a_1 such that a_0 \cdot a_1=1+(p-1) \cdot k for some integer k. Andy decides to use k=3817, leading to a_0=2,657 and a_1=79,081.

As illustration of how the calculation is done, let m=1020 (the number for \heartsuit 2 as indicated above).

To decrypt this card, Andy needs to raise 1020 to the 2657th power and then find the remainder upon division by p=50,049. This is the definition for 1010200^{269} modulo p. But the calculation is not easy to do directly without special software. We present here a “divide and conquer” approach that use the division algorithm in each step to reduce the exponent by half.

To start, note that 1020^2 \equiv 49518 \ (\text{mod} \ 55049), meaning that the remainder is 49518 when 1020^2 is divided by 55049. In the following series of steps, a congruence calculation is performed in each step (using the division algorithm) to reduce the exponent by half.

    \displaystyle \begin{aligned} 1020^{2657}&\equiv (1020^2)^{1328} \cdot 1020 \ (\text{mod} \ 55049) \\&\text{ } \\&\equiv 49518^{1328} \cdot 1020 \equiv (49518^2)^{664} \cdot 1020  \\&\text{ } \\& \equiv 39766^{664} \cdot 1020 \equiv (39766^2)^{332} \cdot 1020 \\&\text{ } \\& \equiv 52231^{332} \cdot 1020 \equiv (52231^2)^{166} \cdot 1020 \\&\text{ } \\&\equiv 14068^{166} \cdot 1020 \equiv (14068^2)^{83} \cdot 1020 \\&\text{ } \\& \equiv 7469^{83} \cdot 1020 \equiv (7469^2)^{41} \cdot 7469 \cdot 1020 \\&\text{ } \\& \equiv 21324^{41} \cdot 7469 \cdot 1020 \\&\text{ } \\&\equiv 21324^{41} \cdot 21618 \equiv (21324^2)^{20} \cdot 21324 \cdot 21618 \\&\text{ } \\&  \equiv 8236^{20} \cdot 21324 \cdot 21618 \\&\text{ } \\& \equiv 8236^{20} \cdot 1906 \equiv (8236^2)^{10} \cdot 1906 \\&\text{ } \\& \equiv 11328^{10} \cdot 1906 \equiv (11328^2)^{5} \cdot 1906 \\&\text{ } \\& \equiv 4365^5 \cdot 1906 \equiv (4365^2)^2 \cdot 4365 \cdot 1906 \\&\text{ } \\& \equiv 6271^2 \cdot 4365 \cdot 1906 \\&\text{ } \\&\equiv 6271^2 \cdot 7291  \\&\text{ } \\&\equiv 20455 \cdot 7291 \\&\text{ } \\&\equiv 9664 \ (\text{mod} \ 55049)  \end{aligned}

Thus the card number 1020 is encrypted as 9664. To recover the original card number from this encrypted number, Andy needs to raise 9664 to the power of a_1=79081. Here, we get an assist from Fermat’s Little Theorem in addition to the ‘divide and conquer” congruence arithmetic that is used above.

According to Fermat’s Little Theorem, 9664^{55048} \equiv 1 \ (\text{mod} \ 55049). Thus we have

    9664^{79081} \equiv 9664^{55048} \cdot 9664^{24033} \equiv 9664^{24033} \ (\text{mod} \ 55049)

With the help of Fermat’s Little Theorem, the exponent 79081 has come down to 24033. In the rest of the way, the “divide and conquer” approach is used.

    \displaystyle \begin{aligned} 9664^{24033}&\equiv (9664^2)^{12016} \cdot 9664 \ (\text{mod} \ 55049) \\&\text{ } \\&\equiv 29782^{12016} \cdot 9664 \equiv (29782^2)^{6008} \cdot 9664 \\&\text{ } \\&\equiv 8237^{6008} \cdot 9664 \equiv (8237^2)^{3004} \cdot 9664 \\&\text{ } \\&\equiv 27801^{3004} \cdot 9664 \equiv (27801^2)^{1502} \cdot 9664 \\&\text{ } \\&\equiv 7641^{1502} \cdot 9664 \equiv (7641^2)^{751} \cdot 9664 \\&\text{ } \\&\equiv  32941^{751} \cdot 9664 \equiv (32941^2)^{375} \cdot 32941 \cdot 9664 \\&\text{ } \\&\equiv 38642^{375} \cdot 32941 \cdot 9664 \\&\text{ } \\&\equiv 38642^{375} \cdot 48506 \equiv (38642^2)^{187} \cdot 38642 \cdot 48506 \\&\text{ } \\&\equiv 39^{187} \cdot 38642 \cdot 48506 \\&\text{ } \\&\equiv 39^{187} \cdot 5451 \equiv (39^2)^{93} \cdot 39 \cdot 5451 \\&\text{ } \\&\equiv 1521^{93} \cdot 39 \cdot 5451 \\&\text{ } \\&\equiv 1521^{93} \cdot 47442 \equiv (1521^2)^{46} \cdot 1521 \cdot 47442 \\&\text{ } \\&\equiv 1383^{46} \cdot 1521 \cdot 47442 \\&\text{ } \\&\equiv  1383^{46} \cdot 45092 \equiv (1383^2)^{23} \cdot 45092 \\&\text{ } \\&\equiv 41023^{23} \cdot 45092 \equiv (41023^2)^{11} \cdot 41023 \cdot 45092 \\&\text{ } \\&\equiv 38599^{11} \cdot 41023 \cdot 45092  \\&\text{ } \\&\equiv 38599^{11} \cdot 52618 \equiv (38599^2)^{5} \cdot 38599 \cdot 52618 \\&\text{ } \\&\equiv 36665^5 \cdot 38599 \cdot 52618  \\&\text{ } \\&\equiv 36665^5 \cdot 24376 \equiv (36665^2)^{2} \cdot 36665 \cdot 24376  \\&\text{ } \\&\equiv 25645^2 \cdot 36665 \cdot 24376  \\&\text{ } \\&\equiv 25645^2 \cdot 25525  \\&\text{ } \\&\equiv 50671 \cdot 25525  \\&\text{ } \\&\equiv 1020 \ (\text{mod} \ 55049)  \end{aligned}

In each step of the above calculation, the division algorithm is applied to reduce the exponent by half. For example, to go from the first line to the second line, 9664^2 is divided by 55049 to obtain the remainder 29782, i.e. 9664^2 \equiv 29782 \ (\text{mod} \ 55049). The number 1020 in the last line is the remainder when 50671 \cdot 25525 is divided by 55049.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Fermat’s Little Theorem and RSA Algorithm

RSA is a cryptographic algorithm that is used to send and receive messages. We use the Fermat’s Little Theorem to prove that RSA works correctly and accurately. In other words, the decrypted message is indeed the original message from the sender. Mathematically we show that applying the encryption function and the decryption function successively produces the identity function.

To see how RSA works, see the previous post An Illustration of the RSA Algorithm.

___________________________________________________________________________________________________________________

RSA Algorithm

We first briefly describe the algorithm and then present the mathematical statement to validate.

Let N=p \cdot q where p and q are two prime numbers. Let \phi=(p-1) \cdot (q-1). Choose an integer e with 1<e<N such that e and \phi are relatively prime.

The public key consists of N and e where e is the encryption key. Once it is published, anyone can use it to encrypt messages to send to the creator of the public key. The following is the encryption function:

    f(M) \equiv M^e \ (\text{mod} \ N)

where M is a positive integer and is the original message.

The private key is a positive integer d that satisfies:

    d \cdot e \equiv 1 \ (\text{mod} \ \phi=(p-1) \cdot (q-1))

In other words, d is the multiplicative inverse of e in the modular arithmetic of modulo \phi. The above condition is equivalent to: de-1=(p-1) \cdot (q-1) \cdot k for some integer k.

The number d is the decryption key that will be used to decode messages. So it should remain private.

Once the creator of the public key receives an encrypted message C=f(M), he or she uses the following decryption function to obtain the original message M.

    g(C) \equiv C^d \ (\text{mod} \ N)

___________________________________________________________________________________________________________________

The Mathematical Statement to Validate

What we prove is that the decryption function is to undo the encryption function. Specifically, we prove the following:

    g(C)=g(f(M))=(M^e)^d=M^{ed} \equiv M \ (\text{Mod} \ N) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

In other words, applying the decryption function g to the encryption function f produces the original message.

___________________________________________________________________________________________________________________

Fermat’s Little Theorem

In this section, we list out the tools we need to prove the correctness of RSA.

Theorem 1 (Fermat’s Little Theorem)
If p is a prime number and a is an integer such that a and p are relatively prime, then

    a^{p-1}-1 is an integer multiple of p

    or equivalently a^{p-1} \equiv 1 \ (\text{mod} \ p).

For a proof of Fermat’s little theorem, see this post.

Lemma 2 (Euclid’s Lemma)
Let a, b and d be integers where d \ne 0. Then if d divides a \cdot b (symbolically d \lvert a \cdot b), then either d \lvert a or d \lvert b.

Euclid’s Lemma is needed to prove the following Lemma.

Lemma 3
Let M be an integer. Let p and q be prime numbers with p \ne q.

Then if a \equiv M \ (\text{mod} \ p) and a \equiv M \ (\text{mod} \ q), then a \equiv M \ (\text{mod} \ p \cdot q).

Proof of Lemma 3
Suppose we have a \equiv M \ (\text{mod} \ p) and a \equiv M \ (\text{mod} \ q). Then for some integers i and j, we have:

    a=M+p \cdot i and a=M+q \cdot j.

Then p \cdot i=q \cdot j. This implies that p divides q \cdot j (p \lvert q \cdot j). By Euclid’s lemma, we have either p \lvert q or p \lvert j. Since p and q are distinct prime numbers, we cannot have p \lvert q. So we have p \lvert j and that j=p \cdot w for some integer w.

Now, a=M+q \cdot j=M+q \cdot p \cdot w, implying that a \equiv M \ (\text{mod} \ p \cdot q). \blacksquare

___________________________________________________________________________________________________________________

The Proof of (1)

We now prove the property (1) described above. We show that

    (M^e)^d=M^{ed} \equiv M \ (\text{Mod} \ N=p \cdot q)

We first show that M^{ed} \equiv M \ (\text{Mod} \ p) and M^{ed} \equiv M \ (\text{Mod} \ q). Then the desired result follows from Lemma 3.

To show M^{ed} \equiv M \ (\text{Mod} \ p), we consider two cases: M \equiv 0 \ (\text{Mod} \ p) or M \not \equiv 0 \ (\text{Mod} \ p).

Case 1. M \equiv 0 \ (\text{Mod} \ p). Then M is an integer multiple of p, say M=p \cdot w where w is an integer. Then M^{ed}=(p \cdot w)^{ed}=p \cdot p^{ed-1} \cdot w^{ed}. So both M and M^{ed} are integer multiples of p. Thus M^{ed} \equiv M \ (\text{Mod} \ p).

Case 2. M \not \equiv 0 \ (\text{Mod} \ p). This means that p and M are relatively prime (having no common divisor other than 1). Thus we can use Fermat’s Little Theorem. We have M^{p-1} \equiv 1 \ (\text{mod} \ p).

From the way the decryption key d is defined above, we have ed-1=(p-1) \cdot (q-1) \cdot k for some integer k. We then have:

    \displaystyle \begin{aligned} M^{ed}&=M^{ed-1} \cdot M \\&=M^{(p-1) \cdot (q-1) \cdot k} \cdot M \\&=(M^{p-1})^{(q-1) \cdot k} \cdot M \\&\equiv (1)^{(q-1) \cdot k} \cdot M \ (\text{Mod} \ p) \ * \\&\equiv M \ (\text{Mod} \ p) \end{aligned}

At the step with *, we apply Fermat’s Little Theorem. So we have M^{ed} \equiv M \ (\text{Mod} \ p).

The same reason reasoning can show that M^{ed} \equiv M \ (\text{Mod} \ q).

By Lemma 3, it follows that M^{ed} \equiv M \ (\text{Mod} \ N=p \cdot q). \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Revised August 9, 2014.