Number Theory and Cryptography

number theory and cryptography applications basic number theory in cryptography and network security, number theory and cryptography objective questions and answers
Dr.SamuelHunt Profile Pic
Dr.SamuelHunt,United Arab Emirates,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Arithmetic, Logic and Numbers With an Introduction to Cryptography Unit NT: Number Theory and Cryptography Edward A. Bender S. Gill Williamson cEdward A. Bender & S. Gill Williamson 2010. All rights reserved.Preface The material in this unit of study was, over several years, presented by the authors to lower division undergraduates in the Department of Mathematics and the Department of Computer Science and Engineering at the University of California, San Diego (UCSD). All material has been classroom tested by the authors and other faculty members at UCSD. The first course of a two quarter sequence was chosen from six units of study: Boolean Func- tions (Unit BF), Logic (Unit Lo), Number Theory and Cryptography (Unit NT), Sets and Functions (Unit SF), and Equivalence and Order (Unit EO), and Induction, Se- quences and Series (Unit IS). Thesecond course of the sequence was chosen fromfourunitsof study: Counting and Listing (Unit CL), Functions (Unit Fn), Decision Trees and Recursion (Unit DT), and Basic Concepts in Graph Theory (Unit GT). The order of presentation of units within the first six, as well as those within the second four, can be varied for students with a good high school background in mathematics. Discrete mathematics has become an essential tool in computer science, economics, biology, mathematics, chemistry, and engineering. Each area introduces its own special terms for shared concepts in discrete mathematics. The only way to keep from reinventing the wheel from area to area is to know the precise mathematical ideas behind the concepts being applied by these various fields. Our course material is dedicated to this task. At the end of each unit is a section of multiple choice questions: Multiple Choice Questions for Review. These questions should be read before reading the corresponding unit, and they should be referred to frequently as the units are read. We encouraged our students to be able to work these multiple choice questions and variations on them with ease and understanding. At the end of each section of the units are exercises that are suitable for written homework, exams, or class discussion. iiiivTable of Contents Unit NT: Number Theory and Cryptography Section 1: Basic Facts About Numbers........................................................NT-1 rationalnumbers,irrationalnumbers,prime,composite,odd,even,ndividesm,primefactor- ization, infinitely many primes, perfect squares, irrationality of integral square roots, residue classes mod d, mod as binary operator, mod as equivalence relation, modular arithmetic, modular addition, modular multiplication, floor function, ceiling function, diagonalization proofs Section 2: Cryptography and Secrecy........................................................NT-13 plaintext, ciphertext, key, espionage, greatest common divisor, least common multiple, Eu- clidean algorithm, Euler φ function, public key, symmetric encryption, discrete log problem, Diffie-Hellman algorithm, RSA algorithm Multiple Choice Questions for Review.......................................................NT-26 Notation Index..................................................................................NT-Index 1 Subject Index....................................................................................NT-Index 3 A star in the text () indicates more difficult and/or specialized material. vviUnit NT Number Theory and Cryptography Section 1: Basic Facts About Numbers Inthissection,weshalltakealookatsomeofthemostbasicpropertiesofZ,thesetofinte- gers. We look at properties related to parity (even, odd), prime factorization, irrationality of square roots, and modular arithmetic. First we recall some standard notation for sets of various basic types of numbers. • R denotes the real numbers, • Z denotes the integers, • Q denotes the rational numbers (ratios of integers), • N denotes the nonnegative integers (the “natural numbers”), + • N denotes the nonzero natural numbers (the positive integers), + • N denotes the set of natural numbers greater than or equal to 2. 2 Note thatR−Q is the set of irrational numbers. Example 1 (Odd and even integers) A basic subdivision ofZ is into the odd integers and the even integers. An element of Z is even if it is “of the form 2t,” where t ∈Z. An element of Z is odd if it is not even. The odd integers are all of the form 2t+1, where t∈Z. (This should be proved, but we will not do so.) The phrase “of the form 2t” can be written precisely as ∀n∈Z, (n is even) if and only if (∃t∈Z such that n=2t). The most elementary mathematical facts about odd and even integers concern the closure 1 properties. Here is the closure property for multiplication: The integers m and n are both odd if and only if mn is odd. (Equivalently, by negating both sides of “if and only if,” at least one the integers m or n is even if and only if mn is even. ) To show the “only if” part, suppose that if m and n are bothodd,saym= 2j+1andm =2k+1. Thenmn= 4jk+2j+2k+1= 2(2jk+j+k)+1 is of the form 2t+1 where t = 2jk+j +k. Thus, mn is odd. To show the “if” part, we use the inverse. Suppose that at least one of m or n is even. Without loss of generality, we may suppose that m is even, say m = 2j. Then mn = 2jn is of the form 2t where t = jn. Thus, mn is even. A similar statement for addition is that, for integers m and n, m+n is odd if and only if one of them is odd and the other is even. 1 A function on S×S has the closure property on S if its image is contained in S. Here S is the odd integers and the function is multiplication. NT-1Number Theory and Cryptography Fromtheclosurepropertyformultiplicationofoddintegers,youcanprovebyinduction k thatforanyk ≥1,andanyintegerm,m isoddifandonlyifmisodd. Logicallyequivalent k k is that m is even if and only if m is even. The fact that m is odd if m is odd can also be proved using the binomial theorem, which you should have seen in high school:   k X k k i k−i (x+y) = x y . i i=0 Sincem is odd,m= 2j+1 for some integerj. Letx =2j andy = 1. Writtenanotherway,       k k k k k 1 2 k m =(2j+1) = 1+(2j) +(2j) +···+(2j) . 1 2 k k In this form m is obviously 1 plus an even integer and hence odd. Prime Numbers and Factorization Most mathematicians would agree that the most important concept in number theory is the notion of a prime. Definition 1 (Prime and composite numbers) A natural numbern is prime if n≥2 and the only divisors of n are n and 1. We denote the set of prime numbers by P. An integer n≥ 2 that is not prime is composite. The number 2 is the smallest prime and the only even prime. The other primes less than 20 are 3, 5, 7, 11, 13, 17, 19. Example 2 (Prime factorization of any integer n≥2) Consider the integer 226512. It ends in 2 so it is divisible by 2. (We say that “n is divisible by m,” indicated by the notation mn, if n = qm for some integer q.) In fact, 226512/2= 113256. We can divide by 2 again, 113256/2 = 56628; and again, 56628/2 = 28314; and again, 38314/2 = 14157. 4 That’s it. We can’t divide by 2 anymore, so we have 226512= 2 ×14157. But, it is easy to check that 14157 is divisible by 3 to get 4719 which is again divisible by 3 to get 1573. 4 2 That’s it for dividing by 3, so we have 226512=2 ×3 ×1573. Continuingin this manner, 4 2 2 we end up with 226512 = 2 ×3 × 11 × 13. We have written 226512 as a product of primes. Also, the notation m6n means that n is not divisible by m. Can every integer greater than 1 be written as a product of primes? What about a single prime p? It is convenient to adopt the terminology that a single prime p is a product 2 of one prime, itself. 2 We could go even further and say that 1 is also can be written as an empty product. In fact, mathematicians do this: They say that an empty sum is 0 and an empty product is 1. You may think this strange, but you’ve already seen it with exponents: The notation n 0 a stands for the product of n copies of a. Thus a is the product of no copies of a, and 0 you learned that we define a = 1 when you studied exponents. This is done so that the n+m n m rule a =a a will work when n= 0. NT-2Section 1: Basic Facts About Numbers In Unit IS (Induction, Sequences and Series) we use induction to prove the assertion A(n) for every integer n≥2 where A(n)= “n is a product of primes.” You might find it helpful to read the first two pages of Unit IS at this time. We start (base case) with n = 2, which is a prime and hence a product of primes. The induction hypothesis is the following: “Suppose that for some n2, the assertionA(k) is true for all k such that 2≤k n.” Assume the induction hypothesis and consider n. If n is a prime, then it is a product of primes (itself). Otherwise, n = st where 1 s n and 1 t n. By the induction hypothesis, s and t are each a product of primes. Hence n = st is a product of primes. Thus A(n) is true and the assertion is proved by induction. e e e 1 2 k If n ≥ 2 is an integer, the notation n = p p ···p is commonly used to designate 1 2 k its prime factorization, where p ,p ,...p are distinct primes and all e 0. In other 1 2 k i words, each prime factor is raised to its highest power that divides n. Thus, 226512 = 4 2 1 1 2 ×3 ×1573 . Of course, exponents with value 1 are usually omitted, thus 1573 would be written 1573. It is important to note (We won’t give a proof.) that prime factorization is unique in the following sense. Supposeone studentcorrectlycomputesaprime factorizationofn and e e e 1 2 k gets n=p p ···p where she has ordered the prime factors so that p p ···p . 1 2 k 1 2 k Suppose that another student also correctly computes a prime factorization of n and gets f f f 1 2 j n=q q ···q with q q ··· q , thenk =j, q =p , and e =f , for i = 1,...,k. 1 2 j i i i i 1 2 j Let’s call this a theorem: Theorem 1 (Unique prime factorization) Every integern≥ 2 can be factored into a productof primes. Thisfactorizationisuniquein thesensethatanytwo suchfactorizations differ only in the order in which the primes are written. Sometimes people think it is “obvious” that prime factorization is unique. That’s not true. There are sets other than the integers where prime factorization can be defined, but 3 it may not be unique. The assumptionthat it is unique was used in a “proof”of Fermat’s Last Theorem about a century ago. Of course, the proof was false because factorization was not unique in the set being studied. Understanding the problem led to what is known as “algebraic number theory,” which eventually led to a correct proof of Fermat’s Last Theorem. √ 3 Whena,b∈Z,complexnumbersoftheforma+b −5areatypeof“algebraicinteger.”    √ √ The set of these “integers” is denoted byZ −5 = a+b −5 a,b∈Z . We have √  √  6= 2×3= 1+ −5 1− −5 . √ √ √  −5and1− −5cannotbefactoredfurtherinZ −5 Since2, 3, 1+ , theyare “primes.” √  Hence prime factorization is not unique forZ −5 . The desire for uniqueness led to the   √ concept of “ideals” inZ −5 and the development of “algebraic number theory.” NT-3Number Theory and Cryptography Now that we know that every integer n≥ 2 is a product of powers of primes, we can show Theorem 2 (Infinitely many primes) There are infinitely many primes. Proof: Suppose that there were only finitely many primes, say the k primes P=p ,p ,...,p . 1 2 k Consider the integer n= (p p ···p )+1 gotten by taking the product of all of the primes 1 2 k in P and adding one. Clearly, n ∈/ P (it’s too big). That means n is a product of primes. Let p be one of the prime factors of n. Hence n/p is an integer. For p ∈P, dividing n by i p leaves a remainder of 1 and so n/p is not an integer. Since n/p is an integer and n/p i i i is not, we cannot have p = p . Hence p∈/ P. Contradiction Thus there cannot be finitely i many primes. Prime factorization can be used to prove things that apparently do not depend on primes. Our next example illustrates this. √ Example 3 (For all n ∈N, n is either an integer or irrational) The integer 36 √ is nice because 36 = 6 and 6 is an integer. Thus 36 is called a perfect square. A perfect √ squareisanintegerwhosesquarerootisalsoaninteger. Suppose nisnotaninteger. How √ √ “bad” is it? For example, maybe, though not an integer, n is rational; that is, n=a/b for some integers a and b. Sadly, that can’t happen. We prove this by contradiction √ Suppose n = a/b where b ≥ 2 and we have cancelled common factors from the √ 2 2 numeratoranddenominator. Since n =a/b, we havenb =a . Letpbe aprime factorof 2 2 b (p exists since b≥ 2). Since prime factorizationis unique, p is a prime factor of nb =a . On the other hand, since p is a prime factor of b, it is not a prime factor of a since we have cancelled common factors to get a and b. So far, we have shown that p is a prime factor of 2 a but not a prime factor ofa. In the next paragraph,we show that this is a contradiction. e e e 1 2 k For any integer x, if the prime factorization of x is x = p p ···p then the prime 1 2 k 2e 2e 2e 2 2 1 2 k factorization of x is x = p p ···p . In other words, any integer x has exactly the 1 2 k 2 same prime divisors as its square, x . Apply this with x=a. We have proved √ Theorem 3 (Irrational square roots) For all n ∈ N, n is either an integer or irrational. 2 2 We can use this to get a lot of irrational numbers. Suppose that k n (k+1) for √ √ some k ∈N. Taking square roots, we have k nk+1. Thus n cannot be an integer √ √ √ √ √ √ 4 and so it must be irrational. In particular 2, 3, 5, 6, 7, 8 are all irrational. 4 Some classical Greeks were bothered by this. They thought there should be a basic unit of length such that all the lines in a geometrical constructionwere integer multiples of that length, but they could prove that this was impossible: By the Pythagorean Theorem, √ the diagonal of a unit square has length 2, which they knew was irrational. If the side of √ the square were b basic units long and the diagonal were a, then 2=a/b. NT-4Section 1: Basic Facts About Numbers There are some basic properties of irrational and rational numbers lurking beneath the surface here. If the product xy of two numbers is irrational, one of the numbers must be irrational. Equivalently (the contrapositive), if x and y are both rational, say x = a/b and y = c/d, then xy = ac/bd is rational. Likewise, if the sum x+y of two numbers is irrational, one of the numbers must be irrational (prove this). Some studentsthinkthese statementsmeanthatthe productoftwo nonzeroirrational numbers is irrational and the sum of two irrational numbers is irrational, both statements √ √ √ √ are false: 2× 2 = 2 and (− 2)+ 2 = 0. It is true, however, that if x = 6 0 is rational and y is irrational, then the product xy is irrational. To prove this statement, use the contrapositive. If xy = a/b then y = a/bx. Since x 6= 0 is rational, say x = c/d, this implies that y =ad/cb is rational. Example 4 (The rational numbers are countable) We want to show that we can create a list a ,a ,a ,... such that every rational number appears on the list. We do this 1 2 3 as follows: Step 1. Start the list with 0,1/1,−1/1 and set k =3. Step 2. Appendto the list all rational numbers in reducedform where the sum of the numerator and denominator (ignoring signs) is k. Begin with the largest numerators andproceedtothesmallest,listingpositivenumbersandthennegativeones. (Thus,for k = 3 we append2/1,1/2,−1/2,−2/1 and for k = 4 we append3/1,1/3,−1/3,−3/1.) Step 3. Increase k by one and go to Step 2. The list begins a = 0, a = 1/1, a = −1/1, 1 2 3 k =3: a = 2/1, a = 1/2, a = −1/2, a = −2/1, 4 5 6 7 k =4: a = 3/1, a = 1/3, a =−1/3, a =−3/1, 8 9 10 11 k =5: a = 4/1, a = 3/2, a = 2/3, a = 1/4, 12 13 14 15 a =−1/4, a =−2/3, a =−3/2, a − 4/1, 15 16 17 18 Note that each rational number occurs exactly once in the list. In some sense, the number ofrationalnumbersisthesameasthenumberofpositiveintegerssincewehaveonerational number for each positive integer (the subscript of a) Because we can form such a list, we say that the set of rational numbers is countable. More simply, people say that the rationals are countable. Example5(Thereal numbers are notcountable) Wemustshowthatitisimpossible to form a list of the real numbers. How can we do this? We must show that, no matter what list of real numbers we have, there is some real number that is not on the list. Suppose we have a list a ,a ,... of real numbers. Let d be the kth digit after the 1 2 k decimal point in a . For example, if a = 2.718281828... (the number e), then d = 2. If k 4 4 d = 1, let b = 2 and, if d = 6 1, let b = 1. Look at the number r = 0.b b b .... We k k k k 1 2 3 claim it is not in the list. Why is this? Suppose someone claims, for example that a =r. 99 By definition, d is the ninety-ninth digit of a after the decimal point. Since b = 6 d , 99 99 99 99 the numbers r and a differ in their ninety-ninth digits. Thus r = 6 a . 99 99 NT-5Number Theory and Cryptography Arguments of this type are called diagonal arguments. Why is this? A picture can help. Here ∗ stands for a digit we are not interested in and we have dropped all the digits before the decimal points. a =.d ∗ ∗ ∗ ∗ ∗ ... 1 1 a =.∗ d ∗ ∗ ∗ ∗ ... 2 2 a =.∗ ∗ d ∗ ∗ ∗ ... 3 3 a =.∗ ∗ ∗ d ∗ ∗ ... 4 4 a =.∗ ∗ ∗ ∗ d ∗ ... 5 5 The digits d ,d ,... that we are changing appear in a diagonal pattern. The diagonal is 1 2 not always so straightforward in a diagonal argument. Remainders and Modular Arithmetic We all know from elementary school that if we divide one integer x by another d 0, we geta quotientq anda remainderr, where0≤r d. Inotherwords,x=qd+r,0≤r d. Forexample, ifx= 234andd= 21, thenq = 11andr =3. Thus, 234=11×21+3. There are 21 possible remainders that can be gotten by dividing some randomly chosen integer by 21. These remainders belong to the set0,1,2,...,20. The setZ of all integers can be partitioned (divided up) into 21 subsets 21Z, 21Z+1, 21Z+2,...,21Z+20 according to these remainders. Note that, for a set S of numbers aS+b =as+bs∈S so that 21Z+4 = ...,−17,4,25,.... We have just seen that 234 belongs to the subset 21Z+3. (The set 21Z+3 equals3+21kk =0,±1,±2,....) For generald0, instead of d =21, we get dZ, dZ+1, dZ+2,...,dZ+(d−1) The sets dZ+j are called residue classes modulo d. Ifx =qd+r,0≤r d,thenwedenotethisfactbyxmodulod=r orbyxmodd=r. In this usage, “mod” is called a binary operation. Given any pair of integers x and d 0, computing xmodd always results in some integer r, 0≤r d. ′ The word “mod” is also used to convey the information that “x and x belong to the ′ ′ same residue class mod d.” The notation is x = x (mod d) or x 6= x (mod d) to express ′ the facts (respectively) that “x and x belong to the same residue class mod d,” or, “x and ′ x do not belong to the same residue class mod d.” Often you will see ≡ used instead of = in these expressions. Because of the possible confusion between these two uses, we will use the C program- ming language notation for the binary operation. Let’s summarize all this in a definition. Definition 2 (Residue classes and “mod”) Let d ≥ 2 be an integer For 0 ≤ j d the set dZ+j =nd+j n∈Z is called a residue class modulo d. The notation “mod” is used in two ways: NT-6Section 1: Basic Facts About Numbers ′ ′ • x = x (modd) This means that x and x belong to the same reside class modulo ′ d. In other words, when x and x are divided by d they have the same remainder. We say thatx andy are equal modulo d (or modd). For reasons we will learn later, this is ′ referred to as “using mod as an equivalence relation.” The notation x≡x (modd) is also used to indicate thatx andy are equal modulod. If the value ofd is clear, people ′ often write x≡x , omitting (modd). • xmodd =r or x%d =r This means that when x is divided by d the remainder is r where 0≤r d. Used this way, “mod” is a binary operator. To avoid confusion, we will use the C programming language notation r =x%d. Since the two uses of “mod” involve different placement of “mod,” you should not be confused as to which use is intended. Example6(Afactaboutremainders) Thereissomethingimportantaboutremainders ′ ′ ′ thattheymaynothavediscussedinelementaryschool. Supposex =qd+randx =q d+r . Then, subtracting and dividing by d gives ′ ′ ′ ′ x−x (q−q )d+(r−r ) r−r ′ = =q−q + . d d d ′ ′ Notethatsince0≤r dand0≤r dwemusthave0≤r−r d. Thismeansthatthe ′ r−r ′ ′ only way that can be an integer is thatr−r =0 or r =r . This seems like a trivial d ′ point, but it is very important. It means that x and x have the same remainder when ′ dividedbyd(i.e., belongtothesameresidueclassmodd)ifandonlyifddividesx−x . For example 7666 and 7652 belong to the same residue class modulo 7 since 7666−7652=14, which is 0 modulo 7. ′ The notation x = x (mod d) behaves like equality in many ways. The following theorem lists three of them. ′ Theorem 4 (Arithmetic with mod) The notation x = x (mod d) behaves like ′ equality for addition, subtraction and multiplication. In other words, if x = x (mod d) ′ and y =y (mod d) then ′ ′ ′ ′ ′ ′ x+y =x +y (modd), x−y =x −y (modd) and xy =xy (modd). We talk about addition modulo d or simply modular addition, and similarly for subtraction ′ ′ andmultiplication. Noticethatwe didnot sayx/y =x/y modd. It is not trueingeneral. For example, 2=8 (mod 6) and 2=2 (mod 6) but 2/26=8/2 (mod 6). ′ ′ Proof: We prove addition. By definition x+y = x +y (mod d) means that (x+y)− ′ ′ (x +y ) is divisible by d. But ′ ′ ′ ′ ′ ′ (x+y)−(x +y ) (x−x )+(y−y ) x−x y−y = = + . d d d d NT-7Number Theory and Cryptography ′ ′ ′ ′ Since x=x (mod d) and y =y (mod d), both x−x and y−y are divisible by d. Thus, ′ ′ (x+y)−(x +y ) is divisible by d. The proof for subtraction is nearly the same as for addition, so we omit it. ′ ′ We now prove multiplication. Again, we show that xy−xy is divisible by d: ′ ′ ′ ′ ′ ′ ′ xy−xy x(y−y )+y (x−x ) y−y x−x ′ = =x +y . d d d d ′ ′ ′ ′ Since, x =x (mod d) and y =y (mod d), both x−x and y−y are divisible by d. Thus, ′ ′ xy−xy is divisible by d. Example 7 (Powers of dZ+1) Suppose x ∈ dZ+1. We could equally well write this as x mod d = 1 or x = 1 (mod d) or even just x ≡ 1 provided we know we are doing n arithmetic modulo d. We claim that x ≡1 for all n∈N. The proof is by induction on n. 0 0 1 1 For n = 0, x = 1 and so x ≡ 1. For n = 1, x = x and so x ≡ 1 since we are n n−1 n−1 given that x ≡ 1. For n 1, x = (x )x. By induction x ≡ 1. By the theorem, n−1 x x≡1×1=1. We are done. When d = 2, you should be able to see that this simply states that powers of odd numbers are odd, a fact we proved in Example 1. Example 8 (Using modular arithmetic cleverly) There are smart ways and dumb ways to use Theorem 4. It is interesting to look first at a dumb way, just to see the power of these statements. Suppose you want to find the remainder when the number N =113×(167+484)+192×145is divided by 21. That is, we wish to know N (mod21). Afriendsaysheisgoingtohelp. Hetellsyouthat113=95180(mod21),167=5159244761 (mod 21), 484 = 9073 (mod 21), 192 = 207441 (mod 21) and 145 = 19857871 (mod 21). He suggests you substitute those larger numbers for the original numbers in the expression N =113×(167+484)+192×145 to get M = 95180×(5159244761+9073)+207441×19857871. He assuresyou that, if you computeM anddivide by 21 you will get the desired remainder r. He says he would like to borrow your car while you do the computations. After several hours work, you getM =495177116538231. Dividing by 21 gives 15 as a remainder. Thus, r = 15, so N (mod21) =15. That is the right answer but it is a dumb way to do it Another way is to just compute N =113×(167+484)+192×145= 101403 and divide that by 21 to get the remainder 15. That is not too dumb. Another way is to note that 113 = 8 (mod 21), 167 = 20 (mod 21), 484 = 1 (mod 21), 192 = 3 (mod 21), 145 = 19 (mod 21). Substitute those for the corresponding numbers to get L =8(20+1)+3∗19=225. Now divide 225 by 21 to get 15 as the remainder. A modification on the above is to note that 20=−1 (mod 21) and 19=−2 (mod 21) ′ to get L = 8(−1+1)+3(−2)=−6. Dividing −6 by 21 gives a remainder of 15. Did you NT-8Section 1: Basic Facts About Numbers learn that in elementary school? The remainder r must always be positive, 0 ≤ r 21. Thus, writing −6 = q×21+r gives −6 = (−1)×21+15. Do you see the power of these techniques? Don’t be afraid to use them (wisely). Note that they apply to multiplying and adding, not dividing. For example, 484 = 1 (mod 21), 22 = 1 (mod 21), but 484/21 (mod 21) = 6 1/1 (mod 21). The number 484/21 is not even an integer. The Floor and Ceiling Functions Incomputerscience, manybasic conceptsare naturallyexpressedin termsofintegervalues (e.g., running time, input size, memory blocks) but are analyzed by functions that return real numbers. The conversion of the real numbers to integers that have direct meaning in terms of original problems sometimes involves the special functions “floor” and “ceiling.” Let x ∈ R be a real number. The floor function of x, denoted by ⌊ x⌋ , is the largest integer less than or equal to x. It is also called the greatest integer function. The ceiling function of x, denoted by ⌈ x⌉ , is the least integer greater than or equal to x. It is also called the least integer function. Here are some examples: ⌈ 2.8⌉ =3, ⌈ 5⌉ =5, ⌈− 2.8⌉ =−2, ⌊ 2.8⌋ =2, ⌊ 5⌋ =5, ⌊− 2.8⌋ =−3, ⌈ 55+2.8⌉ = 55+⌈ 2.8⌉ =55+3= 58, ⌊− 5.6⌋ =−6=−⌈− (−5.6)⌉ , Geometrically, the idea is simple. The floor of x moves you to the next integer less than or equal to x on the number line. The ceiling moves you to the next integer greater than or equal to x. For computation, notice that ∀n∈Z, ∀x∈R,⌊ n+x⌋ =n+⌊ x⌋ . ∀n∈Z, ∀x∈R,⌈ n+x⌉ =n+⌈ x⌉ . This is easily shown and we omit the proof. Note also that ⌊ x⌋ =−⌈− x⌉ and ⌈ x⌉ =−⌊− x⌋ . For example, ⌊ 2.1⌋ =−⌈− 2.1⌉ . For proofs and exercises, it is often helpful to know that any real number can be written as the sum of an integer n and a fraction f, −1 f +1. Thus, 4.9 = 4+0.9, −3.6 =−3−0.6 = −4+0.4. If x = n+f, then, since ⌊ x⌋ = n+⌊ f⌋ and ⌈ x⌉ = n+⌈ f⌉ . you only have to think about the fractional part in your computations. For example, ⌊ 4.9⌋ =4+⌊ 0.9⌋ =4+0=4, ⌈− 3.6⌉ =−4+⌈ 0.4⌉ =−4+1=−3. If you prefer, ⌈− 3.6⌉ =−3+⌈− .6⌉ =−3+0=−3. NT-9Number Theory and Cryptography Exercises for Section 1 1.1. Prove the statement if true, otherwise find a counterexample. (a) For all natural numbers x and y, x+y is odd if one of x and y even and the other is odd. (b) For all natural numbers x and y, if x+y is odd then one of x and y even and the other is odd. 1.2. Prove the statement if true, otherwise find a counterexample. (a) The difference of any two odd integers is odd. (b) If the sum of two integers is even, one of them must be even. 1.3. Prove the statement if true, otherwise find a counterexample. (a) The product of two integers is even if and only if at least one of them is even. (b) The product of two integers is odd if and only if at least one of them is odd. 1.4. Prove the statement if true, otherwise find a counterexample. 3 3 (a) For any integers m and n, m −n is even if and only if m−n is even. 3 3 (b) For any integers m and n, m −n is odd if and only if m−n is odd. 1.5. Prove the statement if true, otherwise find a counterexample. 3 (a) For all integers n 2, n −8 is composite. n (b) For all integers n, (−1) =−1 if and only if n is odd. 1.6. Prove the statement if true, otherwise find a counterexample. 2 (a) ∀n∈Z, n +n+5 is odd. 2 2 (b) ∀n∈Z, (6(n +n+1)−(5n −3) is a perfect square). 2 (c) ∃M 0, ∀nM, (n −n+11 is prime). 2 (d) There is a unique prime p of the form n +2n−3. 1.7. Prove the statement if true, otherwise find a counterexample. (a) For all integers n 0, either n is a perfect square or, n = x+y where x and y are perfect squares or, n=x+y+z where x, y, and z perfect squares. (b) The product of four consecutive positive integers is never a perfect square. 1.8. Prove the statement if true, otherwise find a counterexample. NT-10Section 1: Basic Facts About Numbers 1/2 1/2 1/2 1/2 (a) For all distinct positive integers m and n, either m +n and m −n are both rational or both irrational.   1/2 1/2 1/2 1/2 Hint: Consider m +n m −n . 1/2 1/2 1/2 1/2 (b) Foralldistinctpositiveintegers,ifeitherm +n orm −n arerational then both m and n are perfect squares. (c) For all distinct positive integers m and n, both m and n are perfect squares if 1/2 1/2 and only if m+2m n +n is a perfect square. (d) Which of (a), (b) and (c) are true if m = 6 n is changed to m =n? 1.9. Prove that an integer n 1 is composite if and only if p divides n for some prime 1/2 p≤n . 1.10. Write the following rational numbers as the ratio a/b of two integers a and b0. (a) 3.1415 (b) 0.30303030... (c) 6.32152152152152... ax+b 1.11. Letx∈R satisfy the equation = 1 wherea,b, c, andd are rationalanda = 6 c. cx+d Is x rational? Explain. 1.12. In each case, if the statement is true, prove it, if false, give a counterexample. (a) The sum of three consecutive integers is zero (mod 3). (b) The product of two even integers is zero (mod 4). (c) An integer is divisible by 16 only if it is divisible by 8. (d) For all odd integers n, 3n+3 is divisible by 6. 1.13. In each case, if the statement is true, prove it, if false, give a counterexample. (a) ∀a,b,c∈Z, if ab then abc. (b) ∀a,b,c∈Z, if ab and bc, then ac (c) ∀a,b,c∈Z, if ac then abc. 1.14. In each case, if the statement is true, prove it, if false, give a counterexample. (a) ∀a,b,c∈Z, if a (b+c) then ab and ac. (b) ∀a,b,c∈Z, if abc then ab or ac. 2 2 (c) ∀a,b∈Z, if ab then a b . (d) ∀a,b∈Z, if a 6b then a 6 or ab. 1.15. In each case, factor the given number into a product of powers of distinct primes. NT-11Number Theory and Cryptography (a) 1404. (b) 9702. (c) 89250. e e 1 k 1.16. Let n = p ··· p be the factorization of n into powers of distinct primes. Let 1 k m≥ 1 be an integer. m (a) What is the factorization of n into powers of distinct primes? 1/m 1/m (b) If s 0 is an integer but s is not, must s be irrational? Explain your answer. 1.17. In each case, factor the given number into a product of powers of distinct primes. Recall that n=n(n−1)(n−2)··· 1 is the product of the first n integers. (a) 20. How many terminal zeros in this number? 2 (b) (20) . How many terminal zeros in this number? 3 (c) (20) . How many terminal zeros in this number? 1.18. Prove that if x is a nonzero natural number then 3 x if and only if 3 divides the sum of the decimal digits of x. 1.19. Prove or give a counterexample: The product of any four consecutive integers is equal to 0 (mod 8). 2 1.20. Prove that, for all integers n 1, n −3= 6 0(mod4). 4 1.21. Prove that, for all odd integers n, n = 1(mod16). 1.22. If m−n has remainder 0 when divided by d does that mean the m and n each have the same remainder when divided by d? Support your answer by giving a counterexample or a proof. 1.23. For all integers m,n,a,b, if m mod d = a and n mod d = b does that mean that (m+n) modd =a+b? 1.24. (a) Prove: If j =k (mod d), then dZ+j =dZ+k. (b) Prove: If j = 6 k (mod d), then (dZ+j)∩(dZ+k) is the empty set. log (x) a 1.25. If a0, log (x) is the unique number such that a =x. a (a) Suppose thatp andq are two different primes. Prove that log (q) is irrational. p (b) Istheresultin(a)trueifpandq areallowedtobecompositenumbers? Justify your answer. k m (c) For integers k and m, prove that log (b) =k/m if and only if a =b . a 1.26. In each case, if the statement is true, prove it, if false, give a counterexample. NT-12Section 2: Cryptography and Secrecy (a) ∀x,y ∈R, (⌊ x−y⌋ =⌊ x⌋−⌊ y⌋ ). (b) ∀x∈R, ∀k ∈Z, (⌊ x−k⌋ =⌊ x⌋− k). k k (c) ∀x∈R, k ∈N, (⌊ x ⌋ =⌊ x⌋ ). 1.27. In each case, if the statement is true, prove it, if false, give a counterexample. + n n−r (a) ∀n∈Z, k∈N , (⌊ ⌋ = ) where r =n%k). k k + (b) ∀x∈R, ∀a,b∈N , (⌊ ax+b⌋ =a⌊ x⌋ +b). 1.28. Prove each of the following statements or give a counterexample. (a) ∀x∈R−Z, (⌊ x⌋ +⌊− x⌋ =−1). (b) ∀x∈R−Z, (⌈ x⌉ +⌈− x⌉ =+1). Section 2: Cryptography and Secrecy Cryptographyis concernedwith secretmessages. Cryptanalysisis the name for the general area of breaking secret codes so the messages can be read. This general topic represents a vast body of knowledge. We begin by introducing the basic ideas and problems. Then we take time out to study some number theory functions that are useful for cryptography on the internet. Finally, we look at two protocols that are currently used — Diffie-Hellman and RSA. Basic Ideas SupposethatAlicewishestosendamessagetoBobinsuchawaythatanyoneelsereceiving her message will not be able to understand it. She can communicate in code. There are three pieces of data involved: • The plaintext, which is what Alice wants to tell Bob. • The ciphertext, which is the message Alice actually sends Bob. • The key, which tells how to convert plaintext to ciphertext and vice versa. Since the key is known to Alice and Bob, it is sometimes called the shared key. The rules for converting can be thought of as functions. If P is the set of all possible plaintext messages and C is the set of all possible ciphertext messages, then the key K determines a function f : P → C that Alice uses to encipher the message. Bob uses the K −1 −1 inverse function f to decipher the message. Notice that, in order to decipher, f must K K exist. Thus f must be an injection. The next example illustrates a simple scheme for K doing this. NT-13Number Theory and Cryptography Example 9 (A simple code) Instead of Alice and Bob, we have two factories A and B that are going to exchange goods. There are 64 different items (coded 0,1,2,...63) to be shipped and four methodsof shipping (regularmail representedby the code 00; priority mail, code 01; air mail, code 10; and next day air, code 11). A shipment request looks something like 10101001. The two least significant bits, 01 in this case specify the method of shipping and the other six bits the item in base 2 (101010 or item 42 in this case). The factories want to keep the orders they are requesting from each other secret from their competitors. To keep things secret, the factories agree on a simple encipherment procedure. They agree on a fixed eight bit binary string that they share as a secret. Here is the secret string that they happento choose: K =11000111. This is the shared key, also called the secret key or, simply, the key. Factory A wants to place order r = 10101001 with factory B. To do this, the folks at A add r to K bit-by-bit using addition mod 2. That is, 0+0 = 0, 0+1 = 1+0 = 1, 1+1= 0. Here is what happens: 10101001 plaintext 11000111 key K 01101110 ciphertext Thefirstlineisthemessage,thesecondlineisthekey,andthethirdlineisthemod2bit-by- bit sum of the message and the key. We have just computed f (10101001). Actually, this K is done in the computer. When someone wants to place an order, they type in 10101001. The computer does the addition and sends the result to factory B. When factory B’s computer receives the ciphertext, it adds the shared key to the ciphertext as follows: 01101110 ciphertext 11000111 key K 10101001 plaintext This reverses the process and reveals the correct order from factory A. Pretty nifty — the −1 function and its inverse are the same, i.e. f =f . K K −1 Inthepreviousexample,f =f . Thismakesprogrammingeasiersincethesoftware K K for deciphering is the same as the software for enciphering. As a result, many systems are −1 designed to have f =f . K K There is a problem with our simple system (other than the fact that it’s too simple): We can only send an 8-bit message. • What if we want to send English instead of bits? This is no problem since computers store everything as bits. For example, text is stored using ASCII. • What if we want to send longer messages? Well, we could break it into pieces that are 8-bits long and add the key to each 8-bit piece. For reasons we won’t go into, using the same key K for each 8-bit piece is bad. Therefore there should be some rule for 8 changing K. A simple rule is to replace the K for the current piece with 3K mod 2 for the next piece. NT-14

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