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.
Let . We say that divides (or is a divisor of ), denoted , if there is a number such that .
Let . We say that is a prime number if and the only divisors of are and .
Let and be positive integers. We denote by the remainder you get when you divide by . Note that . We say that and are congruent modulo , denoted (or ), if .
If , then by definition, and have the same remainder when they are divided by . So we can write for some and for some . Then , and therefore .
Suppose . Write for some and . Also write for some and . Then . Since , it must be the case that . Since is an integer between and , the only way can divide is if , i.e., .
The above characterization of can be taken as the definition of . Indeed, it is used a lot in proofs.
We write to denote the greatest common divisor of and . Note that for any , and .
We say that and are relatively prime if .
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.
We let denote the set .
For , we define the addition of and , denoted , as . When is clear from the context, we can drop the subscript from and write . For , we can represent the addition operation in using the following table.
In , the element 0 is called the additive identity. It has the property that for any , .
Part 1: Since , we have , and since , we have . This implies , or in other words, . And this is equivalent to .
Part 2: Follows from the previous part and the definition of .
Let . The additive inverse of , denoted , is defined to be an element in such that .
Show that every element of has a unique additive inverse.
The additive inverse of is if , and is otherwise.
To show uniqueness, assume that and are both additive inverses of . Then , which implies .
Let . We define “ minus ”, denoted , as .
Show that in the addition table of , every row and column is a permutation of the elements .
We argue that every row contains distinct elements of , which implies that every row is a permutation of . Take an arbitrary row, which corresponds to some element . Suppose for the sake of contradiction that two entries of this row are the same. Then there exists and in , , such that . But then if we add to both sides of the equality, we get , a contradiction.
The argument for the columns is the same.
For , we define the multiplication of and , denoted , as . If is clear from the context, we can drop the subscript from and write . Furthermore, we can even drop and represent as simply .
Show that if and , then .
Show that for any ,
Part 1: Hint: Write the elements as for some and remainder .
Part 2: Follows from Part 1 and the definition of .
Let . The multiplicative inverse of , denoted , is defined to be an element in such that .
Let . The multiplicative inverse of in exists if and only if .
Let , where has a multiplicative inverse . Then we define “ divided by ”, denoted , as .
We let denote the set . In other words, is the set of all elements of that have a multiplicative inverse.
Show that is closed under multiplication, i.e., .
If and are in , then they have inverses . To show is in , we need to show that it has an inverse modulo . And indeed, is the inverse of since .
Similar to an addition table for , one can consider a multiplication table for . For example, , and the multiplication table is as below:
Show that in the multiplication table of , every row and column is a permutation of the elements .
We argue that every row contains distinct elements of , which implies that every row is a permutation of . Take an arbitrary row, which corresponds to some element . Suppose for the sake of contradiction that two entries of this row are the same. Then there exists and in , , such that . But then if we multiply both sides of the equality by we get , a contradiction.
The argument for the columns is the same.
The Euler totient function is defined as . By convention, .
Show that for a prime number, . Also show that for and distinct prime numbers, .
We know that is the number of elements in that are relatively prime to . If is a prime number, then for any , we have . And . So .
When for distinct primes and , we need to determine the number of elements in that are relatively prime to . The elements that are not relatively prime to are and In total there are of these elements. Then the number of elements that are relatively prime to is .
Let and . We write to denote
(In this proof we drop the subscript from the multiplication notation.) Take an arbitrary . Let be the elements of , where . By Exercise (Multiplication table permutation property), . The product of all the elements in the first set can be written as . This must be equal to the product , i.e. Dividing both sides by (i.e. multiplying both sides by the inverse of ), we get , as desired.
When is a prime number, then Euler’s Theorem is known as Fermat’s Little Theorem.
We can write where is some integer and is the remainder. So . Then where for the last equality, we used Euler’s Theorem.
Since , we can use the previous exercise and reduce the exponent modulo . So . Furthermore, can be reduced modulo . So . And modulo is , which is the answer.
What the previous two exercises demonstrate is that if we are exponentiating an element , then we can effectively think of the exponent as living in the set . This will be important to keep in mind when we cover Cryptography later.
Let . We say that is a generator if
If is a prime number, then contains a generator.
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 . Note that is easy to compute by dividing by and seeing what the remainder is.
In order to compute in , we can simply add and in and then take the sum modulo . To compute , we can do in and then take the result modulo .
In order to compute in , we can multiply and in and then take the product modulo . To compute , we first need to figure out whether has a multiplicative inverse. Recall that exists if and only if and are relatively prime, i.e. . The following algorithm, known as Euclid’s Algorithm, efficiently computes the greatest common divisor of two numbers.
:
If , then return .
Else return .
Show that if , . Use this to show that Euclid’s Algorithm correctly computes the greatest common divisor of two numbers.
If divides and , then it must divide . In particular, divides both and , and therefore .
If divides and , then it must divide . In particular, divides both and , and therefore .
So we can conclude .
When , if we iteratively use the equality to subtract from the larger number , then we will eventually arrive at . For example: So eventually ends up at .
is obviously equal to . 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.
Suppose and can be represented with at most bits each. Give an upper bound on the number of recursive calls Euclid’s Algorithm makes in terms of .
We claim that . To see this, we case on whether . If , then the claim is true because is always less than . If , then the claim is true because .
Now when we call the algorithm with input and make a recursive call, the next pair of inputs is . Using the claim above, we have . 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 , which is if and are at most -bits.
Using Euclid’s Algorithm, we can check if and determine if has a multiplicative inverse. It turns out that a slight modification of Euclid’s Algorithm also allows us to compute if it exists. In order to show this, we first need a definition.
Let . We say that is a miix of and if for some .
Let . If is a miix of and , then . Furthermore, we know we can write for some integer , and for some integer . Therefore which shows is a multiple of .
Show how to extend Euclid’s algorithm so that it outputs and such that . Then conclude that if is any multiple of , then is a miix of and .
Here is the extended Euclid’s algorithm.
Here, we have modified Euclid’s algorithm to return a tuple of variables; Extended-Euclid where and By the correctness of Euclid’s algorithm, we can conclude that the returned value is the gcd (both algorithms do the same calculations for ). We use induction on the number of steps to argue correctness of the returned values
Base Case: If divides , the algorithm correctly returns and .
Induction Step: Suppose the algorithm ran for steps. By the induction hypothesis, we can assume that Since we can write where , we can say . Thus, the returned tuple is correct.
The above algorithm shows that is a miix of and . So if is a multiple of , it is also a miix of and .
Suppose has a multiplicative inverse modulo , i.e. . Then by the previous exercise, we can obtain and such that . If we take this equation modulo , we get that . Therefore is the multiplicative inverse of .
To sum up, if we want to compute , we can first compute and then compute .
Prove Proposition (Multiplicative inverse characterization) using the previous two exercises.
The previous two exercises imply that is a miix of and if and only if is a multiple of . Then,
Given , and , we can compute efficiently. Assume that and can be represented using at most bits each. The algorithm below is known as fast modular exponentiation. To understand how the algorithm works, see the example following the algorithm.
:
Repeatedly square to obtain
, , , , .Multiply together (modulo ) the powers of so that the product is .
To figure out which powers to multiply, look at the binary representation of .
Consider the example of computing . The first step of the algorithm computes by squaring modulo times. The binary representation of is . This implies that Therefore, to calculate , the second step of the algorithm does:
Suppose and are integers that can be represented using at most bits. Give an upper bound on the running time of the above algorithm in terms of .
Consider the following computational problem. You are given with . The goal is to output such that . In other words, the goal is to find the ’th root of in (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).
Consider the following computational problem which is known as the Discrete Log Problem in . You are given , where is a prime number, , and is a generator (Theorem ( contains a generator) tells us that always contains a generator). The goal is to output such that . In a sense, this is like trying to compute in . 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).
Wilson’s theorem states that is prime if and only if . Can we use this fact in the obvious way to design a polynomial time algorithm for isPrime?
True or false: Suppose that , where . Then .
Determine, with proof, . Note that is prime.
Determine, with proof, .
Let be a generator in , and let be chosen uniformly at random. For every , determine .
Let be chosen uniformly at random. For every , determine .
What is Euler’s Theorem?
What is a generator in ?
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?
What is an efficient algorithm for finding the multiplicative inverse of an element in ?
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.
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).