MODULE 10:   Cryptography
Modular Arithmetic

This chapter contains some mathematical background needed to discuss cryptography, which is the topic of the next chapter. In particular, we will be reviewing modular arithmetic, which we assume you are already familiar with. We’ll remind you the basic definitions in this area as well as go over the computational complexities of the most common modular arithmetic operations. For cryptographic applications, we use the fact that some modular operations are efficiently computable, but also exploit the assumed computational hardness of other modular operations. Therefore, the distinction between which operations are efficiently computable and which ones are not is important to understand.

1
Preliminary Definitions
Definition (AA divides BB)

Let A,BZA, B \in \mathbb Z. We say that AA divides BB (or AA is a divisor of BB), denoted ABA | B, if there is a number CZC \in \mathbb Z such that B=ACB = AC.

Definition (Prime number)

Let PNP \in \mathbb N. We say that PP is a prime number if P2P \geq 2 and the only divisors of PP are 11 and PP.

Definition (Congruence modulo NN)

Let A,BA, B and NN be positive integers. We denote by AmodNA \bmod N the remainder you get when you divide AA by NN. Note that AmodN{0,1,2,,N1}A \bmod N \in \{0,1,2,\ldots,N-1\}. We say that AA and BB are congruent modulo NN, denoted ANBA \equiv_N B (or ABmodNA \equiv B \bmod N), if AmodN=BmodNA \bmod N = B \bmod N.

Exercise (A characterization for congruence modulo NN)

Show that ANBA \equiv_N B if and only if N(AB)N | (A - B).

Solution

