Discrete Mathematics lecture notes

discrete mathematics mathematical reasoning, what is discrete mathematics and its applications ,lecture notes discrete mathematics and its application pdf free download
Dr.SamuelHunt Profile Pic
Dr.SamuelHunt,United Arab Emirates,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
CPS 102 DISCRETE MATHEMATICS FOR COMPUTER SCIENCE Spring 2009 Co-instructors: Herbert Edelsbrunner and Brittany FasyCPS 102 Spring Semester of 2009 Table of Contents Introduction 3 IV INDUCTION 32 I COUNTING 4 11 Mathematical Induction 33 12 Recursion 35 1 Sets and Lists 5 13 Growth Rates 37 2 Binomial Coefficients 8 14 Solving Recurrence Relations 39 3 Equivalence Relations 10 Homework Assignments 41 Homework Assignments 12 V PROBABILITY 42 II NUMBER THEORY 13 15 Inclusion-Exclusion 43 4 Modular Arithmetic 14 16 Conditional Probability 45 5 Inverses 16 17 Random Variables 47 6 Euclid’s Algorithm 18 18 Probability in Hashing 49 7 RSA Cryptosystem 20 19 Probability Distributions 51 Homework Assignments 22 Homework Assignments 53 III LOGIC 23 VI GRAPHS 54 8 Boolean Algebra 24 20 Trees 55 9 Quantifiers 27 21 Tours 58 10 Inference 29 22 Matching 60 Homework Assignments 31 23 Planar Graphs 63 Homework Assignments 66 2Introduction Overview. Discrete mathematics provides concepts that are fundamental to computer science but also other dis- ciplines. This course emphasizes the computer science Meetings. We meet twice a week for lectures, on Mon- connection through the selection and motivation of topics, day and on Wednesday, from 2:50 to 4:05pm, in room which are grouped in six major themes: D243 LSRC. We also have a recitation each week on Fri- day, same time and room as the lectures. I Counting; II Number Theory; Communication. The course material will be delivered III Logic; in the two weekly lectures. A written record of the lec- tures will be available on the web, usually a day after the IV Induction; lecture. The web also contains other information, such as V Probability; homework assignments, solutions, useful links, etc. The VI Graphs. main supporting text is BOGART, STEIN, DRYSDALE. Discrete Mathematics for Computer Science. Key College Publishing, Emeryville, Cali- fornia, 2006. Examinations. There will be a final exam (covering the material of the entire semester) and two midterm. The weighting of participation, exams, and homework used to determine your grades is class participation 10%, homework 30%, midterms 30%, final 30%. Homework. We have six homeworks scheduled throughout this semester, one per main topic covered in the course. The solutions to each homework are due one and a half weeks after the assignment. More precisely, they are due at the beginning of the third lecture after the assignment. The sixth homework may help you prepare for the final exam and solutions will not be collected. RULE 1. The solution to any one homework question must fit on a single page (together with the statement of the problem). RULE 2. The discussion of questions and solutions before the due date is not discouraged, but you must formu- late your own solution. RULE 3. The deadline for turning in solutions is 10 min- utes after the beginning of the lecture on the due date. 3I COUNTING Counting things is a central problem in Discrete Mathematics. Once we can count, we can determine the likelihood of a particular even and we can estimate how long a computer algorithm takes to complete a task. 1 Sets and Lists 2 Binomial Coefficients 3 Equivalence Relations Homework Assignments 41 Sets and Lists Sets and lists are fundamental concepts that arise in var- ious contexts, including computer algorithms. We study basic counting problems in terms of these concepts. Sorting. A common computational task is to rearrange elements in order. Given a linear arrayA1..n of integers, rearrange them such thatAi≤Ai+1 for1≤in. fori = 1ton−1do Figure 1: The number of squares in the grid is twice the sum forj =i+1downto2do from 1 to8. ifAjAj−1then aux =Aj;Aj =Aj−1;Aj =aux Sets. A set is an unordered collection of distinct ele- endif ments. The union of two sets is the set of elements that endfor are in one set or the other, that is, A∪ B = x x ∈ endfor. A orx∈ B. The intersection of the same two sets is the We wish to count the number of comparisons made in this set of elements that are in both, that is, A∩ B = x algorithm. For example, sorting an array of five elements x ∈ A andx ∈ B. We say that A andB are disjoint if uses 15 comparisons. In general, we make 1+2+···+ A∩B =∅. The difference is the set of elements that be- P n−1 (n−1) = i comparisons. long to the first but not to the second set, that is,A−B = i=1 x x ∈ A andx6∈ B. The symmetric difference is the set of elements that belong to exactly one of the two sets, Sums. We now derive a closed form for the above sum that is,A⊕B = (A−B)∪(B−A) = (A∪B)−(A∩B). by adding it to itself. Arranging the second sum in reverse Look at Figure 2 for a visual description of the sets that order and adding the terms in pairs, we get 1+(n−1)+...+(n−1)+1 = n(n−1). Since each number of the original sum is added twice, we divide by two to obtain n−1 X n(n−1) i = . 2 i=1 As with many mathematical proofs, this is not the only Figure 2: From left to right: the union, the intersection, the dif- way to derive this sum. We can think of the sum as two ference, and the symmetric difference of two sets represented as sets of stairs that stack together, as in Figure 1. At the base, disks in the plane. we haven−1 gray blocks and one white block. At each level, one more block changes from gray to white, until result from the four types of operations. The number of we have one gray block andn−1 white blocks. Together, elements in a set A is denoted asA. It is referred to as the stairs form a rectangle divided inton−1 byn squares, the size or the cardinality ofA. The number of elements with exactly half the squares gray and the other half white. P n n(n−1) in the union of two sets cannot be larger than the sum of Thus, i = , same as before. Notice that this i=1 2 the two sizes. sum can appear in other forms, for example, n−1 X SUM PRINCIPLE 1. A∪B≤A+B with equality i = 1+2+...+(n−1) ifA andB are disjoint. i=1 = (n−1)+(n−2)+...+1 To generalize this observation to more than two sets, we n−1 X call the setsS ,S ,...,S a covering ofS = S ∪S ∪ 1 2 m 1 2 = (n−i). ...∪S . IfS ∩S =∅ for alli6= j, then the covering m i j i=1 5is called a partition. To simplify the notation, we write We can also encode each multiplication by a triplet of inte- S m S =S ∪S ∪···∪S . gers, the row number inA, the column number inA which i 1 2 m i=1 is also the row number inB, and the column number inB. There arep possibilities for the first number,q for the sec- SUM PRINCIPLE 2. Let S ,S ,...,S be a covering 1 2 m P m ond, andr for the third number. We generalize this method of S. Then, S ≤ S , with equality if the cov- i i=1 as follows. ering is a partition. PRODUCT PRINCIPLE 2. If S is a set of lists of length Matrix multiplication. Another common computa- m withi possibilities for positionj, for1≤j ≤m, then j Q tional task is the multiplication of two matrices. As- m S =i ·i ·...·i = i . 1 2 m j j=1 suming the first matrix is stored in a two-dimensional array A1..p,1..q and the second matrix is stored in We can use this rule to count the number of cartoon char- B1..q,1..r, we match up rows of A with the columns acters that can be created from a book giving choices for ofB and form the sum of products of corresponding ele- head, body, and feet. If there arep choices for the head,q ments. For example, multiplying choices for the body, andr choices for the legs, then there   arepqr different cartoon characters we can create. 1 3 2 A = 0 2 4 Number of passwords. We apply these principles to with count the passwords that satisfy some conditions. Sup-   0 2 3 pose a valid password consists of eight characters, each   B = 1 2 5 a digit or a letter, and there must be at least two digits. 4 0 1 To count the number of valid passwords, we first count the number of eight character passwords without the digit con- results in 8 8 straint: (26+10) = 36 . Now, we subtract the number of   passwords that fail to meet the digit constraint, namely the 11 8 20 C = . 8 passwords with one or no digit. There are 26 passwords 18 4 14 without any digits. To count the passwords with exactly 7 The algorithm we use to getC fromA andB is described one digit, we note that there are 26 ways to choose an in the following pseudo-code. ordered set of 7 letters, 10 ways to choose one digit, and8 places to put the digit in the list of letters. Therefore, there 7 fori = 1topdo are 26 ·10·8 passwords with only one digit. Thus, there 8 8 7 forj = 1tordo are 36 −26 −26 ·10·8 valid passwords. Ci,j = 0; fork = 1toqdo Lists. A list is an ordered collection of elements which Ci,j =Ci,j+Ai,k·Bk,j are not necessarily different from each other. We note two endfor differences between lists and sets: endfor endfor. (1) a list is ordered, but a set is not; We are interested in counting how many multiplications (2) a list can have repeated elements, but a set can not. the algorithm takes. In the example, each entry of the re- sult uses three multiplications. Since there are six entries Lists can be expressed in terms of another mathematical in C, there are a total of 6· 3 = 18 multiplications. In concept in which we map elements of one set to elements general, there are q multiplications for each of pr entries of another set. A functionf from a domainD to a range of the result. Thus, there are pqr multiplications in total. R, denoted asf :D→R, associates exactly one element We state this observation in terms of sets. in R to each element x ∈ D. A list of k elements is a function1,2,...,k→R. For example, the function in S m PRODUCT PRINCIPLE 1. Let S = S . If the sets Figure 3 corresponds to the list a,b,c,b,z,1,3,3. We can i i=1 S ,S ,...,S form a partition and S = n for each use the Product Principle 2 to count the number of differ- 1 2 m i 1≤i≤m thenS =nm. ent functions from a finite domain,D, to a finite range,R. 61 a 2 b 3 c 4 d 5 1 6 2 7 3 8 z f D R Figure 3: A function representing a list. Specifically, we have a list of lengthD withR possi- bilities for each position. Hence, the number of different D functions fromD toR isR . Bijections. The functionf :D→R is injective or one- to-one if f(x) = 6 f(y) for all x = 6 y. It is surjective or onto if for every r ∈ R, there exists some x ∈ D with f(x) =r. The function is bijective or a one-to-one corre- spondence if it is both injective and surjective. BIJECTION PRINCIPLE. Two sets D and R have the same size if and only if there exists a bijectionf :D→R. Thus, asking how many bijections there are from D toR only makes sense if they have the same size. Suppose this size is finite, that is,D =R =n. Then being injective is the same as being bijective. To count the number of bijections, we assign elements of R to elements of D, in sequence. We have n choices for the first element in the domain,n−1 choices for the second,n−2 for the third, and so on. Hence the number of different bijections from D toR isn·(n−1)·...·1 =n. Summary. Today, we began with the building blocks of counting: sets and lists. We went through some examples using the sum and product principles: counting the num- ber of times a loop is executed, the number of possible passwords, and the number of combinations. Finally, we talked about functions and bijections. 70 1 2 3 4 5 2 Binomial Coefficients 0 1 1 1 1 In this section, we focus on counting the number of ways 2 1 2 1 sets and lists can be chosen from a given set. 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 Permutations. A permutation is a bijection from a finite setD to itself,f :D→D. For example, the permutations By studying this table, we notice several patterns. of 1,2,3 are: 123,132,213,231,312, and 321. Here we list the permutations in lexicographic order, same as  n • = 1. In words, there is exactly one way to choose 0 they would appear in a dictionary. Assuming D = k, no item from a list ofn items. there arek permutations or, equivalently, orderings of the  n • = 1. In words, there is exactly one way to choose set. To see this, we note that there are k choices for the n alln items from a list ofn items. first element, k−1 choices for the second,k− 2 for the   n n third, and so on. The total number of choices is therefore • Each row is symmetric, that is, = . k n−k k(k−1)·...·1, which is the definition ofk. This table is also known as Pascal’s Triangle. If we draw Let N = 1,2,...,n. For k ≤ n, a k-element per- it symmetric between left and right then we see that each mutation is an injection 1,2,...,k → N. In other entry in the triangle is the sum of the two entries above it words, a k-element permutation is a list of k distinct el- in the previous row. ements fromN. For example, the3-element permutations of1,2,3,4 are 1 1 1 123, 124, 132, 134, 142, 143, 1 2 1 213, 214, 231, 234, 241, 243, 1 3 3 1 312, 314, 321, 324, 341, 342, 1 4 6 4 1 412, 413, 421, 423, 431, 432. 1 5 10 10 5 1 There are 24 permutations in this list. There are six or- derings of the subset 1,2,3 in this list. In fact, each Pascal’s Relation. We express the above recipe of con- k 3-element subset occurs six times. In general, we writen structing an entry as the sum of two previous entries more  for the number ofk-element permutations of a set of size n formally. For convenience, we define = 0 whenever k n. We have k 0,n 0, ornk. k−1 Y k    n = (n−i) n n−1 n−1 PASCAL’S RELATION. = + . k k−1 k i=0 = n(n−1)···(n−(k−1)) PROOF. We give two arguments for this identity. The first n works by algebraic manipulations. We get = .   (n−k) n (n−k)(n−1)+k(n−1) = k (n−k)k  n Subsets. The binomial coefficient , pronounced n (n−1) (n−1) k = + choose k, is by definition the number of k-element sub- (n−k−1)k (n−k)(k−1) sets of a sizen set. Since there are k ways to order a set      n−1 n−1 k n of sizek, we know thatn = ·k which implies = + . k k k−1   n n = . For the second argument, we partition the sets. LetS =  k (n−k)k n n and leta be an arbitrary but fixed element from S. k  n We fill out the following tables with values of , where counts the number of k-element subsets of S. To get the k the row index is the values of n and the column index is number of subsets that contain a, we count the (k− 1)-  n the value of k. Values of for k n are all zero and element subsets ofS−a, and to get the number of sub- k are omitted from the table. sets that do not containa, we count thek-element subsets 8   P 3 2 n n−1 n−1 2 n n n ofS−a. The former is and the latter is . COROLLARY 3. i = + + . i=1 k−1 k 3 2 6 Since the subsets that containa are different from the sub- sets that do not contain a, we can use the Sum Principle PROOF. We first express the summands in terms of bino- 1 to get the number of k-element subsets of S equal to mial coefficients and then use Corollary 2 to get the result.   n−1 n−1 + , as required. k−1 k n n n X X 2 X i −i 2 i = 2 + i 2 Binomials. We use binomial coefficients to find a for- i=1 i=1 i=1     n n n mula for(x+y) . First, let us look at an example. X X i i = 2 + 2 2 1 (x+y) = (x+y)(x+y) i=1 i=1     = xx+yx+xy +yy n+1 n+1 = 2 + 2 2 3 2 = x +2xy +y . 2(n+1)n(n−1) (n+1)n Notice that the coefficients in the last line are the same = + 1·2·3 1·2 as in the second line of Pascal’s Triangle. This is more 3 2 n −n n +n generally the case and known as the = + . 3 2  P n n n n−i i BINOMIAL THEOREM. (x+y) = x y . i=0 i This implies the claimed identity. PROOF. If we write each term of the result before combin-  n ing like terms, we list every possible way to select onex or Summary. The binomial coefficient, , counts the dif- k n−i i oney from each factor. Thus, the coefficient ofx y is ferent ways we can choosek elements from a set ofn. We   n n n equal to = . In words, it is the number of ways saw how it can be used to compute (x +y) . We proved n−i i we can selectn−i factors to bex and have the remaining several corollaries and saw that describing the identities i factors to bey. This is equivalent to selectingi factors to as counting problems can lead us to different, sometimes bey and have the remaining factors bex. simpler proofs. Corollaries. The Binomial Theorem can be used to de- rive a number of other interesting sums. We prove three such consequences. P  n n n COROLLARY 1. = 2 . i=0 i PROOF. Letx = y = 1. Then, by the Binomial Theorem we have   n X n n n−i i (1+1) = 1 1 . i i=0 This implies the claimed identity.   P n j n+1 COROLLARY 2. = . j=k k k+1 PROOF. We use Pascal’s Relation to prove this identity. It is instructive to trace our steps graphically, in the triangle    n+1 n n above. In a first step, we replace by and . k+1 k k+1  n Keeping the first term, we replace the second, , by k+1   n−1 n−1 and . Repeating this operation, we finally re- k k+1    k+1 k k place by = 1 and = 0. In other words, k+1 k k+1   n+1 j is equal to the sum of the forj running fromn k+1 k down tok. 93 Equivalence Relations Equivalence relations. We now formalize the above method of counting. A relation on a set S is a collec- tionR of ordered pairs, (x,y). We writex∼y if the pair Equivalence relations are a way to partition a set into sub- (x,y) is inR. We say that a relation is sets of equivalent elements. Being equivalent is then in- terpreted as being the same, such as different views of the • reflexive ifx∼x for allx∈S; same object or different ordering of the same elements, etc. By counting the equivalence classes, we are able to • symmetric ifx∼y impliesy∼x; count the items in the set that are different in an essential • transitive ifx∼y andy∼z implyx∼z. way. We say that the relation is an equivalence relation ifR is reflexive, symmetric, and transitive. IfS is a set andR an Labeling. To begin, we ask how many ways are there equivalence relation onS, then the equivalence class of an to label three of five elements red and the remaining two elementx∈S is elements blue? Without loss of generality, we can call our elementsA,B,C,D,E. A labeling is an function that x = y∈S y∼x. associates a color to each element. Suppose we look at We note here that if x ∼ y then x = y. In the above a permutation of the five elements and agree to color the labeling example,S is the set of permutations of the ele- first three red and the last two blue. Then the permutation mentsA,B,C,D,E and two permutations are equivalent ABDCE would correspond to coloring A,B,D red and if they give the same labeling. Recalling that we color the C,E blue. However, we get the same labeling with other first three elements red and the last two blue, the equiva- permutations, namely lence classes are ABC;DE, ABD;CE, ABE;CD, ACD;BE, ACE;BD, ADE;BC, BCD;AE, ABD;CE BAD;CE DAB;CE BCE;AD, BDE;AC, CDE;AB. ABD;EC BAD;EC DAB;EC ADB;CE BDA;CE DBA;CE Not all relations are equivalence relations. Indeed, there ADB;EC BDA;EC DBA;EC . are relations that have none of the above three properties. There are also relations that satisfy any subset of the three Indeed, we have 32 = 12 permutations that give the properties but none of the rest. same labeling, simply because there are 3 ways to or- der the red elements and 2 ways to order the blue ele- ments. Similarly, every other labeling corresponds to 12 An example: modular arithmetic. We say an integera permutations. In total, we have 5 = 120 permutations is congruent to another integerb modulo a positive integer of five elements. The set of 120 permutations can thus be n, denoted asa =b modn, ifb−a is an integer multiple 120 partitioned into = 10 blocks such that any two per- ofn. To illustrate this definition, letn = 3 and letS be the 12 mutations in the same block give the same labeling. Any set of integers from 0 to 11. Thenx = y mod 3 ifx and two permutations from different blocks give different la- y both belong toS =0,3,6,9 or both belong toS = 0 1 belings, which implies that the number of different label- 1,4,7,10 or both belong to S = 2,5,8,11. This 2 ings is 10. More generally, the number of ways we can can be easily verified by testing each pair. Congruence label k of n elements red and the remaining n− k ele- modulo 3 is in fact an equivalence relation on S. To see  n n ments blue is = . This is also the number of this, we show that congruence modulo3 satisfies the three k(n−k) k k-element subsets of a set ofn elements. required properties. Now suppose we have three labels, red, green, and blue. reflexive. Sincex−x = 0·3, we know thatx =x mod 3. We count the number of different labelings by dividing symmetric. If x = y mod 3 then x and y belong to the the total number of orderings by the orderings within in same subsetS . Hence,y =x mod 3. i the color classes. There are n permutations of the n el- ements. We want i elements red, j elements blue, and transitive. Letx = y mod 3 andy = z mod 3. Hencex k = n−i−j elements green. We agree that a permuta- andy belong to the same subset S and so doy and i tion corresponding to the labeling we get by coloring the z. It follows thatx andz belong to the same subset. firsti elements red, the nextj elements blue, and the lastk elements green. The number of repeated labelings is thus More generally, congruence modulo n is an equivalence n i timesj timesk and we have different labelings. relation on the integers. ijk 10Block decomposition. An equivalence class of elements For example, letn = 3. Then, we havep+q +r = k. is sometimes called a block. The importance of equiva- The choices forp are from 0 to k. Once p is chosen, the lence relations is based on the fact that the blocks partition choices forq are fewer, namely from 0 tok−p. Finally, the set. if p and q are chosen then r is determined, namely r = k−p−q. The number of ways to write k as a sum of three non-negative integers is therefore THEOREM. Let R be an equivalence relation on some setS. Then the blocksS =y ∈ S x∼ y,y ∈ S for x k k−i k XX X allx∈S partitionS. 1 = (k−p+1) p=0q=0 p=0 S PROOF. In order to prove that S = S, we need to x x k+1 S S X show two things, namely S ⊆ S and S ⊇ x x x∈S x∈S = p S. EachS is a subset ofS which implies the first inclu- x p=1   sion. Furthermore, each x ∈ S belongs to S which im- x k +2 plies the second inclusion. Additionally, ifS = 6 S , then = . x y 2 S ∩S = ∅ sincez ∈ S implies z ∼ x, which means x y x thatS =S , which means thatS = 6 S . Therefore,z is x z z y There is another (simpler) way of finding this solution. not related toy, and soz6∈S . y Suppose we line up ourn books, then placek−1 dividers between them. The number of books between thei-th and Symmetrically, a partition of S defines an equivalence the (i−1)-st dividers is equal to the number of books on relation. If the blocks are all of the same size then it is thei-th shelf; see Figure 4. We thus haven +k− 1 ob- easy to count them. jects,k books plusn−1 dividers. The number of ways to QUOTIENT PRINCIPLE. If a setS of sizep can be parti- tioned intoq classes of sizer each, thenp =qr or, equiv- p alently,q = . r Multisets. The difference between a set and a multiset is that the latter may contain the same element multiple Figure 4: The above arrangement of books and blocks represents times. In other words, a multiset is an unordered collec- two books placed on the first and last shelves, and one book on tion of elements, possibly with repetitions. We can list the the second shelf. As a sum, this figure represents 2+1+0+2. repetitions,  hhc,o,l,o,rii n+k−1 choosen−1 dividers fromn+k−1 objects is . n−1 or we can specify the multiplicities, We can easily see that this formula agrees with the result we found forn = 3. m(c) = 1,m(o) = 2,m(r) = 1. The size of a multiset is the sum of the multiplicities. We Summary. We defined relations and equivalence rela- show how to count multisets by considering an example, tions, investigating several examples of both. In partic- the ways to distributek (identical) books amongn (differ- ular, modular arithmetic creates equivalence classes of the ent) shelves. The number of ways is equal to integers. Finally, we looked at multisets, and saw that counting the number of size-k multisets of n elements is • the number of size-k multisets of then shelves; equal to the number of ways to writek as a sum ofn non- negative integers. • the number of ways to write k as a sum of n non- negative integers. We count the ways to writek as a sum ofn non-negative integers as follows. Choose the first integer of the sum to be p. Now we have reduced the problem to counting the ways to writek−p as the sum ofn−1 non-negative integers. For small values ofn, we can do this. 11First Homework Assignment Write the solution to each question on a single page. The deadline for handing in solutions is January 26. Question 1. (20 = 10+10 points). Ifn basketball teams play each other team exactly once, how many games will be played in total? If the teams then compete in a single elimination tournament (similar to March Madness), how many additional games are played? Question 2. (20 = 10+10 points). (a) (Problem 1.2-7 in our textbook). Let D = R = n. Show that the following statement is true: The functionf :D→R is surjective if and only iff is injective. (b) Is the functionf : R → R defined byf(x) = 3x+2 a bijection? Prove or give a counterex- ample. Question 3. (20 = 6+7+7 points). 8 (a) What is the coefficient of the x term of (x− 30 2) ? i j k (b) What is the coefficient of the x y z term of n (x+y +z) ?   n n (c) Show that = . k n−k Question 4. (20 = 6+7+7 points). For (a) and (b), prove or disprove that the relations given are equivalence relations. For (c), be sure to justify your answer. (a) Choose some k ∈ Z. Let x,y ∈ Z. We say x∼y ifx≡y mod k. (b) Let x,y be positive integers. We say x ∼ y if the greatest common factor ofx andy is greater than1. (c) How many ways can you distributek identical cookies ton children? 12II NUMBER THEORY We use the need to send secret messages as the motivation to study questions in number theory. The main tool for this purpose is modular integer arithmetic. 4 Modular Arithmetic 5 Inverses 6 Euclid’s Algorithm 7 RSA Cryptosystem Homework Assignments 134 Modular Arithmetic sound contradictory since everybody knowsP andS is A A just its inverse, but it turns out that there are pairs of func- tions that satisfy this requirement. Now, if Alice wants to We begin the chapter on number theory by introducing send a message to Bob, she proceeds as follows: modular integer arithmetic. One of its uses is in the en- cryption of secret messages. In this section, all numbers 1. Alice gets Bob’s public key,P . B are integers. 2. Alice applies it to encrypt her message,y =P (x). B 3. Alice sendsy to Bob, publically. Private key cryptography. The problem of sending se- 4. Bob appliesS (y) =S (P (x)) =x. B B B cret messages is perhaps as old as humanity or older. We have a sender who attempts to encrypt a message in such a We note that Alice does not need to know Bob’s secret way that the intended receiver is able to decipher it but any key to encrypt her message and she does not need secret possible adversary is not. Following the traditional proto- channels to transmit her encrypted message. col, the sender and receiver agree on a secret code ahead of time, and they use it to both encrypt and decipher the message. The weakness of the method is the secret code, Arithmetic modulo n. We begin by defining what it which may be stolen or cracked. means to take one integer,m, modulo another integer,n. As an example, consider Ceasar’s cipher, which con- sists of shifting the alphabet by some fixed number of po- DEFINITION. Letting n ≤ 1, m modn is the smallest sitions, e.g., integerr≥ 0 such thatm =nq +r for some integerq. A B C ... V W X Y Z Given m and n ≥ 1, it is not difficult to see that q and ↓ ↓ ↓ ... ↓ ↓ ↓ ↓ ↓ r exist. Indeed, n partitions the integers into intervals of E F G ... Z A B C D. lengthn: If we encode the letters as integers, this is the same as ...,−n,...,0,...,n,...,2n,... adding a fixed integer but then subtracting 26, the number The numberm lies in exactly one of these intervals. More of letters, if the sum exceeds this number. We consider precisely, there is an integerq such thatqn≤ m ((q + this kind of integer arithmetic more generally. 1)n. The integerr is the amount by whichm exceedsqn, that is,r =m−qn. We see thatq andr are unique, which Public key cryptography. Today, we use more power- is known as ful encryption methods that give a more flexible way to transmit secret information. We call this public key cryp- EUCLID’S DIVISION THEOREM. Letting n ≥ 1, for tography which roughly works as follows. As before, we everym there are unique integers q and 0 ≤ r n such have a sender, called Alice, and a receiver, called Bob. thatm =nq +r. Both Alice and Bob have a public key, KP and KP , A B which they publish for everyone to see, and a secret key, Computations. It is useful to know that modulos can KS andKS , which is only known to themselves. They A B be taken anywhere in the calculation if it involves only do not exchange the secret key even among each other. addition and multiplication. We state this more formally. The keys are used to change messages so we can think of them as functions. The function that corresponds to the LEMMA 1. Lettingn≥ 1,i modn = (i+kn) modn. public and the secret keys are inverses of each other, that is, This should be obvious because addingk times n moves the integer i to the right by k intervals but maintains its S (P (x)) = P (S (x)) = x; A A A A relative position within the interval. S (P (x)) = P (S (x)) = x. B B B B LEMMA 2. Lettingn≥ 1, we have The crucial point is thatP is easy to compute for every- A body andS is easy to compute for Alice but difficult for A (i+j) modn = (i modn)+(j modn) modn; everybody else, including Bob. Symmetrically,P is easy B (i·j) modn = (i modn)·(j modn) modn. for everybody but S is easy only for Bob. Perhaps this B 14PROOF. By Euclid’s Division Theorem, there are unique • multiplication distributes over addition, that is, i· n integersq ,q and0≤r ,r n such that (j + k) = (i· j)+ (i· k) for alli,j,k∈Z . i j i j n n n n n i = q n+r ; i i These are the eight defining properties of a commutative j = q n+r . j j ring. Had we also a multiplicative inverse for every non- zero element then the structure would be called a field. Plugging this into the left hand side of the first equation, Hence,(Z ,+ ,· ) is a commutative ring. We will see in n n n we get the next section that it is a field ifn is a prime number. (i+j) modn = (q +q )n+(r +r ) modn i j i j = (r +r ) modn i j Addition and multiplication modulo n. We may be = (i modn)+(j modn) modn. tempted to use modular arithmetic for the purpose of trans- mitting secret messages. As a first step, the message is in- Similarly, it is easy to show that (ij) modn = terpreted as an integer, possibly a very long integer. For (r r ) modn, which implies the second equation. i j example, we may write each letter in ASCII and read the bit pattern as a number. Then we concatenate the numbers. Now suppose Alice and Bob agree on two integers,n≥ 1 Algebraic structures. Before we continue, we intro- anda, and they exchange messages using duce some notation. LetZ =0,1,...,n−1 and write n + for addition modulo n. More formally, we have an n P(x) = x+ a; n operation that maps two numbers,i∈Z andj ∈Z , to n n S(y) = y + (−a) = y− a. their sum,i+ j = (i+j) modn. This operation satisfies n n n the following four properties: This works fine but not as a public key cryptography sys- tem. Knowing thatP is the same as addinga modulon, • it is associative, that is,(i+ j)+ k =i+ (j+ k) n n n n it is easy to determine its inverse, S. Alternatively, let us for alli,j,k∈Z ; n use multiplication instead of addition, • 0∈Z is the neutral element, that is, 0+ i = i for n n alli∈Z ; n P(x) = x· a; n ′ • everyi ∈Z has an inverse elementi , that is, i+ n n S(y) = y· (−a) = y : a. n n ′ i = 0; The trouble now is that division modulo n is not as • it is commutative, that is, i + j = j + i for all n n straightforward an operation as for integers. Indeed, if i,j ∈Z . n n = 12 and a = 4, we have 0· 4 = 3· 4 = 6· 4 = 9· 4 = 0 modn. Since multiplication with 4 is not in- The first three are the defining property of a group, and if jective, the inverse operation is not well defined. Indeed, the fourth property is also satisfied we have a commutative 0 : 4 could be0,3,6, or9. n or Abelian group. Thus, (Z ,+ ) is an Abelian group. n n We have another operation mappingi andj to their prod- uct,i· j = (ij) modn. This operation has a similar list n Summary. We learned about private and public key of properties: cryptography, ways to to send a secret message from a sender to a receiver. We also made first steps into number • it is associative, that is,(i· j)· k =i· (j· k) for n n n n theory, introducing modulo arithmetic and Euclid’s Divi- alli,j,k∈Z ; n sion Theorem. We have seem that addition and multiplica- • 1 ∈Z is the neutral element, that is, 1· i = i for n n tion modulon are both commutative and associative, and alli∈Z ; n that multiplication distributes over addition, same as in or- dinary integer arithmetic. • it is commutative, that is,i· j = j· i for alli,j ∈ n n Z . n Under some circumstances, we also have inverse elements but not in general. Hence, (Z ,· ) is generally not a n n group. Considering the interaction of the two operations, we note that 15′ ′ ′′ ′ 5 Inverses the right and geta· (a· a ) =a · (a· a ) and therefore n n n n ′ ′′ a =a . Ifa has a multiplicative inverse, we can use it to solve a linear equation. Multiplying with the inverse from In this section, we study under which conditions there is a the left and using associativity, we get multiplicative inverse in modular arithmetic. Specifically, we consider the following four statements. a· x = b; n ′ ′ (a · a)· x = a · b; n n n I. The integera has a multiplicative inverse inZ . n ′ x = a · b. n II. The linear equationa· x =b has a solution inZ . n n Since the multiplicative inverse is unique, so is the solu- III. The linear equationax+ny = 1 has a solution in the ′ tionx = a · b to the linear equation. We thus proved a n integers. little bit more than I =⇒ II, namely also the uniqueness IV. The integersa andn are relative prime. of the solution. We will see that all four statements are equivalent, and ′ A. If a has a multiplicative inverse a in Z then for n we will prove all necessary implications to establish this, every b ∈ Z , the equation a· x = b has the unique n n except for one, which we will prove in the next section. ′ solutionx =a · b. n Every implication has an equivalent contrapositive form. Examples. Before starting the proofs, we compute mul- For a statement I =⇒ II this form is¬II =⇒¬I. We state tiplicative inverses for a few values of n anda; see Table the contrapositive form in this particular instance. 1. Except fora = 0, all values ofa have multiplicative in- n = 2 a 0 1 A’. Ifa· x = b has no solution inZ thena does not n n ′ a 1 have a multiplicative inverse. n = 3 a 0 1 2 ′ a 1 2 To prove A’ we just need to assume that it is false, that is, n = 4 a 0 1 2 3 that¬II and I both hold. But if we have I then we also have ′ a 1 3 II. Now we have¬II as well as II. But this is a contradic- n = 5 a 0 1 2 3 4 ′ tion with they cannot both be true. What we have seen a 1 2 3 4 here is a very simple version of a proof by contradiction. n = 6 a 0 1 2 3 4 5 ′ a 1 5 More complicated versions will follow later. n = 7 a 0 1 2 3 4 5 6 ′ By setting b = 1, we get x = a as a solution to ′ a 1 4 5 2 3 6 ′ ′ a· x = 1. In other words,a · a =a· a = 1. Hence, n n n n = 8 a 0 1 2 3 4 5 6 7 ′ II =⇒ I. This particuar implication is called the converse a 1 3 5 7 of I =⇒ II, which should not be confused with the contra- n = 9 a 0 1 2 3 4 5 6 7 8 ′ a 1 5 7 2 4 8 positive. The converse is a new, different statement, while the contrapositive is logically eqivalent to the original im- ′ Table 1: Values ofn for whicha has a multiplicative inversea . plication, no matter what the specifics of the implication Black entries indicate the inverse does not exist. are. verses ifn = 2,3,5,7 but not ifn = 4,6,8,9. In the latter case, we have multiplicative inverses for some values ofa Linear equations in two variables. Here we prove but not for all. We will later find out that the characterizing II ⇐⇒ III. Recall that a · x = 1 is equivalent to n condition for the existence of the multiplicative inverse is ax modn = 1. Writingax =qn+r with0≤r n, we thatn anda have no non-trivial common divisor. see thatax modn = 1 is equivalent to the existence of an integerq such thatax =qn+1. Writingy =−q we get Linear equations modulo n. Here we prove I ⇐⇒ II. ax+ny = 1. The multiplicative inverse of an integera∈Z is another n ′ ′ ′ All steps in the above derivation are reversible. Hence, we integer a ∈ Z such that a · a = a· a = 1. We n n n proved that II is equivalent to III. We state the specific note that the multiplicative inverse is unique, if it exists. ′′ ′ result. Indeed, ifa · a = 1 then we can multiply witha from n 16B. The equationa· x =b has a solution inZ iff there n n exist integersx andy such thatax+ny = 1. Implications are transitive, that is, if I implies II and II implies III then I implies III. We can do the same chain of implications in the other direction as well. Hence, if I⇐⇒ II and II⇐⇒ III, as we have established above, we also have I⇐⇒ III. We again state this specific result for clarity. C. The integer a has a multiplicative inverse inZ iff n there exist integersx andy such thatax+ny = 1. Greatest common divisors. Here we prove III =⇒ IV. We will prove IV =⇒ III later. We say an integeri factors another integer j if j/i is an integer. Furthermore, j is a prime number if its only factors are ±j and ±1. The greatest common divisor of two integersj andk, denoted asgcd(j,k), is the largest integerd that is a factor of both. We sayj andk and relative prime if gcd(j,k) = 1. D. Given integersa andn, if there exist integersx and y such thatax+ny = 1 thengcd(a,n) = 1. PROOF. Suppose gcd(a,n) = k. Then we can writea = ik andn =jk. Substituting these into the linear equation gives 1 = ax+ny = k(ix+jy). But then k is a factor of 1 and therefore k = ±1. This implies that the only common factors of a and n are ±1 and thereforegcd(a,n) = 1. Summary. We have proved relationships between the statements I, II, III, IV; see Figure 5. We will see later that I C D A III IV B II Figure 5: Equivalences between statements. the implication proved by D can also be reversed. Thus computing the greatest common divisor gives a test for the existence of a multiplicative inverse. 176 Euclid’s Algorithm that after a finite number of iterations the algorithm halts withr = 0. In other words, the algorithm terminates after a finite number of steps, which is something one should In this section, we present Euclid’s algorithm for the great- always check, in particular for recursive algorithms. est common divisor of two integers. An extended version of this algorithm will furnish the one implication that is missing in Figure 5. Last implication. We modify the algorithm so it also returns the integersx andy for whichgcd(j,k) =jx+ky. This provides the missing implication in Figure 5. Reduction. An important insight is Euclid’s Division Theorem stated in Section 4. We use it to prove a relation- D’. Ifgcd(a,n) = 1 then the linear equationax+ny = ship between the greatest common divisors of numbers j 1 has a solution. andk when we replacek by its remainder moduloj. This finally verifies that the gcd is a test for the existence LEMMA. Let j,k,q,r 0 with k = jq + r. Then of a multiplicative inverse in modular arithmetic. More gcd(j,k) = gcd(r,j). specifically,x modn is the multiplicative inverse ofa in Z . Do you see why? We can thus update the relationship n PROOF. We begin by showing that every common factor between the statements I, II, III, IV listed at the beginning ofj andk is also a factor ofr. Lettingd = gcd(j,k) and of Section 5; see Figure 6. writingj =Jd andk =Kd, we get I r = k−jq = (K−Jq)d. C We see that r can be written as a multiple of d, so d is D, D’ A III IV indeed a factor of r. Next, we show that every common factor ofr andj is also a factor ofk. Lettingd = gcd(r,j) and writingr =Rd andj =Jd, we get B II k = jq +r = (Jq +R)d. Figure 6: Equivalences between the statements listed at the be- Hence,d is indeed a factor ofk. But this implies thatd is ginning of Section 5. a common factor ofj andk iff it is a common factor ofr andj. Extended gcd algorithm. Ifr = 0 then the above algo- Euclid’s gcd algorithm. We use the Lemma to compute rithm returns j as the gcd. In the extended algorithm, we the greatest common divisor of positive integers j andk. also returnx = 1 andy = 0. Now supposer 0. In this The algorithm is recursive and reduces the integers until case, we recurse and get the remainder vanishes. It is convenient to assume that ′ ′ gcd(r,j) = rx +jy both integers,j andk, are positive and thatj ≤k. ′ ′ = (k−jq)x +jy integer GCD(j,k) ′ ′ ′ = j(y −qx )+kx. q =k div j; r =k−jq; ′ ′ ifr = 0thenreturnj We thus returng = gcd(r,j) as well asx =y −qx and ′ elsereturn GCD(r,j) y = x . As before, we assume 0 j ≤ k when we call endif. the algorithm. 3 If we call the algorithm forj k then the first recursive integer XGCD(j,k) call is fork andj, that is, it reverses the order of the two q =k div j; r =k−jq; integers and keeps them ordered as assumed from then on. ifr = 0thenreturn(j,1,0) ′ ′ Note also that r j. In words, the first parameter, j, else(g,x,y ) = XGCD(r,j); ′ ′ ′ shrinks in each iterations. There are only a finite num- return(g,y −qx,x ) ber of non-negative integers smaller thanj which implies endif. 18To illustrate the algorithm, we run it for j = 14 and to different pairs of remainders. The generalization of this k = 24. The values of j,k,q,r,g = gcd(j,k),x,y at insight to relative prime numbersm andn is known as the the various levels of recursion are given in Table 2. j k q r g x y CHINESE REMAINDER THEOREM. Let m,n 0 be 14 24 1 10 2 -5 3 relative prime. Then for every a ∈ Z and b ∈ Z , the m n 10 14 1 4 2 3 -2 system of two linear equations 4 10 2 2 2 -2 1 2 4 2 0 2 1 0 x modm = a; x modn = b Table 2: Running the extended gcd algorithm on j = 14 and k = 24. has a unique solution inZ . mn There is a further generalization to more then two moduli Computing inverses. We have established that the inte- that are pairwise relative prime. The proof of this theorem gera has a multiplicative inverse inZ iff gcd(a,n) = 1. n works as suggested by the example, namely by showing Assumingn =p is a prime number, this is the case when- thatf :Z →Z ×Z defined by mn m n everap is positive. f(x) = (x modm,x modn) COROLLARY. Ifp is prime then every non-zeroa∈Z p is injective. Since bothZ andZ ×Z have sizemn, mn m n has a multiplicative inverse. this implies thatf is a bijection. Hence,(a,b)∈Z ×Z m n has a unique preimage, the solution of the two equations. It is straightforward to compute the multiplicative inverse To use this result, we would take two large integers, x using the extended gcd algorithm. As before, we assume andy, and represent them as pairs, (x modm,x modn) p is a prime number and 0ap. and (x modm,x modn). Arithmetic operations can then be done on the remainders. For example, x times integer INVERSE(a,p) y would be represented by the pair (g,x,y) = XGCD(a,p); assertg = 1; returnx modp. xy modm = (x modm)(y modm) modm; xy modn = (x modn)(y modn) modn. The assert statement makes sure that a and p are indeed relative prime, for else the multiplicative inverse would We would choose m and n small enough so that multi- not exist. We have seen that x can be negative so it is plying two remainders can be done using conventional, necessary to take x modulo p before we report it as the single-word integer multiplication. multiplicative inverse. Summary. We discussed Euclid’s algorithm for com- Multiple moduli. Sometimes, we deal with large inte- puting the greatest common divisor of two integers, and its gers, larger then the ones that fit into a single computer extended version which provides the missing implication word (usually 32 or 64 bits). In this situation, we have to in Figure 5. We have also learned the Chinese Remainder find a representation that spreads the integer over several Theorem which can be used to decompose large integers words. For example, we may represent an integerx by its into digestible junks. remainders modulo 3 and modulo 5, as shown in Table 3. We see that the first 15 non-negative integers correspond x 0 1 2 3 4 . . . 13 14 15 x mod 3 0 1 2 0 1 . . . 1 2 0 x mod 5 0 1 2 3 4 . . . 3 4 0 Table 3: Mapping the integers from0 to15 to pairs of remainders after dividing with 3 and with5. 19x a 0 1 2 3 4 5 6 7 RSA Cryptosystem 1 1 1 1 1 1 1 1 2 1 2 4 1 2 4 1 Addition and multiplication modulo n do not offer the 3 1 3 2 6 4 5 1 computational difficulties needed to build a viable cryp- 4 1 4 2 1 4 2 1 tographic system. We will see that exponentiation modulo 5 1 5 4 6 2 3 1 n does. 6 1 6 1 6 1 6 1 Table 5: Exponentiation modulon = 7. We writex from left to Operations as functions. Recall that + and · each n n right anda from top to bottom. read two integers and return a third integer. If we fix one of the two input integers, we get two functions. Specifically, fixing a ∈ Z , we have functions A : Z → Z and inZ . Hence, n n n p M :Z →Z defined by n n X = 1· 2· ...· (p−1) p p p A(x) = x+ a; n = (1· a)· (2· a)· ...· ((p−1)· a) p p p p p p p−1 M(x) = x· a; n = X· (a modp). p Multiplying with the inverse ofX givesa modp = 1. see Table 4. Clearly, A is injective for every choice of p−1 x 0 1 2 3 4 5 A(x) 2 3 4 5 0 1 One-way functions. The RSA cryptosystem is based on M(x) 0 2 4 0 2 4 the existence of one-way functionsf :Z →Z defined n n by the following three properties: Table 4: The functionA defined by addinga = 2 modulon = 6 is injective. In contrast, the function M defined by multiplying • f is easy to compute; witha = 2 is not injective. −1 • its inverse,f :Z →Z , exists; n n n 0 and a ∈ Z . On the other hand, M is injective n −1 • without extra information,f is hard to compute. iff gcd(a,n) = 1. In particular, M is injective for every non-zeroa∈Z ifn is prime. n The notions of ‘easy’ and ‘hard’ computation have to be made precise, but this is beyond the scope of this course. Roughly, it means that givenx, computingy =f(x) takes Exponentiation. Yet another function we may consider −1 on the order of a few seconds while computing f (y) is takinga to thex-th power. LetE :Z →Z be defined n n takes on the order of years. RSA uses the following recipe by to construct one-way functions: x E(x) = a modn 1. choose large primesp andq, and letn =pq; = a· a· ...· a, n n n 2. choosee = 6 1 relative prime to (p−1)(q−1) and let where we multiplyx copies ofa together. We see in Table d be its multiplicative inverse modulo(p−1)(q−1); 5 that for some values of a and n, the restriction of E to e 3. the one-way function is defined byf(x) =x modn the non-zero integers is injective and for others it is not. d and its inverse is defined byg(y) =y modn. Perhaps surprisingly, the last column of Table 5 consists of1s only. According to the RSA protocol, Bob publishese andn and keepsd private. To exchange a secret message,x∈Z , n FERMAT’S LITTLE THEOREM. Let p be prime. Then p−1 4. Alice computesy =f(x) and publishesy; a modp = 1 for every non-zeroa∈Z . p 5. Bob readsy and computesz =g(y). PROOF. Since p is prime, multiplication with a gives an injective function for every non-zero a ∈ Z . In other To show that RSA is secure, we would need to prove p words, multiplying witha permutes the non-zero integers that without knowingp,q,d, it is hard to computeg. We 20

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.