離散數學-數論-資料下載頁

　　

【正文】 ose 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?1642 = 372?328 = 44. gcd(164,44) = gcd(44, 164 mod 44). – 164 mod 44 = 164?44 ?164/44? = 164?443 = 164?132 = 32. gcd(44,32) = gcd(32, 44 mod 32) = gcd(32,12) = gcd(12, 32 mod 12) = gcd(12,8) = gcd(8, 12 mod 8) = gcd(8,4) = gcd(4, 8 mod 4) = gcd(4,0) = 4. So, we repeatedly swap the numbers. Largest first. “mod” reduces them quickly! Complexity? Guess… O(log b) divisions. Linear in digits of b! Compare to direct search for divisor. (Lame`’s thm. Section ) 2022+ yr alg. makes Emerce possible! 72 Integers and Algorithms 73 Baseb number systems Ordinarily, we write base10 representations of numbers, using digits 09. Of course, any base b1 will work. For any positive integers n,b, there is a unique sequence ak ak1… a1a0 of digits aib such that: ???kiii ban0The “base b expansion of n” Hmm. What about base 1? Unary notation。 “mainly” quite inefficient. Why bother with “unary”? Complexity of algs.: always think about, what is the length of the input. Some problems still hard even with unary input! 74 Base Systems Theorem: Base b expansion of a number Let b be a positive integer greater than 1. Then if n is a positive integer, it can be expressed uniquely in the form n = ak bk ^k + ak1 bk1 ^(k1)+ … + a 1 b^1 + a0 Where k is a nonnegative integer, a0, a1, …, a k are nonnegative integers less than b, and ak ≠0 (Proof by induction) Bases of Particular Interest Base b=10 (decimal): 10 digits: 0,1,2,3,4,5,6,7,8,9. Base b=2 (binary): 2 digits: 0,1. (“Bits”=“binary digits.”) Base b=8 (octal): 8 digits: 0,1,2,3,4,5,6,7. Base b=16 (hexadecimal): 16 digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F The modern digital world! Octal digits correspond to groups of 3 bits Hex digits give groups of 4 bits Used “only” because we have 10 fingers Converting to Base b (An algorithm, informally stated.) To convert any integer n to any base b1: To find the value of the rightmost (lowestorder) digit, simply pute n mod b. Now, replace n with the quotient ?n/b?. Repeat above two steps to find subsequent digits, until n is gone (=0). 78 Constructing Base b Expansions procedure base b expansion (n:positive integer) q := n k := 0 while (q ? 0) begin ak := q mod b q := ? q / b ? k := k + 1 end {the base b expansion of n is (ak1 ak2 . . . a1 a0 )b } N=25 in binary? 12m o d112/312m o d332/602m o d662/1202m o d12122/2512m o d252543210???????????????????aNaNaNaNaNSo, we have 25 in binary is 11001. 80 N= 23670 in hexadecimal? 23670 mod 16 = 6。 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??