Integers and DivisionWhy prime numbers?The divides operatorTheorem on the divides operatorPrime numbersFundamental theorem of arithmeticComposite factorsShowing a number is primeShowing a number is compositePrimes are infiniteThe prime number theoremShowing a number is prime or notThe division “algorithm”Greatest common divisorRelative primesMore on gcd’sLeast common multiplelcm and gcd theoremPseudorandom numbersSlide 21Slide 22The Caesar cipherSlide 24Rot13 encoding1Integers and DivisionCS 202Epp section ??Aaron Bloomfield2Why prime numbers?•Prime numbers are not well understood•Basis for today’s cryptography•Unless otherwise indicated, we are only talking about positive integers for this chapter3The divides operator•New notation: 3 | 12–To specify when an integer evenly divides another integer–Read as “3 divides 12”•The not-divides operator: 5 | 12–To specify when an integer does not evenly divide another integer–Read as “5 does not divide 12”4Theorem on the divides operator•If a | b and a | c, then a | (b+c)–Example: if 5 | 25 and 5 | 30, then 5 | (25+30)•If a | b, then a | bc for all integers c–Example: if 5 | 25, then 5 | 25*c for all ints c•If a | b and b | c, then a | c–Example: if 5 | 25 and 25 | 100, then 5 | 1005Prime numbers•A positive integer p is prime if the only positive factors of p are 1 and p–If there are other factors, it is composite–Note that 1 is not prime!•It’s not composite either – it’s in its own class•An integer n is composite if and only if there exists an integer a such that a | n and 1 < a < n6Fundamental theorem of arithmetic•Every positive integer greater than 1 can be uniquely written as a prime or as the product of two or more primes where the prime factors are written in order of non-decreasing size•Examples–100 = 2 * 2 * 5 * 5–182 = 2 * 7 * 13–29820 = 2 * 2 * 3 * 5 * 7 * 717Composite factors•If n is a composite integer, then n has a prime divisor less than or equal to the square root of n•Strong inductive proof using the following logic:–Since n is composite, it has a factor a such that 1<a<n–Thus, n = ab, where a and b are positive integers greater than 1–Either a≤n or b≤n (Otherwise, ab >  n*n > n)–Thus, n has a divisor not exceeding n–This divisor is either prime or a composite•If the latter, then it has a prime factor–In either case, n has a prime factor less than n8Showing a number is prime•Show that 113 is prime•Solution–The only prime factors less than 113 = 10.63 are 2, 3, 5, and 7–Neither of these divide 113 evenly–Thus, by the fundamental theorem of arithmetic, 113 must be prime9Showing a number is composite•Show that 899 is prime•Solution–Divide 899 by successively larger primes (up to 899 = 29.98), starting with 2–We find that 29 and 31 divide 899•On a unix system, enter “factor 899”aaron@orion:~.16> factor 899899: 29 3110Primes are infinite•Theorem (by Euclid): There are infinitely many prime numbers•Proof by contradiction•Assume there are a finite number of primes•List them as follows: p1, p2 …, pn.•Consider the number q = p1p2 … pn + 1–This number is not divisible by any of the listed primes•If we divided pi into q, there would result a remainder of 1–We must conclude that q is a prime number, not among the primes listed above•This contradicts our assumption that all primes are in the list p1, p2 …, pn.11The prime number theorem•The radio of the number of primes not exceeding x and x/ln(x) approaches 1 as x grows without bound–Rephrased: the number of prime numbers less than x is approximately x/ln(x)–Rephrased: the chance of an number x being a prime number is 1 / ln(x)•Consider 200 digit prime numbers–ln (10200)  460–The chance of a 200 digit number being prime is 1/460–If we only choose odd numbers, the chance is 2/460 = 1/230–This result will be used in the next lecture!12Showing a number is prime or not•Consider showing that 2650-1 is prime–That number has about 200 digits•There are approximately 10193 prime numbers less than 2650-1–By theorem 5 (x/ln(x), where x = 2650-1)•How long would that take to test each of those prime numbers?–Assume a computer can do 1 billion (109) per second–It would take 10193/109 = 10184 seconds–That’s 3.2 * 10176 years!–There are quicker methods to show a number is prime, but not to find the factors if the number is found to be composite•We will use this in the next lecture13The division “algorithm”•Let a be an integer and d be a positive integer. Then there are unique integers q and r, with 0 ≤ r < d, such that a = dq+r•We then define two operators:–q = a div d–r = a mod d14Greatest common divisor•The greatest common divisor of two integers a and b is the largest integer d such that d | a and d | b–Denoted by gcd(a,b)•Examples–gcd (24, 36) = 12–gcd (17, 22) = 1–gcd (100, 17) = 115Relative primes•Two numbers are relatively prime if they don’t have any common factors (other than 1)–Rephrased: a and b are relatively prime if gcd (a,b) = 1•gcd (25, 39) = 1, so 25 and 39 are relatively prime16•Given two numbers a and b, rewrite them as:–Example: gcd (120, 500)•120 = 23*3*5 = 23*31*51•500 = 22*53 = 22*30*53•Then compute the gcd by the following formula:–Example: gcd(120,500) = 2min(3,2)3min(1,0)5min(1,3) = 223051 = 20More on gcd’snnbnbbanaapppbpppa ...,...21212121),min(),min(2),min(1...),gcd(2211nnbanbabapppba 17),max(),max(2),max(1...),lcm(2211nnbanbabapppba Least common multiple•The least common multiple of the positive integers a and b is the smallest positive integer that is divisible by both a and b.–Denoted by lcm (a, b)– •Example: lcm(10, 25) = 50•What is lcm (95256, 432)?–95256 = 233572, 432=2433–lcm (233572, 2433) = 2max(3,4)3max(5,3)7max(2,0) = 243572 = 19051218lcm and gcd theorem•Let a and b be positive integers. Then a*b = gcd(a,b) * lcm (a, b)•Example: gcd (10,25) = 5, lcm (10,25) = 50–10*25 = 5*50•Example: gcd (95256, 432) = 216, lcm (95256, 432) = 190512–95256*432 = 216*19051220Pseudorandom numbers•Computers cannot generate truly random numbers!•Algorithm for “random” numbers: choose 4