Unit 1.2 Integer Representations.pdf

§ Unit 1.2: Integer Representations & Algorithms Introduction At the heart of encrypting a message is the idea of changing the representation of the characters so that if our message is intercepted, the string of characters is incomprehensible to the unintended reader. By now y...

§ Unit 1.2: Integer Representations & Algorithms Introduction At the heart of encrypting a message is the idea of changing the representation of the characters so that if our message is intercepted, the string of characters is incomprehensible to the unintended reader. By now you are well aware that while humans communicate in words, computers communi- cate in numbers, and in order to understand how a computer can encrypt a string of characters, we need to understand how a computer represents integers. Some commonly used integer expansions are... Decimal Representation - base 10: 106 = 1 · 100 + 0 · 10 + 6 · 1 = 1 · 102 + 0 · 101 + 6 · 100 = (106)10 81 = 8 · 101 + 1 · 100 = (81)10 Binary Representation - base 2: (106)10 = 1 · 64 + 1 · 32 + 1 · 8 + 1 · 2 = 1 · 26 + 1 · 25 + 0 · 24 + 1 · 23 + 0 · 22 + 1 · 21 + 0 · 20 = (1101010)2 Octal Representation - base 8 Hexadecimal Representation - base 16 We will now delve deeper into these representations and device algorithms to convert between representations. Relevant Reading: DM 4.2 Integer Representations THM 1.2.1 | Let b > 1 ∈ Z and n ∈ Z+. Then ∃!ai ∈ Z satisfying 0 < ai < b for i = 0, 1, 2,... , k, k ≥ 0 such that n has b-expansion n = ak bk + ak−1 bk−1 + · · · + a1 b1 + a0 b0 NOTE: We write n = (ak ak−1 · · · a1 a0 )b e.g. 11 = (1011)2 because 11 = 1 · 23 + 0 · 22 + 1 · 21 + 1 · 20 1 Example 1. What is the binary representation of the following numbers? (a) 3 (b) 18 Example 2. What is the decimal representation of each of the following? (a) (101011111)2 (b) (7016)8 (c) (2AE0B)16 NOTE: In hexadecimal representation (i.e. b = 16), we have the following values: A = 10 B = 11 C = 12 D = 13 E = 14 F = 15 2  ALGORITHM 1.2.1 | Constructing base b-representations Suppose n, b ∈ Z+ where n is in decimal representation and b is the base you wish to convert to. Then, 1. Divide n by b to obtain n = b · q0 + a0. Recall that q0 and a0 will be integers. 2. Keep a0 as the rightmost digit in the base b-representation. 3. Set n = q0 and divide by b to obtain q0 = b · q1 + a1. 4. Keep a1 as the next rightmost digit in the base b-representation. 5. Repeat 3. − 4. until qi = 0. Example 3. (a) Find the octal-representation of (12345)10 (b) Find the base 16-representation of (175627)10 PSEUDOCODE 1.2.1 | Constructing base b-representations INPUT: n > 0 an integer in decimal representation, b > 1 - integers OUTPUT: (ak−1 , ak−2 ,... , a1 , a0 ) - base b representation b_representation(n, b): q = n k = 0 while q != 0: a_k = q mod b q = q div b k++ return (a_k-1, a_k-2,..., a_1, a_0)} 3  ALGORITHM 1.2.2 | Converting from Base-8 or Base-16 to Base-2 Suppose n ∈ Z+ with octal or hexadecimal expansion (ak−1 , ak−2 ,... , a1 , a0 )b. 1. If b = 8: Convert each digit ai to a binary block of three digits. If b = 16: Convert each digit ai to a binary block of four digits. 2. Concatenate the blocks. Example 4. Find the binary representation of each number. (a) (765)8 (b) (A8D)16 Extra Practice: Prove the correctness of this Algorithm 2 for the case b = 8. 4 Integer Operations Addition MOTIVATION: Consider adding 9 + 5. ALGORITHM 1.2.3 | Addition of Binary Numbers Suppose k ∈ Z+ , and a = (ak−1 , ak−2 ,... , a1 , a0 )2 and u = (uk−1 , uk−2 ,... , u1 , u0 )2 are the binary representations of decimal numbers a and u. Then, the sum a + u can be found by the following steps. 1. For i = 0, 1,... , k − 1: Perform ai +2 ui plus any carry from the i − 1-st step. PSEUDOCODE 1.2.3 | Adding two numbers with base 2-expansions INPUT: a = (ak−1 , ak−2 ,... , a1 , a0 )2 , u = (uk−1 , uk−2 ,... , u1 , u0 )2 OUTPUT: (sk−1 , sk−2 ,... , s1 , s0 )2 sum of a + u binaryAdd(a, u): c = 0 #carry for i in 0:k-1: s i = (a i + u i + c) mod 2 c = (a i + u i + c) div 2 sk = c return (s k, s k-1, s k-2,..., s 1, s 0) 5 Multiplication MOTIVATION: Consider multiplying 11 × 3. 6 ALGORITHM 1.2.4 | Multiplying two numbers with base 2-expansions Suppose k, n ∈ Z+ , and a = (ak−1 , ak−2 ,... , a1 , a0 )2 and u = (un−1 , un−2 ,... , u1 , u0 )2 are the binary representations of decimal numbers a and u. Then, the product a × u can be found by the following steps. 1. Initialize a empty container to store the partial products. 2. For i = 0, 1,... , n − 1: if ui is 1, then store the partial product (ak−1 , ak−2 ,... , a1 , a0 , 0, 0,... , 0)2 | {z } i−many 0’s 3. Add the partial products and return the sum. PSEUDOCODE 1.2.4 | Multiplying two numbers with base 2-expansions INPUT: a = (an−1 , an−2 ,... , a1 , a0 )2 , u = (uk−1 , uk−2 ,... , u1 , u0 )2 OUTPUT: (sq−1 , sq−2 ,... , s1 , s0 )2 product of a · u binaryProduct(a, u): c = [] # initialize empty container to store partial products s = 0 for i = 0:k-1: if u_i = 1: x = a + "i zeros appended to the end" c.append(x) for j = 0:len(c): s = binaryAdd(s, c_j) return s 7 Modular Exponentiation MOTIVATION: Try finding 7345 mod 5 with the aid of a traditional calculator. Odds are you will come across an overflow error. Why does this happen? IDEA: 1. Find the binary expansion of 345. i 2. Compute the partial modulo operations defined by pi = 72 mod 5 3. Use Corollary 4.1.4 a · b mod m = (a mod m)(b mod m) mod m 8 +26 +24 +23 +20 to compute 7345 mod 5 = 72 mod 5. Example 5. Compute 7345 mod 5. 8 9 10 ALGORITHM 1.2.5 | Modular Exponentiation GOAL: bn mod m, when n is large. 1. Find the binary expansion of n, n = ak−1 2k−1 + · · · + a1 21 + a0 20. 2. Initialize x−1 = 1 3. Initialize p0 = b mod m 4. For i = 0, 1,... , k − 1: i. If ai = 1: Update the current product xi = pi · xi−1 mod m ii. Compute the partial product pi+1 = p2i mod m. 5. Return x which will equal bn mod m PSEUDOCODE 1.2.5 | Modular Exponentiation INPUT: b-integer, m-integer, n = (ak−1 , ak−2 ,... , a1 , a0 )2 OUTPUT: bn mod m modExp(b,n, m): x = 1 # this will hold the final product 0 p = b mod m # first power corresponding to b2 mod m for i = 0:k-1: if a i = 1: x = (x * p) mod m p = (p * p) mod m return x 11 Example 6. Trace through the algorithm to compute 7345 mod 5. 12 13  Relevant Exercises Problems are from Discrete Mathematics and Applications 8th. edition by K. Rosen. 1. (4.2.1 - 4.2.13 odd) 2. (4.2.21) 3. (4.2.25) 4. (4.2.27) 14