EFTA01140626.pdf

Basic Number Theory Zeph Grunschlag Copyright .& Zeph Groh.h.9, 2001-2002. 1 EFTA01140626 Announcement Last 4 problems will be added tonight to HW4. 2 EFTA01140627 Agenda Section 2.3 • Divisors • Primality • Fundamental Theorem of Arithmetic • Division Algorithm • Greatest common divisors/least common multiples • Relative Primality • Modular arithmetic • Caesar's Cipher 2002.02.25 3 3 EFTA01140628 Importance of Number Theory Before the dawn of computers, many viewed number theory as last bastion of "pure math" which could not be useful and must be enjoyed only for its aesthetic beauty. No longer the case. Number theory is crucial for encryption algorithms. Of utmost importance to everyone from Bill Gates, to the CIA, to Osama Bin Laden. E.G., of great importance in COMS 4180 "Network Security". 2002.02.25 4 4 EFTA01140629 Importance of Number Theory The encryption algorithms depend heavily on modular arithmetic. We need to develop various machinery (notations and techniques) for manipulating numbers before can describe algorithms in a natural fashion. First we start with divisors. 5 EFTA01140630  Divisors DEF: Let a, band c be integers such that a = b .c. Then band c are said to divide (or are factors) of a, while a is said to be a multiple of b (as well as of c). The pipe symbol "I" denotes "divides" so the situation is summarized by: blancla. NOTE: Students find notation confusing, and think of "I" in the reverse fashion, perhaps confuse pipe with forward slash "I" 2002.02.25 6 6 EFTA01140631  Divisors. Examples Q: Which of the following is true? 1. 77 I 7 2. 7 I 77 3. 24 I 24 4. 0 I 24 5. 24 I 0 002.02-25 7 EFTA01140632  Divisors. Examples A: 1. 77 I 7: false bigger number can't divide smaller positive number 2. 7 I 77: true because 77 = 7 • 11 3. 24 I 24: true because 24 = 24 • 1 4. 0 I 24: false, only 0 is divisible by 0 5. 24 I 0: true, 0 is divisible by every number (0 = 24 • 0) 8 EFTA01140633  Formula for Number of Multiples up to given n Q: How many positive multiples of 15 are less than 100? _CC 2 C2 9 EFTA01140634  Formula for Number of Multiples up to given n A: Just list them: 15, 30, 45, 60, 75, 80, 95. Therefore the answer is 6. Q: How many positive multiples of 15 are less than 1,000,000? 10 EFTA01140635  Formula for Number of Multiples up to Given n A: Listing is too much of a hassle. Since 1 out of 15 numbers is a multiple of 15, if 1,000,000 were were divisible by 15, answer would be exactly 1,000,000/15. However, since 1,000,000 isn't divisible by 15, need to round down to the highest multiple of 15 less than 1,000,000 so answer is L1,000,000/15]. In general: The number of d-multiples less than N is given by: l{m E I dim and m≤ N}I =LN/di 2002.02.25 11 11 EFTA01140636  Divisor Theorem THM: Let a, b, and c be integers. Then: 1. albs aic 4 al(b+ c) 2. alb-) albc 3. albs bk. 4 aic EG: 1. 17134 A 171170 4 171204 2. 17134 4 171340 3. 6112 A 121144 4 6 1 144 2002.02.25 12 12 EFTA01140637  Divisor Theorem. Proof of no. 2 In general, such statements are proved by starting from the definitions and manipulating to get the desired results. EG. Proof ofno. 2 (alb albc): Suppose al b. By definition, there is a number m such that b = am. Multiply both sides by cto get bc= amc= a (mc). Consequently, be has been expressed as a times the integer 177C so by definition of "I", albc 2002.02.25 13 13 EFTA01140638  Prime Numbers DEF: A number n≥ 2 prime if it is only divisible by 1 and itself. A number n≥ 2 which isn't prime is called composite. Q: Which of the following are prime? 0,1,2,3,4,5,6,7,8,9,10 2002.02.25 14 14 EFTA01140639  Prime Numbers A: 0, and 1 not prime since not positive and greater or equal to 2 2 is prime as 1 and 2 are only factors 3 is prime as 1 and 3 are only factors. 4,6,8,10 not prime as non-trivially divisible by 2. 5, 7 prime. 9 = 3 •3 not prime. Last example shows that not all odd numbers are prime. 2002.02.25 15 15 EFTA01140640  Fundamental Theorem of Arithmetic THM: Any number n≥ 2 is expressible as as a unique product of 1 or more prime numbers. Note: prime numbers are considered to be "products" of 1 prime. We'll need induction and some more number theory tools to prove this. Q: Express each of the following number as a product of primes: 22, 100, 12, 17 2002.02.25 16 16 EFTA01140641  Fundamental Theorem of Arithmetic A: 22 = 2.11, 100 = 2.2.5.5, 12 = 2•2•3, 17 = 17 Convention: Want 1 to also be expressible as a product of primes. To do this we define 1 to be the "empty product". Just as the sum of nothing is by convention 0, the product of nothing is by convention 1. -,Unique factorization of 1 is the factorization that uses no prime numbers at all. 2002.02.25 17 17 EFTA01140642  Primality Testing Prime numbers are very important in encryption schemes. Essential to be able to verify if a number is prime or not. It turns out that this is quite a difficult problem. First try: boolean isPrime(integer n) if ( /7 < 2 ) return false for(i= 2 to n -1) if(i In) // "divides"! not disjunction return false return true Q: What is the running time of this algorithm? 2002.02.25 18 18 EFTA01140643  Primality Testing A: Assuming divisibility testing is a basic operation —so 0(1) (this is an invalid assumption)— then above primality testing algorithm is O(n). Q: What is the running time in terms of the input size k? 19 EFTA01140644  Primality Testing A: Consider n = 1,000,000. The input size is k = 7 because n was described using only 7 digits. In general we have n = O(10k). Therefore, running time is O(10k). REALLY HORRIBLE! Q: Can we improve algorithm? 2002.02.25 20 20 EFTA01140645  Primality Testing A: • Don't try number bigger than n/2 • After trying 2, don't try any other even numbers, because know n is odd by this point. • In general, try only smaller prime numbers • In fact, only need to try to divide by prime numbers no larger than as we'll see next: 2002.02.25 21 21 EFTA01140646  Primality Testing LEMMA: If n is a composite, hen its smallest prime factor is ≤ Proof (by contradiction). Suppose the smallest prime factor is >V171 . Then by the fundamental theorem of arithmetic we can decompose n = pqx where p and q are primes >ji and xis some integer. Therefore n > 11.71 • ji • x = nx implying that n>n, which is impossible showing that the original supposition was false and the theorem is correct. 11A22 2002 02 25 22 EFTA01140647  Primality Testing. Example EG: Test if 139 and 1413_are prime. List all primes up to Vn and check if they divide the numbers. 2: Neither is even 3: Sum of digits trick: 1+3+9 = 13, 1+4+3 = 8 so neither divisible by 3 5: Don't end in 0 or 5 7: 140 divisible by 7 so neither div. by 7 11: Alternating sum trick: 1-3+9 = 7 so 139 not div. By 11. 1-4+3 = 0 so 143 is divisible by 11. STOP! Next prime 13 need not be examined since bigger than .‘M . Conclude: 139 is prime, 143 is composite. 2002.02.25 23 23 EFTA01140648  Division Remember long division? q the dthe 3 quotient divisor 31)117 93 a the r the dividend 24 remainder 117 = 31'3 + 24 a= dq+ r 2002.02.25 24 24 EFTA01140649  Division THM: Let a be an integer, and d be a positive integer. There are unique integers q, r with r e satisfying a = c/q + r The proof is a simple application of long- division. The theorem is called the division algorithm though really, it's long division that's the algorithm, not the theorem. ::002.02.25 25 25 EFTA01140650  Greatest Common Divisor Relatively Prime DEF Let a,b be integers, not both zero. The greatest common divisor of a and b (or gcd(a,b) ) is the biggest number dwhich divides both a and b. Equivalently: gcd(a,b) is smallest number which divisibly by any xdividing both a and b. DEF: a and bare said to be relatively prime if gcd(a,b) = 1, so no prime common divisors. ::002.02.25 26 26 EFTA01140651 Greatest Common Divisor Relatively Prime Q: Find the following gcd's: 1. gcd(11,77) 2. gcd(33,77) 3. gcd(24,36) 4. gcd(24,25) 2002.02.25 27 27 EFTA01140652  Greatest Common Divisor Relatively Prime A: 1. gcd(11,77) = 11 2. gcd(33,77) = 11 3. gcd(24,36) = 12 4. gcd(24,25) = 1. Therefore 24 and 25 are relatively prime. NOTE: A prime number are relatively prime to all other numbers which it doesn't divide. 2002.02.25 28 28 EFTA01140653  Greatest Common Divisor Relatively Prime EG: More realistic. Find gcd(98,420). Find prime decomposition of each number and find all the common factors: 98 = 2.49 = 2.7.7 420 = 2.210 = 2.2.105 = 2.2'3'35 = 2.2.3.5.7 Underline common factors: 2.7'7, 2.2.3.5.7 Therefore, gcd(98,420) = 14 ::002.02.25 29 29 EFTA01140654  Greatest Common Divisor Relatively Prime Pairwise relatively prime the numbers a, b, c, d, ... are said to be pairwise relatively prime if any two distinct numbers in the list are relatively prime. Q: Find a maximal pairwise relatively prime subset of { 44, 28, 21, 15, 169, 17 } . CC2 C2 2C 30 EFTA01140655  Greatest Common Divisor Relatively Prime A: A maximal pairwise relatively prime subset of {44, 28, 21, 15, 169, 17} : {17, 169, 28, 15} is one answer. {17, 169, 44, 15} is another answer. 31 EFTA01140656  Least Common Multiple DEF: The least common multiple of a, and b (lcm(a,b) ) is the smallest number m which is divisible by both a and b. Equivalently: lcm(a,b) is biggest number which divides any xdivisible by both a and b Q: Find the lcm's: 1. lcm(10,100) 2. lcm(7,5) 3. lcm(9,21) 002.02.25 32 32 EFTA01140657  2002-02-25 Least Common Multiple A: 1. lcm(10,100) = 100 2. Icm(7,5) = 35 3. Icm(9,21) = 63 THM: Icm(a,b) = ab/gcd(a,b) 2002.02.25 33 Skip proof in lecture 33 EFTA01140658  2002-02-25 lcm in terms of gcd Proof THM: Icm(a,b) = ab/gcd(a,b) Proof Let g = gcd(a,b). 20D2.02.25 Skip proof in lecture 34 EFTA01140659  2002-02-25 lcm in terms of gcd Proof THM: lcm(a,b) = ab/gcd(a,b) Proof Let g = gcd(a,b). Factor a and b using g. a= gx, b= gy where xand y are relatively prime. 2002.02.25 35 Skip proof in lecture 35 EFTA01140660  2002-02-25 lcm in terms of gcd Proof THM: lcm(a,b) = ab/gcd(a,b) Proof Let g = gcd(a,b). Factor a and b using g. a= gx, b= gy where xand y are relatively prime. Therefore, ab/gcd(a,b) = gxgy/g = gxy. Notice that a and b both divide gxy. On the other hand, let m be divisible by both a and b. 2002.02.25 36 Skip proof in lecture 36 EFTA01140661  2002-02-25 lcm in terms of gcd Proof THM: Icm(a,b) = ab/gcd(a,b) Proof (continued) on the other hand, let m be divisible by both a and b: So m/g is divisible by both xand y. As x and y have no common prime factors, the fundamental theorem of arithmetic implies that m/g must be divisible by xy. 2002.02.25 37 Skip proof in lecture 37 EFTA01140662  2002-02-25 lcm in terms of gcd Proof THM: lcm(a,b) = ab/gcd(a,b) Proof (continued) ...m/g must be divisible by xy. Therefore, m must be divisible by gxy. This shows that any multiple of a and b is bigger than gxy so by definition, gxy= ab/gcd(a,b) is the lcm. 2002.02.25 38 Skip proof in lecture 38 EFTA01140663  Modular Arithmetic There are two types of "mod" (confusing): the mod function • Inputs a number a and a base b • Outputs a mod b a number between 0 and b-1 inclusive • This is the remainder of a÷b • Similar to Java's % operator. the (mod) congruence • Relates two numbers a, a'to each other relative some base b • a m a' (mod b) means that a and a' have the same remainder when dividing by b 2002.02.25 39 39 EFTA01140664  mod function Similar to Java's "0/0" operator except that answer is always positive. E.G. -10 mod 3 = 2, but in Java —10%3 = -1. Q: Compute 113 mod 24 -29 mod 7 -10 40 EFTA01140665  mod function A: Compute 113 mod 24: 24)113 z. -29 mod 7 6 [CC 2 C2 2, 41 EFTA01140666  mod function A: Compute 4 _ 113 mod 24: 113 96 17 -29 mod 7 .C2 C2 2, 42 42 EFTA01140667  mod function A: Compute 4 _ 113 mod 24: 24)113 96 17 2. -29 mod 7 7F2T, 2202 0235 43 43 EFTA01140668  mod function A: Compute 4 113 mod 24: 24F3 96 17 -29 mod 7 —5 —35 6 ,CC2C22, 44 44 EFTA01140669  (mod) congruence Formal Definition DEF: Let a,a' be integers and b be a positive integer. We say that a is congruent to a' modulo b (denoted by a= a' (mod b) ) if b l (a— a'). Equivalently: a mod b = a'mod b Q: Which of the following are true? 1. 3 = 3 (mod 17) 2. 3 = -3 (mod 17) 3. 172 = 177 (mod 5) 4. -13 = 13 (mod 26) 2002.02.25 45 45 EFTA01140670  (mod) congruence A: 1. 3 = 3 (mod 17) True. any number is congruent to itself (3-3 = 0, divisible by all) 2. 3 = -3 (mod 17) False. (3-(-3)) = 6 isn't divisible by 17. 3. 172 = 177 (mod 5) True. 172-177 = -5 is a multiple of 5 4. -13 = 13 (mod 26) True: -13-13 = -26 divisible by 26. 2002.02.25 46 46 EFTA01140671  (mod) congruence Identities The (mod) congruence is useful for manipulating expressions involving the mod function. It lets us view modular arithmetic relative a fixed base, as creating a number system inside of which all the calculations can be carried out. • a mod b = a (mod b) 0. Suppose a= a'(mod b) and c= c'(mod b) Then: • a+c = (act- c')(mod b) • ac= a'c'(mod b) • a k E. a' k (mod b) 2002.02.25 47 47 EFTA01140672  Modular arithmetic harder examples Q: Compute the following. 1. 3071001 mod 102 2. (-45 • 77) mod 17 3. (i10 1)modll 1=4 2002.02.25 48 48 EFTA01140673  Modular arithmetic harder examples A: Use the previous identities to help simplify: 1. Using multiplication rules, before multiplying (or exponentiating) can reduce modulo 102: 3071001 mod 102 = 3071°°1 (mod 102) 11001 (mod 102) = 1 (mod 102). Therefore, 3071001 mod 102 = 1. 2002.02.25 49 49 EFTA01140674  Modular arithmetic harder examples A: Use the previous identities to help simplify: 2. Repeatedly reduce after each multiplication: (-45.77) mod 17 = (-45.77) (mod 17) .(6.9) (mod 17) = 54 (mod 17) = 3 (mod 17). Therefore (-45.77) mod 17 = 3. 2002.02.25 50 50 EFTA01140675  Modular arithmetic harder examples A: Use the previous identities to help simplify: 3. Similarly, before taking sum can simplify modulo 11: ( 23 23 3 E )MOd 11 (E )(MOd 1) (D - 10(11O(1 1 1) i=4 i=4 i=4 (1-1+1 —1+...+1-1)(mod11) 0(modii) Therefore, the answer is 0. .002.02.25 SI 51 EFTA01140676  Proving Modular Identities We first need: THM: a. a'(mod b) 3k a= a'+ kb Proof direction: If a= a'+ kb, then (a-a') = kb so that b I (a-a') which by definition means that a. a'(mod b) - direction: If a= a'(mod b), by definition b I (a-a') so for some k we have (a-a') = kb which becomes a= a'+ kb This is a handy little theorem as we'll see next: .002.02.25 52 52 EFTA01140677  Proving Modular Identities Prove the identity a= a'(mod b) n c= c'(mod b) ---4 ac= a'c'(mod b) Proof By the previous, we can assume that there are kand / such that a= a'+ bk and c= c'+ bl Thus ac= (a'+ bk)(c'+ bl) = a'c'+b(kc'-i-la'+bk1). Therefore (ac-a'c') = b(kcq-laq-bk6 is divisible by band hence by definition, ac= a'c'(mod b) 2002.02.25 53 53 EFTA01140678  Simple Encryption Variations on the following have been used to encrypt messages for thousands of years. 1. Convert a message to capitals. 2. Think of each letter as a number between 1 and 26. 3. Apply an invertible modular function to each number. 4. Convert back to letters (0 becomes 26). 2002.02.25 54 54 EFTA01140679  Letter <--Number Conversion Table A B C D E F G H I 3 K L M 1 2 3 4 5 6 7 8 9 10 11 12 13 N O P Q R S T U V W X Y 14 15 16 17 18 19 20 21 22 23 24 25 216 2002.02-25 55 55 EFTA01140680  Encryption example Let the encryption function be f (a) = (3a + 9) mod 26 Encrypt "Stop Thief" 1. STOP THIEF (capitals) 2. 19,20,15,16 20,8,9,5,6 3. 14,17,2,5 17,7,10,24,1 4. NQBE QGJXA 56 EFTA01140681  Decryption example Decryption works the same, except that you apply the inverse function. EG: Find the inverse of f (a) = (3a + 9) mod 26 If we didn't have to deal with mod 26, inverse would be g (a) = 3-1(a - 9) We'll see that since gcd(3,26) = 1, the inverse of 3 is actually well defined modulo 26 and is the number 9. This gives: g (a) = 9 (a - 9) mod 26 = (9a— 3) mod 26 2002.02.25 57 57 EFTA01140682  Caesar's Cipher f (a) = (a+3) mod 26 2002 02.25 se 58 EFTA01140683 Blackboard Exercise Prove that there are infinitely many prime numbers. (Discovered by Euclid). 59 EFTA01140684  2002-02-25 Importance of Number Theory Before the dawn of computers, many viewed number theory as last bastion of "pure math" which could not be useful and must be enjoyed only for its aesthetic beauty. No longer the case. Number theory is crucial for encryption algorithms. Of utmost importance to everyone from Bill Gates, to the CIA, to Osama Bin Laden. Check out Angelos Keromytis's lecture--- www.cs.columbia.edu/—angelos/teaching/lectureafindex.html ---from COMS 4180 "Network Security" in which he applies number theory to encryption. 2002.02.25 60 Link not functioning this semester 60 EFTA01140685