If ANBA \equiv_N B, then by definition, AA and BB have the same remainder RR when they are divided by NN. So we can write A=QN+RA = Q\cdot N + R for some QZQ \in \mathbb Z and B=QN+RB = Q' \cdot N + R for some QZQ' \in \mathbb Z. Then AB=(QQ)NA-B = (Q - Q') \cdot N, and therefore N(AB)N | (A-B).

Suppose N(AB)N | (A-B). Write A=QN+RA = Q \cdot N + R for some QZQ \in \mathbb Z and R{0,1,,N1}R \in \{0,1,\ldots, N-1\}. Also write B=QN+RB = Q' \cdot N + R' for some QZQ' \in \mathbb Z and R{0,1,,N1}R' \in \{0,1,\ldots, N-1\}. Then AB=(QQ)N+(RR)A - B = (Q - Q') \cdot N + (R - R'). Since N(AB)N | (A-B), it must be the case that N(RR)N | (R - R'). Since RRR-R' is an integer between (N1)-(N-1) and (N1)(N-1), the only way NN can divide RRR-R' is if R=RR=R', i.e., ANBA \equiv_N B.

Note

The above characterization of ANBA \equiv_N B can be taken as the definition of ANBA \equiv_N B. Indeed, it is used a lot in proofs.

Definition (gcd)

We write gcd(A,B)\gcd(A, B) to denote the greatest common divisor of AA and BB. Note that for any AA, gcd(A,1)=1\gcd(A,1) = 1 and gcd(A,0)=A\gcd(A, 0) = A.

Definition (Relatively prime)

We say that AA and BB are relatively prime if gcd(A,B)=1\gcd(A,B) = 1.

In the section below, we first give the definitions of basic modular operations like addition, subtraction, multiplication, division and exponentiation. We also explore some of their properties. In the section after, we look at the computational complexity of these operations. Being able to compute these operations efficiently is crucial for applications.

2
Modular operations: Definitions and properties
2.1
Addition and subtraction
Definition (ZN\mathbb Z_N)

We let ZN\mathbb Z_N denote the set {0,1,2,,N1}\{0,1,2,\ldots,N-1\}.

Definition (Addition in ZN\mathbb Z_N)

For A,BZNA, B \in \mathbb Z_N, we define the addition of AA and BB, denoted A+NBA +_N B, as (A+B)modN(A+B) \bmod N. When NN is clear from the context, we can drop the subscript NN from +N+_N and write ++. For N=5N=5, we can represent the addition operation in Z5\mathbb Z_5 using the following table.

image

In ZN\mathbb Z_N, the element 0 is called the additive identity. It has the property that for any AZNA \in \mathbb Z_N, A+N0=0+NA=AA +_N 0 = 0 +_N A = A.

Exercise (Addition modulo NN behaves nicely)
  • Show that if ANBA \equiv_N B and ANBA' \equiv_N B', then A+ANB+BA+ A' \equiv_N B+B'.

  • Show that for any A,BZA,B \in \mathbb Z, (A+B)modN=(AmodN)+N(BmodN).(A + B) \bmod N = (A \bmod N) +_N (B \bmod N).

Solution

Part 1: Since ANBA \equiv_N B, we have N(AB)N | (A-B), and since ANBA' \equiv_N B', we have N(AB)N | (A'-B'). This implies N(AB)+(AB)N | (A-B) + (A'-B'), or in other words, N(A+A)(B+B)N | (A+A') - (B+B'). And this is equivalent to A+ANB+BA + A' \equiv_N B + B'.

Part 2: Follows from the previous part and the definition of +N+_N.

Definition (Additive inverse)

Let AZNA \in \mathbb Z_N. The additive inverse of AA, denoted A-A, is defined to be an element in ZN\mathbb Z_N such that A+NA=0A +_N -A = 0.

Exercise (Additive inverses modulo NN are unique)

Show that every element of ZN\mathbb Z_N has a unique additive inverse.

Solution

The additive inverse of AZNA \in \mathbb Z_N is 00 if A=0A = 0, and is NAN-A otherwise.

To show uniqueness, assume that A-A and A-A' are both additive inverses of AA. Then A+NA=A+NA=0A +_N -A = A +_N -A' = 0, which implies A=A-A = -A'.

Definition (Subtraction in ZN\mathbb Z_N)

Let A,BZNA, B \in \mathbb Z_N. We define “AA minus BB”, denoted ANBA -_N B, as A+NBA +_N -B.

Exercise (Addition table permutation property)

Show that in the addition table of ZN\mathbb Z_N, every row and column is a permutation of the elements ZN\mathbb Z_N.

Solution

We argue that every row contains distinct elements of ZN\mathbb Z_N, which implies that every row is a permutation of ZN\mathbb Z_N. Take an arbitrary row, which corresponds to some element AZNA \in \mathbb Z_N. Suppose for the sake of contradiction that two entries of this row are the same. Then there exists BB and BB' in ZN\mathbb Z_N, BBB \neq B', such that A+NB=A+NBA +_N B = A +_N B'. But then if we add A-A to both sides of the equality, we get B=BB = B', a contradiction.

The argument for the columns is the same.

2.2
Multiplication and division
Definition (Multiplication in ZN\mathbb Z_N)

For A,BZNA, B \in \mathbb Z_N, we define the multiplication of AA and BB, denoted ANBA \cdot_N B, as ABmodNAB \bmod N. If NN is clear from the context, we can drop the subscript NN from N\cdot_N and write \cdot. Furthermore, we can even drop \cdot and represent ANBA \cdot_N B as simply ABAB.

Exercise (Multiplication modulo NN behaves nicely)
  • Show that if ANBA \equiv_N B and ANBA' \equiv_N B', then AANBBAA' \equiv_N BB'.

  • Show that for any A,BZA,B \in \mathbb Z, ABmodN=(AmodN)N(BmodN).AB \bmod N = (A \bmod N) \cdot_N (B \bmod N).

Solution

Part 1: Hint: Write the elements as QN+RQN + R for some QZQ \in \mathbb Z and remainder R{0,1,,N1}R \in \{0,1,\ldots,N-1\}.

Part 2: Follows from Part 1 and the definition of N\cdot_N.

Definition (Multiplicative inverse)

Let AZNA \in \mathbb Z_N. The multiplicative inverse of AA, denoted A1A^{-1}, is defined to be an element in ZN\mathbb Z_N such that ANA1=1A \cdot_N A^{-1} = 1.

Proposition (Multiplicative inverse characterization)

Let A,NNA,N \in \mathbb N. The multiplicative inverse of AA in ZN\mathbb Z_N exists if and only if gcd(A,N)=1\gcd(A,N) = 1.

Definition (Division in ZN\mathbb Z_N)

Let A,BZNA, B \in \mathbb Z_N, where BB has a multiplicative inverse B1B^{-1}. Then we define “AA divided by BB”, denoted A/NBA /_N B, as ANB1A \cdot_N B^{-1}.

Definition (ZN\mathbb Z_N^*)

We let ZN\mathbb Z_N^* denote the set {AZN:gcd(A,N)=1}\{A \in \mathbb Z_N : \gcd(A, N) = 1\}. In other words, ZN\mathbb Z_N^* is the set of all elements of ZN\mathbb Z_N that have a multiplicative inverse.

Exercise (ZN\mathbb Z_N^* is closed under multiplication)

Show that ZN\mathbb Z_N^* is closed under multiplication, i.e., A,BZN    ANBZNA,B \in \mathbb Z_N^* \implies A \cdot_N B \in \mathbb Z_N^*.

Solution

If AA and BB are in ZN\mathbb Z_N^*, then they have inverses A1,B1ZNA^{-1}, B^{-1} \in \mathbb Z_N^*. To show ANBA \cdot_N B is in ZN\mathbb Z_N^*, we need to show that it has an inverse modulo NN. And indeed, B1NA1B^{-1} \cdot_N A^{-1} is the inverse of ANBA \cdot_N B since ANBNB1NA1=1A \cdot_N B \cdot_N B^{-1} \cdot_N A^{-1} = 1.

Note (Multiplication table for ZN\mathbb Z_N^*)

Similar to an addition table for ZN\mathbb Z_N, one can consider a multiplication table for ZN\mathbb Z_N^*. For example, Z8={1,3,5,7}\mathbb Z_8^* = \{1, 3, 5, 7\}, and the multiplication table is as below:

image

Exercise (Multiplication table permutation property)

Show that in the multiplication table of ZN\mathbb Z_N^*, every row and column is a permutation of the elements ZN\mathbb Z_N^*.

Solution

We argue that every row contains distinct elements of ZN\mathbb Z_N^*, which implies that every row is a permutation of ZN\mathbb Z_N^*. Take an arbitrary row, which corresponds to some element AZNA \in \mathbb Z_N^*. Suppose for the sake of contradiction that two entries of this row are the same. Then there exists BB and BB' in ZN\mathbb Z_N^*, BBB \neq B', such that ANB=ANBA \cdot_N B = A \cdot_N B'. But then if we multiply both sides of the equality by A1A^{-1} we get B=BB = B', a contradiction.

The argument for the columns is the same.

Definition (Euler totient function)

The Euler totient function φ:NN\varphi : \mathbb N\to \mathbb N is defined as φ(N)=ZN\varphi(N) = |\mathbb Z_N^*|. By convention, φ(0)=0\varphi(0) = 0.

Exercise (φ(P)\varphi(P) and φ(PQ)\varphi(PQ))

Show that for PP a prime number, φ(P)=P1\varphi(P) = P-1. Also show that for PP and QQ distinct prime numbers, φ(PQ)=(P1)(Q1)\varphi(PQ) = (P-1)(Q-1).

Solution

We know that φ(N)\varphi(N) is the number of elements in {0,1,2,,N1}\{0,1,2,\ldots,N-1\} that are relatively prime to NN. If PP is a prime number, then for any A{1,2,,P1}A \in \{1,2,\ldots,P-1\}, we have gcd(A,P)=1\gcd(A,P) = 1. And gcd(0,P)=P\gcd(0,P) = P. So φ(P)=P1\varphi(P) = P-1.

When N=PQN = PQ for distinct primes PP and QQ, we need to determine the number of elements in {0,1,2,,PQ1}\{0,1,2,\ldots,PQ-1\} that are relatively prime to PQPQ. The elements that are not relatively prime to PQPQ are 00 and P,2P,3P,,(Q1)P,Q,2Q,3Q,,(P1)Q.\begin{aligned} P, 2P, 3P, \ldots, (Q-1)P, \\ Q, 2Q, 3Q, \ldots, (P-1)Q.\end{aligned} In total there are 1+(Q1)+(P1)=Q+P11 + (Q-1) + (P-1) = Q + P - 1 of these elements. Then the number of elements that are relatively prime to PQPQ is PQ(Q+P1)=PQQP+1=(P1)(Q1)PQ - (Q + P - 1) = PQ - Q - P + 1 = (P-1)(Q-1).

2.3
Exponentiation
Definition (Exponentiation in ZN\mathbb Z_N)

Let AZNA \in \mathbb Z_N and EZE \in \mathbb Z. We write AEA^E to denote ANANNAE times.\underbrace{A \cdot_N A \cdot_N \cdots \cdot_N A}_{E \text{ times}}.

Theorem (Euler’s Theorem)

For any AZNA \in \mathbb Z_N^*, Aφ(N)=1A^{\varphi(N)} = 1. Equivalently, for any A,NZA,N \in \mathbb Z with gcd(A,N)=1\gcd(A,N) = 1, Aφ(N)N1A^{\varphi(N)} \equiv_N 1.

Proof

(In this proof we drop the subscript NN from the multiplication notation.) Take an arbitrary AZNA \in \mathbb Z_N^*. Let B1,B2,,BkB_1,B_2,\ldots,B_k be the elements of ZN\mathbb Z_N^*, where k=φ(N)k = \varphi(N). By Exercise (Multiplication table permutation property), {AB1,AB2,,ABk}=ZN\{AB_1, AB_2, \ldots, AB_k\} = \mathbb Z_N^*. The product of all the elements in the first set can be written as (AB1)(AB2)(ABk)(AB_1)(AB_2)\cdots (AB_k). This must be equal to the product B1B2BkB_1B_2 \cdots B_k, i.e. (AB1)(AB2)(ABk)=B1B2Bk.(AB_1)(AB_2)\cdots (AB_k) = B_1B_2\cdots B_k. Dividing both sides by B1B2BkB_1B_2\cdots B_k (i.e. multiplying both sides by the inverse of B1B2BkB_1B_2 \cdots B_k), we get Ak=1A^k = 1, as desired.

Note (Fermat’s Little Theorem)

When NN is a prime number, then Euler’s Theorem is known as Fermat’s Little Theorem.

Exercise (Reducing exponent modulo φ(N)\varphi(N))

Let AZNA \in \mathbb Z_N^* and EZE \in \mathbb Z. Show that AENAEmodφ(N)A^E \equiv_N A^{E \bmod \varphi(N)}.

Solution

We can write E=φ(N)Q+RE = \varphi(N) \cdot Q + R where QQ is some integer and R{0,1,,φ(N)1}R \in \{0,1,\ldots, \varphi(N)-1\} is the remainder. So Eφ(N)RE \equiv_{\varphi(N)} R. Then AE=Aφ(N)Q+R=(Aφ(N))QAR=AR,A^E = A^{\varphi(N) \cdot Q + R} = \left(A^{\varphi(N)}\right )^Q \cdot A^R = A^R, where for the last equality, we used Euler’s Theorem.

Exercise (Modular computation by hand)

Compute by hand 10298mod7102^{98} \bmod 7.

Solution

Since gcd(102,7)=1\gcd(102,7) = 1, we can use the previous exercise and reduce the exponent modulo 66. So 1029871022102^{98} \equiv_7 102^2. Furthermore, 102102 can be reduced modulo 77. So 1022742102^{2} \equiv_7 4^2. And 1616 modulo 77 is 22, which is the answer.

Important Note (Exponent lives in Zφ(N)\mathbb Z_{\varphi(N)})

What the previous two exercises demonstrate is that if we are exponentiating an element AZNA \in \mathbb Z_N^*, then we can effectively think of the exponent as living in the set Zφ(N)\mathbb Z_{\varphi(N)}. This will be important to keep in mind when we cover Cryptography later.

Definition (Generator in ZN\mathbb Z_N^*)

Let AZNA \in \mathbb Z_N^*. We say that AA is a generator if {AE:EZφ(N)}=ZN.\{A^E : E \in \mathbb Z_{\varphi(N)}\} = \mathbb Z_N^*.

Theorem (ZP\mathbb Z_P^* contains a generator)

If PP is a prime number, then ZP\mathbb Z_P^* contains a generator.

3
Modular operations: Computational complexity

In this section, we will look at the computational complexities of doing the basic modular operations discussed in the previous section. We will use the fact that addition, subtraction, multiplication and division operations can be computed efficiently in Z\mathbb Z. Note that AmodNA \bmod N is easy to compute by dividing AA by NN and seeing what the remainder is.

3.1
Addition and subtraction

In order to compute A+NBA +_N B in ZN\mathbb Z_N, we can simply add AA and BB in Z\mathbb Z and then take the sum modulo NN. To compute ANBA -_N B, we can do A+(NB)A + (N-B) in Z\mathbb Z and then take the result modulo NN.

3.2
Multiplication and division

In order to compute ANBA \cdot_N B in ZN\mathbb Z_N, we can multiply AA and BB in Z\mathbb Z and then take the product modulo NN. To compute A/NB=ANB1A /_N B = A \cdot_N B^{-1}, we first need to figure out whether BB has a multiplicative inverse. Recall that B1B^{-1} exists if and only if BB and NN are relatively prime, i.e. gcd(B,N)=1\gcd(B,N) = 1. The following algorithm, known as Euclid’s Algorithm, efficiently computes the greatest common divisor of two numbers.

Algorithm (Euclid’s gcd algorithm)

gcd(A,B)\gcd(A, B):

  • If B=0B = 0, then return AA.

  • Else return gcd(B,AmodB)\gcd(B, A \bmod B).

Exercise (gcd property)

Show that if ABA \geq B, gcd(A,B)=gcd(AB,B)\gcd(A,B) = \gcd(A-B, B). Use this to show that Euclid’s Algorithm correctly computes the greatest common divisor of two numbers.

Solution

If xx divides AA and BB, then it must divide ABA-B. In particular, gcd(A,B)\gcd(A,B) divides both BB and ABA-B, and therefore gcd(AB,B)gcd(A,B)\gcd(A-B,B) \geq \gcd(A, B).

If xx divides ABA-B and BB, then it must divide AA. In particular, gcd(AB,B)\gcd(A-B,B) divides both AA and BB, and therefore gcd(A,B)gcd(AB,B)\gcd(A,B) \geq \gcd(A-B, B).

So we can conclude gcd(A,B)=gcd(AB,B)\gcd(A,B) = \gcd(A-B,B).

When ABA \geq B, if we iteratively use the equality gcd(A,B)=gcd(AB,B)\gcd(A,B) = \gcd(A-B,B) to subtract BB from the larger number AA, then we will eventually arrive at gcd(A,B)=gcd(AmodB,B)\gcd(A,B) = \gcd(A \bmod B, B). For example: gcd(6004,6)=gcd(5998,6)=gcd(5992,6)=gcd(5986,6)=gcd(4,6).\begin{aligned} \gcd(6004, 6) & = \gcd(5998, 6) \\ & = \gcd(5992, 6) \\ & = \gcd(5986, 6) \\ & \cdots \\ & = \gcd(4,6).\end{aligned} So gcd(6004,6)\gcd(6004, 6) eventually ends up at gcd(6004mod6,6)\gcd(6004 \bmod 6, 6).

gcd(AmodB,B)\gcd(A \bmod B, B) is obviously equal to gcd(B,AmodB)\gcd(B, A \bmod B). So one can show that Euclid’s algorithm is correct by an induction argument, where the base case corresponds to the base case of the recursive algorithm, and the induction step corresponds to the recursive call.

Exercise (Time complexity of Euclid’s algorithm)

Suppose AA and BB can be represented with at most nn bits each. Give an upper bound on the number of recursive calls Euclid’s Algorithm makes in terms of nn.

Solution

We claim that AmodBA/2A \bmod B \leq A/2. To see this, we case on whether A2BA \geq 2B. If A2BA \geq 2B, then the claim is true because AmodBA \bmod B is always less than BB. If A<2BA < 2B, then the claim is true because AmodB=AB<AA/2=A/2A \bmod B = A - B < A - A/2 = A/2.

Now when we call the algorithm with input (A,B)(A, B) and make a recursive call, the next pair of inputs is (B,AmodB)(B, A \bmod B). Using the claim above, we have (AmodB)BAB/2(A \bmod B) \cdot B \leq A B/2. So in each recursive call, the product of the inputs is going down by a factor of at least 2. And this implies the number of recursive calls is at most log2(AB)\log_2 (A B), which is O(n)O(n) if AA and BB are at most nn-bits.

Using Euclid’s Algorithm, we can check if gcd(B,N)=1\gcd(B,N) = 1 and determine if BB has a multiplicative inverse. It turns out that a slight modification of Euclid’s Algorithm also allows us to compute B1B^{-1} if it exists. In order to show this, we first need a definition.

Definition (Miix)

Let A,B,CNA,B,C \in \mathbb N. We say that CC is a miix of AA and BB if C=kA+BC = k A + \ell B for some k,Zk, \ell \in \mathbb Z.

Exercise (Miix vs gcd 1)

Let A,B,CNA,B,C \in \mathbb N. Show that if CC is a miix of AA and BB then CC is a multiple of gcd(A,B)\gcd(A,B).

Solution

Let G=gcd(A,B)G = \gcd(A, B). If CC is a miix of AA and BB, then C=kA+BC = kA + \ell B. Furthermore, we know we can write A=xGA = xG for some integer xx, and B=yGB = yG for some integer yy. Therefore C=kA+B=kxG+yG=G(kx+y),C = kA + \ell B = kxG + \ell yG = G(kx + \ell y), which shows CC is a multiple of GG.

Exercise (Miix vs gcd 2)

Show how to extend Euclid’s algorithm so that it outputs kk and \ell such that gcd(A,B)=kA+B\gcd(A,B) = k A + \ell B. Then conclude that if CC is any multiple of gcd(A,B)\gcd(A,B), then CC is a miix of AA and BB.

Solution

Here is the extended Euclid’s algorithm.

def    Extended-Euclid(A,B):1.    If B divides A, return (B,0,1).2.    Else:3.        (G,k,)=Extended-Euclid(B,AmodB)4.        Return (G,,(kA/B))\begin{aligned} \hline\hline\\[-12pt] &\textbf{def}\;\; \text{Extended-Euclid}(A,B):\\ &{\scriptstyle 1.}~~~~\texttt{If $B$ divides $A$, return $(B, 0, 1)$.}\\ &{\scriptstyle 2.}~~~~\texttt{Else:}\\ &{\scriptstyle 3.}~~~~~~~~(G,k,\ell) = \text{Extended-Euclid}(B, A \bmod B)\\ &{\scriptstyle 4.}~~~~~~~~\texttt{Return $(G,\ell, (k-\ell \cdot \lfloor A/B \rfloor ) )$}\\ \hline\hline\end{aligned}

Here, we have modified Euclid’s algorithm to return a tuple of variables; Extended-Euclid(A,B)=(G,k,)(A,B) = (G,k,\ell) where G=gcd(A,B)G = \gcd(A,B) and G=kA+B.G = k \cdot A + \ell \cdot B. By the correctness of Euclid’s algorithm, we can conclude that the returned value GG is the gcd (both algorithms do the same calculations for GG). We use induction on the number of steps to argue correctness of the returned values (k,).(k,\ell).

Base Case: If BB divides AA, the algorithm correctly returns k=0k=0 and =1\ell=1.

Induction Step: Suppose the algorithm ran for s>1s >1 steps. By the induction hypothesis, we can assume that G=kB+(AmodB).G = k \cdot B + \ell \cdot (A \bmod B). Since we can write A=qB+(AmodB)A = q\cdot B + (A \bmod B) where q=A/Bq = \lfloor A/B \rfloor, we can say G=kB+(AqB)G = k \cdot B + \ell (A - q\cdot B). Thus, the returned tuple (G,,kA/B)(G, \ell, k - \ell \cdot \lfloor A/B \rfloor) is correct.

The above algorithm shows that gcd(A,B)\gcd(A,B) is a miix of AA and BB. So if CC is a multiple of gcd(A,B)\gcd(A,B), it is also a miix of AA and BB.

Suppose BB has a multiplicative inverse modulo NN, i.e. gcd(B,N)=1\gcd(B,N) = 1. Then by the previous exercise, we can obtain kk and \ell such that 1=kB+N1 = kB + \ell N. If we take this equation modulo NN, we get that kBN1kB \equiv_N 1. Therefore kk is the multiplicative inverse of BB.

To sum up, if we want to compute A/NB=ANB1A /_N B = A \cdot_N B^{-1}, we can first compute B1B^{-1} and then compute ANB1A \cdot_N B^{-1}.

Exercise

Prove Proposition (Multiplicative inverse characterization) using the previous two exercises.

Solution

The previous two exercises imply that CC is a miix of AA and BB if and only if CC is a multiple of gcd(A,B)\gcd(A,B). Then, A1 exists   k such that kAN1  k such that N divides kA1   k,q such that kA1=qN  k,q such that 1=kA+(q)N  1 is a miix of A and N  gcd(A,N)=1.\begin{aligned} A^{-1} \text{ exists } & \Longleftrightarrow \; \exists k \text{ such that } k A \equiv_N 1 \\ & \Longleftrightarrow \; \exists k \text{ such that $N$ divides $kA - 1$ } \\ & \Longleftrightarrow \; \exists k, q \text{ such that } k A - 1 = qN \\ & \Longleftrightarrow \; \exists k, q \text{ such that } 1 = kA + (-q)N \\ & \Longleftrightarrow \; \text{1 is a miix of $A$ and $N$} \\ & \Longleftrightarrow \; \gcd(A,N) = 1.\end{aligned}

3.3
Exponentiation

Given NNN \in \mathbb N, AZNA \in \mathbb Z_N and ENE \in \mathbb N, we can compute AEmodNA^E \bmod N efficiently. Assume that A,EA, E and NN can be represented using at most nn bits each. The algorithm below is known as fast modular exponentiation. To understand how the algorithm works, see the example following the algorithm.

Algorithm (Fast modular exponentiation)

FME(A,E,N)\text{FME}(A, E, N):

  • Repeatedly square AA to obtain
    A2modNA^2 \bmod N, A4modNA^4 \bmod N, A8modNA^8 \bmod N, \ldots, A2nmodNA^{2^n} \bmod N.

  • Multiply together (modulo NN) the powers of AA so that the product is AEA^E.
    To figure out which powers to multiply, look at the binary representation of EE.

Consider the example of computing 233753mod1002337^{53} \bmod 100. The first step of the algorithm computes 23372mod10023374mod10023378mod100233716mod100233732mod100\begin{aligned} 2337^{2} \bmod 100 \\ 2337^{4} \bmod 100 \\ 2337^{8} \bmod 100 \\ 2337^{16} \bmod 100 \\ 2337^{32} \bmod 100 \end{aligned} by squaring 23372337 modulo 100100 55 times. The binary representation of 5353 is 110101110101. This implies that 53=1+4+16+32.53 = 1 + 4 + 16 + 32. Therefore, to calculate 233753mod1002337^{53} \bmod 100, the second step of the algorithm does: (2337mod100)(23374mod100)(233716mod100)(233732mod100).(2337 \bmod 100) \cdot (2337^{4} \bmod 100) \cdot (2337^{16} \bmod 100) \cdot (2337^{32} \bmod 100).

Exercise

Suppose A,EA, E and NN are integers that can be represented using at most nn bits. Give an upper bound on the running time of the above algorithm in terms of nn.

3.4
Taking roots

Consider the following computational problem. You are given A,E,NNA, E, N \in \mathbb N with AZNA \in \mathbb Z_N^*. The goal is to output BNB \in \mathbb N such that BENAB^E \equiv_N A. In other words, the goal is to find the EE’th root of AA in ZN\mathbb Z_N^* (if it exists). Many experts believe (but cannot prove) that this problem cannot be computed in polynomial time. The assumed hardness of this problem is used in the famous RSA cryptosystem (see the chapter on Cryptography for details).

3.5
Taking logarithms

Consider the following computational problem which is known as the Discrete Log Problem in ZP\mathbb Z_P^*. You are given A,B,PNA, B, P \in \mathbb N, where PP is a prime number, AZPA \in \mathbb Z_P^*, and BZPB \in \mathbb Z_P^* is a generator (Theorem (ZP\mathbb Z_P^* contains a generator) tells us that ZP\mathbb Z_P^* always contains a generator). The goal is to output XNX \in \mathbb N such that BXPAB^X \equiv_P A. In a sense, this is like trying to compute logBA\log_B A in ZN\mathbb Z_N^*. Many experts believe (but cannot prove) that this problem cannot be computed in polynomial time. The assumed hardness of this problem is used in the famous Diffie-Hellman secret key exchange protocol (see the chapter on Cryptography for details).

4
Check Your Understanding
Problem
  1. Wilson’s theorem states that NN is prime if and only if (N1)!NN1(N-1)! \equiv_N N-1. Can we use this fact in the obvious way to design a polynomial time algorithm for isPrime?

  2. True or false: Suppose that AKN1A^K \equiv_N 1, where A1A \neq 1. Then φ(N)K\varphi(N) | K.

  3. Determine, with proof, 75010002(mod251)750^{10002} \pmod{251}. Note that 251251 is prime.

  4. Determine, with proof, 251(15251)(mod7)251^{(15^{251})} \pmod{7}.

  5. Let GG be a generator in ZN\mathbb Z_N^*, and let RZφ(N)R \in \mathbb Z_{\varphi(N)} be chosen uniformly at random. For every AZNA \in \mathbb Z_N^*, determine Pr[GR=A]\Pr[G^R = A].

  6. Let RZNR \in \mathbb Z_N^* be chosen uniformly at random. For every A,BZNA, B \in \mathbb Z_N^*, determine Pr[ANR=B]\Pr[A \cdot_N R = B].

  7. What is Euler’s Theorem?

  8. What is a generator in ZN\mathbb Z_N^*?

  9. Consider the addition, subtraction, multiplication, division, exponentiation, taking logarithm, and taking root. Which of these operations are known to be polynomial-time solvable when the universe is the integers? Which of them are known to be polynomial-time solvable in the modular universe?

  10. What is an efficient algorithm for finding the multiplicative inverse of an element in ZN\mathbb Z_N^*?

5
High-Order Bits
Important Note
  1. The theory behind modular arithmetic should mostly be review. It is important to know how the basic operations are defined and what kind of properties they have.

  2. For which modular arithmetic operations do we have an efficient algorithm for (and what is that algorithm)? For which operations do we not expect to have an efficient algorithm? And for these operations, why don’t the “obvious” algorithms work? You should have a solid understanding of all these. Please internalize Important Note (Our model when measuring running time) and Important Note (Integer inputs are large numbers).

Exercise (Multiplication table permutation property)

Show that in the multiplication table of \(\mathbb Z_N^*\), every row and column is a permutation of the elements \(\mathbb Z_N^*\).

See in chapter
Theorem (Euler’s Theorem)

For any \(A \in \mathbb Z_N^*\), \(A^{\varphi(N)} = 1\). Equivalently, for any \(A,N \in \mathbb Z\) with \(\gcd(A,N) = 1\), \(A^{\varphi(N)} \equiv_N 1\).

See in chapter
Proposition (Multiplicative inverse characterization)

Let \(A,N \in \mathbb N\). The multiplicative inverse of \(A\) in \(\mathbb Z_N\) exists if and only if \(\gcd(A,N) = 1\).

See in chapter
Theorem (\(\mathbb Z_P^*\) contains a generator)

If \(P\) is a prime number, then \(\mathbb Z_P^*\) contains a generator.

See in chapter
Important Note (Our model when measuring running time)

In the Turing machine model, a step in the computation corresponds to one application of the transition function of the machine. However, when measuring running time, often we will not be considering the Turing machine model.

If we don’t specify a particular computational model, by default, our model will be closely related to the Random Access Machine (RAM) model. Compared to TMs, this model aligns better with the architecture of the computers we use today. We will not define this model formally, but instead point out two properties of importance.

First, given a string or an array, accessing any index counts as 1 step.

Second, arithmetic operations count as 1 step as long as the numbers involved are “small”. We say that a number \(y\) is small if it can be upper bounded by a polynomial in \(n\), the input length. That is, \(y\) is small if there is some constant \(k\) such that \(y\) is \(O(n^k)\). As an example, suppose we have an algorithm \(A\) that contains a line like \(x = y + z\), where \(y\) and \(z\) are variables that hold integer values. Then we can count this line as a single step if \(y\) and \(z\) are both small. Note that whether a number is small or not is determined by the length of the input to the algorithm \(A\).

We say that a number is large, if it is not small, i.e., if it cannot be upper bounded by a polynomial in \(n\). In cases where we are doing arithmetic operations involving large numbers, we have to consider the algorithms used for the arithmetic operations and figure out their running time. For example, in the line \(x = y + z\), if \(y\) or \(z\) is a large number, we need to specify what algorithm is being used to do the addition and what its running time is. A large number should be treated as a string of digits/characters. Arithmetic operations on large numbers should be treated as string manipulation operations and their running time should be figured out accordingly.

See in chapter
Important Note (Integer inputs are large numbers)

Given a computational problem with an integer input \(x\), notice that \(x\) is a large number (if \(x\) is \(n\) bits long, its value can be about \(2^n\), so it cannot be upper bounded by a polynomial in \(n\)). Therefore arithmetic operations involving \(x\) cannot be treated as 1-step operations. Computational problems with integer input(s) are the most common examples in which we have to deal with large numbers, and in these situations, one should be particularly careful about analyzing running time.

See in chapter