【正文】 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) = 1 63 Relative primes Two numbers are relatively prime if they don’t have any mon factors (other than 1) – Rephrased: a and b are relatively prime if gcd (a,b) = 1 gcd (25, 16) = 1, so 25 and 16 are relatively prime 64 Pairwise relative prime A set of integers a1, a2, … an are pairwise relatively prime if, for all pairs of numbers, they are relatively prime – Formally: The integers a1, a2, … an are pairwise relatively prime if gcd(ai, aj) = 1 whenever 1 ≤ i j ≤ n. Example: are 10, 17, and 21 pairwise relatively prime? – gcd(10,17) = 1, gcd (17, 21) = 1, and gcd (21, 10) = 1 – Thus, they are pairwise relatively prime Example: are 10, 19, and 24 pairwise relatively prime? – Since gcd(10,24) ≠ 1, they are not More on gcd’s 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 pute the gcd by the following formula: – Example: gcd(120,500) = 2min(3,2) 3min(1,0) 5min(1,3) = 22 30 51 = 20 nn bnbbanaa pppbpppa . . .,. . . 2121 2121 ??),m i n (),m i n (2),m i n (1 ...),g c d ( 2211 nn banbaba pppba ?Least mon multiple The least mon 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) = 24 35 72 = 190512 ),m a x (),m a x (2),m a x (1 . . .),l c m ( 2211 nn banbaba pppba ?lcm and gcd theorem 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 So, 10*25 = 5*50 Example: gcd (95256, 432) = 216, lcm (95256, 432) = 190512 So, 95256*432 = 216*190512 How do we find the gcd? Two algs.: 1) Try all s up to smallest 2) Factor s. (likely) Exp. in of digits! ? Euclid’s Algorithm for GCD Finding GCDs by paring prime factorizations can be difficult when the prime factors are not known! And, no fast alg. for factoring is known. (except …) Euclid discovered: For all ints. a, b gcd(a, b) = gcd((a mod b), b). How can this be useful? (assume ab) Sort a, b so that ab, and then (given b1) (a mod b) a, so problem is simplified. Euclid of Alexandria 325265 . On quantum puter! Theorem: Let a =bq+r, where a, b, q, and r are integers. Then gcd(a,b) = gcd(b,r) Suppose a and b are the natural numbers whose gcd has to be determined. And suppose the remainder of the division of a by b is r. Therefore a = qb + r where q is the quotient of the division. Any mon divisor of a and b is also a divisor of r. To see why this is true, consider that r can be written as r = a ? qb. Now, if there is a mon divisor d of a and b such that a = sd and b = td, then r = (s?qt)d. Since all these numbers, including s?qt, are whole numbers, it can be seen that r is divisible by d. (Also, by corollary on slide 6.) Similarly, any mon divisor of b and r is also a divisor of a. Note that a = qb +r. Hence a mon divisor of b and r also divides a. It follows that gcd(a,b) = gcd(b,r). QED 70 Euclidean Algorithm procedure procedure (a,b:positive integers) x := a y := b while y ? 0 begin r := x mod y x := y y := r end { gcd(a, b) is x } Lemma: Let a = bq + r, where a, b, q, and r are integers. Then gcd(a, b) = gcd(b, r) What about the “y=0” case? Arises when r = 0. So, y divides x. But “x:=y” and “y:=0”, so return x. Also note that gcd(a,0) = a. Do we need a = b? hmm… Euclid’s Algorithm Example gcd(372,164) = gcd(164, 372 mod 164). – 372 mod 164 = 372?164 ?372/164? = 372?164 6 N= ? 23670/16 ? = 1479 mod 16 = 7 76 N= ? 1479/16 ? = 92 mod 16 = 12 C76 N= ?92/16 ? = 5 mod 16 = 5 5C76 Addition of Integers in Binary Notation procedure add (a,b:positive integers) c := 0 for j := 0 to n 1 begin d := ? (aj + bj + c) / 2 ? sj := aj + bj + c 2d c := d end sj := c {the binary expansion of the sum is (sn sn1 . . . s0 )2 } {the binary expansions of a and b are: an1,an2,… a 1,a0 and bn1,bn2,… b 1,b0} As you have known since grade 1 or before … ? Correctness proof? Complexity? (additions) O(n), where n is number of bits! (log of the size of the number) 82 Multiplying Integers procedure multiply (a,b:positive integers) c := 0 for j := 0 to n 1 begin if bj then cj := a shifted j places else cj := 0 end p := 0 for j := 0 to n – 1 p := p + cj {p is the value of ab } {the binary expansions of a and b are: an1,an2,… a 1,a0 and bn1,bn2,… b 1,b0} O(n2) Note: There are more efficient algorithms for multiplication! Complexity? (additions and shifts) Modular Exponentiation Problem: Given large integers b (base), n (exponent), and m (modulus), efficiently pute bn mod m. – Note that bn itself may contain a very large number of digits. Yet, this is a type of calculation that is monly required in modern cryptographic algorithms! Hmm. Modular Exponentiation: Using Binary Expansion of exponent n Note that: We can pute b to various powers of 2 by repeated squaring. – Then multiply them into the partial product, or not, depending on – whether the corresponding ai bit is 1. 002211002211)()()( 222222aaaaaanbbbbbkkkkkkkk??