C960 Discrete Math II Unit 2 Number Theory and Cryptography (Flashcards with solutions) Exam

C960 Discrete Math II Unit 2 Number Theory and Cryptography (Flashcards with solutions) Exam Questions with Answers 2.3.3: Computing div and mod. -10 mod 5 - Correct Answers: 0 Starting with -10, when 5 is added 2 times to -10, the result is 0, which is in the range from 0 through 4.-10 + 2 · 5 = 0-10 = -2 · 5 + 0 2.3.3: Computing div and mod. -13 mod 6 - Correct Answers: 5 Starting with -13, when 6 is added 3 times to -13, the result is 5, which is in the range from 0 through 5.-13 + 3 · 6 = 5-13 = -3 · 6 + 5 2.3.3: Computing div and mod. -13 div 6 - Correct Answers: -3 Starting with -13, 6 is added 3 times until the result yields a number in the range from 0 through 5.-13 + 3 · 6 = 5-13 = -3 · 6 + 5 2.3.1: Compute divisor and modulus. 344 mod 5 - Correct Answers: 4 344 = 68·5 + 4, so 344 mod 5 = 4. 2.3.1: Compute divisor and modulus. 344 div 5 - Correct Answers: 68 344 = 68·5 + 4, so 344 div 5 = 68. 2.3.1: Compute divisor and modulus. (-215) mod 7 - Correct Answers: 2 (−215) = (−31)·7 + 2, so (−215) mod 7 = 2. 2.3.1: Compute divisor and modulus. (-215) div 7 - Correct Answers: -31 (−215) = (−31)·7 + 2, so (−215) div 7 = −31. Lesson 2.5.2 Computing arithmetic expressions modulo n. (43¹⁷+32*130) mod n 7 - Correct Answers: 4 The value of the expression (43¹⁷+32*139) mod 7 does not change if 43, 32, and 139 are replaced by 43 mod 7, 32 mod 7, and 139 mod 7. The value of the expression is therefore (1¹⁷+4*6) mod 7. (43¹⁷+32*139) mod 7 is equal to (1+24) mod 7=25 mod 7=4 2.5.3: Computing arithmetic expressions modulo n. (651²³ + 17) mod 10 - Correct Answers: 8 651 mod 10 = 1. Therefore, (651²³ + 17) mod 10 = (1²³ + 17) mod 10 = (1 + 17) mod 10 = 8 2.5.1: Compute expression using modular arithmetic. [(47 mod 6) + (36 mod 6)] mod 6 - Correct Answers: 5 2.5.1: Compute expression using modular arithmetic [(34 mod 6 )(72 mod 6)] mod 6 - Correct Answers: 0 2.5.1: Compute expression using modular arithmetic. [27 · 70] mod 7 - Correct Answers: 0 2.5.1: Compute expression using modular arithmetic [26¹⁹ + 13] mod 5 - Correct Answers: 4 2.5.1: Computing using modular arithmetic 38⁷ mod 3 - Correct Answers: 2 387 mod 3 = (38 mod 3)7 mod 3 = (27) mod 3 = 128 mod 3 = 2 2.5.1: Computing using modular arithmetic (72 · (−65) + 211) mod 7 - Correct Answers: 4 (72 · (−65) + 211) mod 7 = ((72 mod 7) · (−65 mod 7) + (211 mod 7)) mod 7 = (2 · 5 + 1) mod 7 = 11 mod 7 = 4 2.5.1: Computing using modular arithmetic (77 · (−65) + 147) mod 7 - Correct Answers: 0 (77 · (−65) + 147) mod 7 = ((77 mod 7) · (−65) + (147 mod 7)) mod 7 = (0 · (−65) + 0) mod 7 = 0 2.5.2: Congruence modulo n Group the numbers from the given set into classes of congruence. That is, put two numbers in the same group if they are equivalent modulo 11. {−57, 17, 108, 0, −110, −93, 1111, 130, 232} - Correct Answers: Congruent to 0 modulo 11: 0, -110, 1111 Congruent to 1 modulo 11: 232 Congruent to 6 modulo 11: 17, -93 Congruent to 9 modulo 11: -57, 108, 130 2.5.2: Congruence modulo n Group the numbers from the given set into classes of congruence. That is, put two numbers in the same group if they are equivalent modulo 13. {−63, -54, -41, 11, 13, 76, 80, 130, 132, 137} - Correct Answers: Congruent to 0 modulo 13: 13, 130 Congruent to 2 modulo 13: -63, 80, 132 Congruent to 7 modulo 13: 137 Congruent to 11 modulo 13: -54, -41, 11, 7 2.7.1: Prime factorizations What is the prime factorization for 48 in exponential form? - Correct Answers: 2⁴ * 3 = 48. Also, 2 and 3 are both prime numbers. 2.7.1: Prime factorizations What is the prime factorization for 31? - Correct Answers: 31 31 is a prime number, so its prime factorization is itself. 2.7.1: Prime factorizations. In which prime factorization are the prime factors listed in non-decreasing order? 2·7·13·11 2·7·11·13 7·2·11·13 - Correct Answers: 2·7·11·13 Each prime factor is greater than or equal to the one that precedes it. 2.8.1: GCD and LCM from prime factorizations. LCM(924, 33075) in exponential form 924 = 2² * 3¹ * 5⁰ * 7¹ * 11¹ 33075 = 2⁰ * 3³ * 5² * 7² * 11⁰ - Correct Answers: 2² * 3³ * 5² * 7² * 11¹ = 1455300 The LCM is obtained by taking the larger of the exponents of each prime from 924 and 33075, which results in LCM(924,33075) = 2² * 3³ * 5² * 7² * 11¹ = 1455300 2.8.1: GCD and LCM from prime factorizations. GCD(924, 33075) in exponential form 924 = 2² * 3¹ * 5⁰ * 7¹ * 11¹ 33075 = 2⁰ * 3³ * 5² * 7² * 11⁰ - Correct Answers: 2⁰ * 3¹ * 5⁰ * 7¹ * 11⁰ = 21 The GCD is obtained by taking the smaller of the exponents of each prime from 924 and 33075, which results in GCD(924, 33075) = 2⁰ * 3¹ * 5⁰ * 7¹ * 11⁰ = 21 2.8.2: Finding expressions for the GCD and LCM from prime factorizations. 315 = 3² * 5 * 7 550 = 2 * 5² * 11 LCM(315, 550) in exponential form - Correct Answers: 2 * 3² * 5² * 7 * 11 315 = 2⁰·3²·5¹·7¹ 550 = 2¹·3⁰·5²·7⁰·11¹ GCD(550, 315) = ₂max{0,1}·₃max{0, 1}·₅max{2,0}·₇max{1,0}·₁₁max{0,1} 2.8.2: Finding expressions for the GCD and LCM from prime factorizations. 147 = 3 * 7² 315 = 3² * 5 * 7 GCD(147,315) in exponential form - Correct Answers: 3 * 7 147 = 3¹ * 5⁰ * 7² 315 = 3² * 5¹ * 7¹ GCD(147, 315) = ₃min{1,2}·₅min{0,1}·₇min{2,1} = 3 · 7 2.8.2: Finding expressions for the GCD and LCM from prime factorizations. 315 = 3² * 5 * 7 550 = 2 * 5² * 11 GCD(315, 550) in exponential form - Correct Answers: 5 315 = 2⁰ * 3² * 5¹ *7¹ * 11⁰ 550 = 2¹ * 3⁰ * 5² * 7⁰ * 11¹ GCD(550, 315) =₂min{0,1}·₃min{0, 1}·₅min{1,2}·₇min{1,0}·₁₁min{0,1} 2.8.2: Finding expressions for the GCD and LCM from prime factorizations. 147 = 3 * 7² 315 = 3² * 5 * 7 LCM(147, 315) in exponential form - Correct Answers: 3² * 5 * 7² 147 = 3¹ * 5⁰ * 7² 315 = 3² * 5¹ * 7¹ ₃max{1,2}·₅max{0,1}·₇max{2,1} = 3 · 7 2.8.1: Computing using prime factorizations 1078 = 2 * 7² * 11 25480 = 2³ * 5 * 7² * 13 GCD(1078, 25480) in exponential form - Correct Answers: 2 * 7² = 98 2.8.1: Computing using prime factorizations 175 = 5² * 7 25480 = 2³ * 5 * 7² * 13 LCM(175 , 25480) in exponential form - Correct Answers: 2³ * 5² * 7² * 13 = 127400 2.8.1: Computing using prime factorizations 175 = 5² * 7 25480 = 2³ * 5 * 7² * 13 175 * 25480 in exponential form - Correct Answers: 2³ * 5³ * 7³ * 13 = 4459000 2.8.1: Computing using prime factorizations 25480 = 2³ * 5 * 7² * 13 140 = 2² * 5 * 7 25480/140 in exponential form - Correct Answers: 2 * 7 * 13 = 182 2.9.1: Brute force factoring Suppose that the slightly better brute force algorithm for factoring is given the number 653117 as input. How many numbers would the algorithm have to check to either find a factor or determine that the input is prime? (653117 happens to be a prime number). - Correct Answers: 807 The algorithm can stop checking numbers when it reaches x=⌊653117⌋=808. Since 653117 is prime, the algorithm will not find a factor before reaching x = 808. There are 807 numbers in the range 2 through 808 that are checked by the algorithm. 2.9.2: Finding a random number Consider a random integer selected from the range from 2 to 1,000,000,000,000. Approximately, what are the chances that the selected number is prime? - Correct Answers: 0.036 The chances the selected number is prime is 1/ln(1,000,000,000,000) which is approximately 0.036. 2.9.1: Estimating the number of primes Use the prime number theorem to give an approximation for the number of prime numbers in the range 2 through 10,000,000 - Correct Answers: 620421 10,000,000 = 10⁷. The number of prime numbers in the range 2 through 10⁷ is approximately 10⁷/ln(10⁷) ≈ 620421. 2.10.2: Euclid's Algorithm Consider an Euclid's algorithm with input integers y = 156 and x = 54 What is the value of r at the beginning of the first iteration of the loop in Euclid's algorithm? - Correct Answers: 48 r = 156 mod 54 = 48 2.10.2: Euclid's Algorithm Consider an Euclid's algorithm with input integers y = 156 and x = 54 What is the value of r at the beginning of the second iteration of the loop in Euclid's algorithm? - Correct Answers: 6 x = 54, y = 48, r = 54 mod 48 = 6 2.10.2: Euclid's Algorithm Consider an Euclid's algorithm with input integers y = 156 and x = 54 What is the value of r after the second iteration of the loop in Euclid's algorithm? - Correct Answers: 0 x = 48, y = 6, r = 48 mod 6 = 0 2.10.2: Euclid's Algorithm Consider an Euclid's algorithm with input integers y = 156 and x = 54 How many times does the loop in Euclid's algorithm execute on input 156 and 54? - Correct Answers: 2 After the second iteration of the loop, r = 0, so the loop executes two times 2.10.2: Euclid's Algorithm Consider an Euclid's algorithm with input integers y = 156 and x = 54 What is the GCD of 156 and 54? - Correct Answers: 6 After the last iteration of the loop, y = 54, x = 6, and r = 0. Therefore the GCD is x = 6. 2.11.1: The Extended Euclidean Algorithm Write GCD of 675 and 210 as a linear combination of those two numbers - Correct Answers: GCD(675, 210) = 15 = 5 * 675 - 16 * 210 2.11.2: Extended Euclidean Algorithm Write GCD of 225 and 60 as a linear combination of those two numbers 15 = 60 - (A * 45) 45 = 225 - (B * 60) What's A? - Correct Answers: 1 A = 60 div 45 = 1 2.11.2: Extended Euclidean Algorithm Write GCD of 225 and 60 as a linear combination of those two numbers 15 = 60 - (A * 45) 45 = 225 - (B * 60) What's B? - Correct Answers: 3 B = 225 div 60 = 3 2.11.2: Extended Euclidean Algorithm The two linear equations above can be used to express GCD(225, 60) as a linear combination of 225 and 60: 15 = C · 225 + D · 60 What is the correct value for C? - Correct Answers: -1 15 = 60 - 45. 45 = 225 - (3 · 60) The second equation replaces 45 in the first equation with a linear combination of 225 and 60.15 = 60 - (225 - 3 · 60) = 4·60 - 225The coefficient of 225 is -1. 2.11.2: Extended Euclidean Algorithm The two linear equations above can be used to express GCD(225, 60) as a linear combination of 225 and 60: 15 = C · 225 + D · 60 What is the correct value for D? - Correct Answers: 4 15 = 60 - 45 45 = 225 - (3 · 60) The second equation replaces 45 in the first equation with a linear combination of 225 and 60. 15 = 60 - (225 - 3·60) = 4·60 - 225. The coefficient of 60 is 4. 2.11.1: Euclid Algorithm Fill in the missing numbers of the sequence generated by Euclid's algorithm on inputs 94 and 16. GCD(94, 16) yields sequence: 94 16 ? ? 0 Solve ? - Correct Answers: 14, 2 94 mod 16 = 14 16 mod 14 = 2 2.11.1: Euclid Algorithm Enter the number to complete the linear combination. GCD(87, 18) yields sequence: 15 = 87 - ? * 18 3 = 18 - ? * 15 Solve ? - Correct Answers: 4, 1 87 div 18 = 4 18 div 15 =1 2.11.1: Euclid Algorithm Enter the number to complete the linear combination. GCD(50, 44) yields sequence: 50 44 6 2 0 6 = 50 − 1 ⋅ 44 2 = 44 − 7 ⋅ 6 After substitution: 2=44 − 7 ⋅ (50 − 1 ⋅ 44) 2 = ? ⋅ 50 + ? ⋅44 Solve ? - Correct Answers: -7, 8 2.11.1: Applying the Euclidean Algorithm and the Extended Euclidean Algorithm Find the GCD of the two numbers, and express the GCD as a linear combination of the two numbers. 56 and 42 - Correct Answers: GCD(56, 42) = 14 = 56 - 42 56 42 14 0 56 mod 42 = 14 42 mod 14 = 0 GCD(56, 42) = 14 The equation is: 14 = 56 - (56 div 42)·42 = 56 - 42 GCD(56, 42) = 14 = 56 - 42 2.11.1: Applying the Euclidean Algorithm and the Extended Euclidean Algorithm Find the GCD of the two numbers, and express the GCD as a linear combination of the two numbers. 81 and 60 - Correct Answers: GCD(81, 60) = 3 = 3·81 - 4·60 0 81 mod 60 = 21 60 mod 21 = 18 21 mod 18 = 3 18 mod 3 = 0 The equations for substitution are: 3 = 21 - (21 div 18)18 = 21 -18 18 = 60 - (60 div 21)21 = 60 - 2·21 21 = 81 - (81 div 60)60 = 81 - 60 Substitute (60 - 2·21) for 18 into the equation 3 = 21 -18 3 = 21 - (60 - 2·21) = 3·21 - 60 Substitute (81 - 60) for 21 into the equation 3 = 3·21 - 60 3 = 3·(81 - 60) - 60 = 3·81 - 4·60 GCD(81, 60) = 3 = 3·81 - 4·60 2.12.1: Multiplicative inverses mod n ? * 8 mod 11 = 1 - Correct Answers: 7 7 · 8 mod 11 = 56 mod 11 = 1 2.12.1: Multiplicative inverses mod n ? * 9 mod 11 = 1 - Correct Answers: 5 5 · 9 mod 11 = 45 mod 11 = 1 2.12.1: Multiplicative inverses mod n ? * 10 mod 11 = 1 - Correct Answers: 10 10 · 10 mod 11 = 100 mod 11 = 1 2.12.2: Find the multiplicative inverse using the results of the Extended Euclidean Algorithm. Euclid's algorithm returnsGCD(61, 54) = 1 = 26 · 54 - 23 · 61 What is the multiplicative inverse of 54 mod 61? - Correct Answers: 26 26 is the coefficient of 54 in the equation:1 = 26 · 54 - 23 · 61The inverse of 54 mod 61 is (c mod 61), where c is the coefficient of 54:26 mod 61 = 26 2.12.2: Find the multiplicative inverse using the results of the Extended Euclid's algorithm returnsGCD(14, 33) = 1 = 3 · 33 - 7 · 14.What is the multiplicative inverse of 14 in Z₃₃ ? - Correct Answers: 26 -7 is the coefficient of 14 in the equation:1 = 3 · 33 - 7 · 14The inverse of 14 in Z₃₃ is (c mod 33), where c is the coefficient of 14:-7 mod 33 = 26 2.12.1: Computing a multiplicative inverse For each x and n, find the multiplicative inverse mod n of x. Your answer should be an integer s in the range 0 through n - 1. Check your solution by verifying that sx mod n = 1 x = 52, n = 77 - Correct Answers: 40 77 mod 52 = 25 52 mod 25 = 2 25 mod 2 = 1 The equations for substitution are: 1 = 25 - 12·2 2 = 52 - 2·25 25 = 77 - 52 Substitute (52 - 2·25) for 2 into the equation 1 = 25 - 12·2 1 = 25 - 12·(52 - 2·25) = 25·25 - 12·52 Substitute (77 - 52) for 25 into the equation 1 = 25·25 - 12·52 1 = 25·(77 - 52) - 12·52 = 25·77 - 37·52 GCD(77, 52) = 1 = 25·77 - 37·52 The coefficient of 52 in the equation above is -37. The multiplicative inverse of 52 mod 77 is (-37 mod 77) = 40. Check: 52·40 mod 77 = 2080 mod 77 = 1 2.12.1: Computing a multiplicative inverse For each x and n, find the multiplicative inverse mod n of x. Your answer should be an integer s in the range 0 through n - 1. Check your solution by verifying that sx mod n = 1 x = 77, n = 52 - Correct Answers: 25 GCD(77, 52) = 1 = 25·77 - 37·52 The coefficient of 77 in the equation above is 25. The multiplicative inverse of 77 mod 52 is (25 mod 52) = 25. Check: 77·25 mod 52 = 1925 mod 52 = 1 2.12.1: Computing a multiplicative inverse For each x and n, find the multiplicative inverse mod n of x. Your answer should be an integer s in the range 0 through n - 1. Check your solution by verifying that sx mod n = 1 x = 53, n = 71 - Correct Answers: 67 71 mod 53 = 18 53 mod 18 = 17 18 mod 17 = 1 The equations for substitution are: 1 = 18 - 17 17 = 53 - 2·18 18 = 71 - 53 Substitute (53 - 2·18) for 17 into the equation 1 = 18 - 17 1 = 18 - (53 - 2·18) = 3·18 - 53 Substitute (71 - 53) for 18 into the equation 1 = 3·18 - 53 1 = 3·(71 - 53) - 53 = 3·71 - 4·53 GCD(71, 53) = 1 = 3·71 - 4·53 The coefficient of 53 in the equation above is -4. The multiplicative inverse of 53 mod 71 is (-4 mod 71) = 67. Check: 53·67 mod 71 = 3551 mod 71 = 1 2.14.1: Converting a number base b into its decimal expansion (2012)₃ - Correct Answers: 59 (2 * 3³) + (0 * 3²) + (1 * 3¹) + (2 * 3⁰) = 59 2.14.2: Converting to decimal expansion. (10)₁₇ - Correct Answers: 17 (1 * 17¹) + (0 * 17⁰) 2.14.2: Converting to decimal expansion. (1100110)₂ - Correct Answers: 102 2⁶ + 2⁵ + 2² + 2¹ = 102 2.14.2: Converting to decimal expansion (346)₇ - Correct Answers: 181 (3 * 7²) + (4 * 7¹) + ( 6 * 7⁰) = 181 2.14.2: Converting to decimal expansion. (120121)₃ - Correct Answers: 541 1·3⁵ + 2·3⁴ + 1·3² + 2·3¹ + 1·3⁰ = 243 + 2·81 + 9 + 2·3 + 1 = 421 2.14.2: Converting to decimal expansion. (50020)₈ - Correct Answers: 20496 (5·8⁴) + (2·8¹) = 20496 2.15.1: Hexadecimal expansions What is the decimal expansion of (2F)₁₆? - Correct Answers: 47 2 · 16¹ + 15 · 16⁰ = 47 2.15.1: Hexadecimal expansions What is the binary expansion of (2F)₁₆? Omit the leading zeroes in your answer. - Correct Answers: 101111 0010 corresponds to 2 and 1111 corresponds to F. Put 0010 and 1111 together to get and drop the leading zeroes to get 101111. 2.15.1: Hexadecimal expansions What is the hexadecimal number that corresponds to 1011101? - Correct Answers: 5D The rightmost four bits, 1101, corresponds to D. The remaining bits on the left are 101. Add a leading zero to 101 on the left to get 0101 which corresponds to 5. Therefore 1011101 corresponds to a hexadecimal expansion of 5D. 2.15.1: Converting from hex to binary Give a binary representation for each number given below in hex. Drop the leading zeroes in your binary representation. (A3)₁₆ - Correct Answers: (A)₁₆ = (1010)₂ (3)₁₆ = (0011)₂ 2.15.1: Converting from hex to binary (1FC)₁₆ - Correct Answers: (1)1₁₆ = (0001)₂ (F)₁₆ = (1111)₂ (C)₁₆ = (1100)₂ 2.15.1: Converting from hex to binary (2A0B)₁₆ - Correct Answers: (2)₁₆= (0010)₂ (A)₁₆ = (1010)₂ (0)₁₆ = (0000)₂ (B)₁₆ = (1011)₂ 2.15.2: Converting from binary to hex Give a hexadecimal representation for each number given below in binary. 101 - Correct Answers: 5 2.15.2: Converting from binary to hex Give a hexadecimal representation for each number given below in binary. 11101 - Correct Answers: 1D 2.15.2: Converting from binary to hex Give a hexadecimal representation for each number given below in binary. - Correct Answers: 2DA15 2.16.1: Converting a decimal number to its base b expansion Find the base 6 expansion of 67 - Correct Answers: 151 67 div 6 = 11 67 mod 6 = 1 11 div 6 = 1 11 mod 6 = 5 1 div 6 = 0 1 mod 6 = 1 2.16.2: Conversion to expansion base b Find the expansion base 5 of 57 - Correct Answers: 212 57 mod 5 = 2; Rightmost digit is 2. 57 div 5 = 11 11 mod 5 = 1; Next digit to the left is 1. 11 div 5 = 2 2 mod 5 = 2; Next digit to the left is 2. 2 div 5 = 0 2.16.2: Conversion to expansion base b Find the expansion base 7 of 52 - Correct Answers: 103 52 mod 7 = 3; Rightmost digit is 3. 52 div 7 = 7 7 mod 7 = 0; Next digit to the left is 0. 7 div 7 = 1 1 mod 7 = 1; Next digit to the left is 1. 1 div 7 = 0 2.16.2: Conversion to expansion base b Find the binary of 21 - Correct Answers: 10101 21 mod 2 = 1; Rightmost bit is 1. 21 div 2 = 10 10 mod 2 = 0; Next bit to the left is 0. 10 div 2 = 5 5 mod 2 = 1; Next bit to the left is 1. 5 div 2 = 2 2 mod 2 = 0; Next bit to the left is 0. 2 div 2 = 1 1 mod 2 = 1; Next bit to the left is 1. 1 div 2 = 0 2.16.3: Number of digits base b How many digits are required to express the base 7 expansion of 2401? - Correct Answers: Log₇ 2402 n = 2401 and b = 7. n + 1 2.16.3: Number of digits base b How many digits are required to express the base 8 expansion of 9? - Correct Answers: log₈ 10 n = 9 and b = 8. n + 1 2.16.3: Number of digits base b How many digits are required to express the binary expansion of 2⁵⁵? - Correct Answers: 56 The binary expansion of 2⁵⁵ is a 1 followed by 55 0's. 2.16.3: Number of digits base b How many digits are required to express the base 8 expansion of 8⁷ - 1? - Correct Answers: 7 n = 8⁷ - 1 and b = 8. The base 8 expansion of 8⁷ - 1 is (7777777)₈. 2.16.1: Converting from decimal to non-decimal bases A number N is given below in decimal format. Compute the representation of N in the indicated base N = 217, binary - Correct Answers: 217 mod 2 = 1 217 div 2 = 108 108 mod 2 = 0 108 div 2 = 54 54 mod 2 = 0 54 div 2 = 27 27 mod 2 = 1 27 div 2 = 13 13 mod 2 = 1 13 div 2 = 6 6 mod 2 = 0 6 div 2 = 3 3 mod 2 = 1 3 div 2 = 1 1 mod 2 = 1 1 div 2 = 0 217 = ()₂ 2.16.1: Converting from decimal to non-decimal bases A number N is given below in decimal format. Compute the representation of N in the indicated base N = 344, hex - Correct Answers: (158)₁₆ 344 mod 16 = 8 344 div 16 = 21 21 mod 16 = 5 21 div 16 = 1 1 mod 16 = 1 1 div 16 = 0 344 = (158)₁₆ 2.16.1: Converting from decimal to non-decimal bases A number N is given below in decimal format. Compute the representation of N in the indicated base N =136, base 7 - Correct Answers: (253)₇ 136 mod 7 = 3 136 div 7 = 19 19 mod 7 = 5 19 div 7 = 2 2 mod 7 = 2 2 div 7 = 0 136 = (253)₇ 2.18.1: An illustration of fast integer exponentiation Compute 7¹¹ - Correct Answers: 7⁸ * 7² * 7¹ 3210 Binary expansion of 11 = (1011)₂ 7^[(1 * 2³) + (0 * 2²) + (1 * 2¹) + (1 * 2⁰)] X 2.18.2: Expressing exponents as products of terms whose exponents are powers of 2. 7 = 2² + 2¹ + 2⁰ Which expression is equivalent to 5⁷? - Correct Answers: 5^2^2 * 5^2^1 * 5^2^0 5⁴⁺²⁺¹ = 5⁷ 2.18.2: Expressing exponents as products of terms whose exponents are powers of 2 The binary representation of 25 is 11001. Which expression is equivalent to b^25? - Correct Answers: b^2^4 * b^2^3 * b^2^0 25 = 1·2⁴ + 1·2³ + 0·2² + 0·2¹ + 1·20 = 2⁴ + 2³ + 2⁰ 2.18.2: Expressing exponents as products of terms whose exponents are powers of 2 The binary representation of 18 is 10010. Which expression is equivalent to b^18? - Correct Answers: b^2^4 * b^2^1 18 = 1·2⁴ + 0·2³ + 0·2² + 1·2¹ + 0·2₀ = 2⁴ + 2¹ 2.18.1: Expressing exponents as a product of terms whose exponents are powers of 2 For each value of y, express by as a product of terms of the form b^2^j, where j is a non-negative integer. y = 53 - Correct Answers: b⁵³ = b^2^5 * b^2^4 * b+2^2 * b^2^0 53 = (110101)₂ 53 = 2⁵ + 2⁴ + 2² + 2⁰ 2.18.1: Expressing exponents as a product of terms whose exponents are powers of 2 For each value of y, express by as a product of terms of the form b^2^j, where j is a non-negative integer. y = 66 - Correct Answers: b^2^6 * b^2^1 66 = (1000010)₂ 66 = 2⁶ + 2¹ 2.18.3: An execution of the iterative algorithm for fast exponentiation Consider the algorithm for iterative fast exponentiation on input x = 3 and y = 13 What is the binary representation of 13? - Correct Answers: 1101 2.18.3: An execution of the iterative algorithm for fast exponentiation Consider the algorithm for iterative fast exponentiation on input x = 3 and y = 13 The loop executes 4 times on input y = 13. Which best describes the state of the algorithm at the beginning of each iteration of the loop? - Correct Answers: Iteration 1: (r mod 2) = 1 Iteration 2: (r mod 2) = 0 Iteration 3: (r mod 2) = 1 Iteration 4: (r mod 2) = 1 The value of (r mod 2) in each iteration are the bits in the binary representation of y in reverse order. 2.18.3: An execution of the iterative algorithm for fast exponentiation Consider the algorithm for iterative fast exponentiation on input x = 3 and y = 13 The loop executes 4 times on input y = 13. Which best describes the state of the algorithm at the beginning of each iteration of the loop? - Correct Answers: Iteration 1: s = x Iteration 2: s = x² Iteration 3: s = x⁴ Iteration 4: s = x⁸ The variable s is squared in each iteration, so if s is a power of x, the exponent doubles each iteration. 2.18.3: An execution of the iterative algorithm for fast exponentiation Consider the algorithm for iterative fast exponentiation on input x = 3 and y = 13 What is the value of the output p at the end of the algorithm? - Correct Answers: x * x⁴ * x⁸ The initial value for the variable is p = 1. p is multiplied by the current value of s in each iteration in which (r mod 2) = 1. (r mod 2) = 1 during iterations 1, 3, and 4. Therefore the output is x · x⁴ · x⁸. 2.19.1: An execution of the iterative algorithm for fast modular exponentiation. Consider the algorithm for iterative fast exponentiation on input x = 3, y = 13, and n = 7. The mod operations are not applied to the variable r. For exponent y = 13, (r mod 2) = 1 at the beginning of iterations 1, 3, and 4. At the beginning of the first iteration s = x = 3. What is the value of s at the beginning of the second iteration? - Correct Answers: 2 During the first iteration, s := s² mod 7 = 3² mod 7 = 2. 2.19.1: An execution of the iterative algorithm for fast modular exponentiation. Consider the algorithm for iterative fast exponentiation on input x = 3, y = 13, and n = 7. The mod operations are not applied to the variable r. For exponent y = 13, (r mod 2) = 1 at the beginning of iterations 1, 3, and 4. What is the value of s at the beginning of the third iteration? - Correct Answers: 4 At the beginning of the second iteration, s = 2.During the second iteration, s := s² mod 7 = 2² mod 7 = 4 2.19.1: An execution of the iterative algorithm for fast modular exponentiation. Consider the algorithm for iterative fast exponentiation on input x = 3, y = 13, and n = 7. The mod operations are not applied to the variable r. For exponent y = 13, (r mod 2) = 1 at the beginning of iterations 1, 3, and 4. What is the value of s at the beginning of the fourth iteration? - Correct Answers: 2 At the beginning of the third iteration, s = 4. During the third iteration, s := s² mod 7 = 4² mod 7 = 2. 2.19.1: An execution of the iterative algorithm for fast modular exponentiation. Consider the algorithm for iterative fast exponentiation on input x = 3, y = 13, and n = 7. The mod operations are not applied to the variable r. For exponent y = 13, (r mod 2) = 1 at the beginning of iterations 1, 3, and 4. Starting with p = 1, the value for p is multiplied by s mod 7 in each iteration in which (r mod 2) = 1. What is the final value for p? - Correct Answers: 3 (r mod 2) = 1 during iterations 1, 3, and 4. The value of s at the beginning of iterations 1, 3, and 4 are 3, 4, and 2. The final value for p is 3 · 4 · 2 mod 7 = 24 mod 7 = 3. 2.19.1: Fast exponentiation 5³⁵ mod 11 - Correct Answers: 1 Refer to book for solution 2.19.1: Fast exponentiation 5⁶⁸ mod 7 - Correct Answers: 4 Refer to book for solution 2.19.1: Fast exponentiation 11²⁰ in Z₃₃ - Correct Answers: 22 Refer to book for solution 2.22.1: Converting a text message into a numerical message. Text message: A T T A C K _ A T _ D A W N What is the numeric message? - Correct Answers: 1,20,20,01,03,11,27,01,20,27,04,01,23,14 2.22.1: Converting a text message into a numerical message Numeric message: 2 0 1 1 4 1 1 2 7 0 2 0 1 1 2 0 1 1 4 0 3 0 5 What is the text message? - Correct Answers: BANK_BALANCE 2.22.2: Sending an encrypted text message Numeric Message: What is the text message? - Correct Answers: MEET AT DAWN 2.22.3: Translating text to numerical messages Text Message: ONE IF BY LAND What is the numeric message? - Correct Answers: 2.22.3: Translating text to numerical messages Text Message: CANCEL ATTACK What is the numeric message? - Correct Answers: 2.22.4: A simple cryptosystem. Alice's message to Bob is 2317. The secret key is 2191, and N = 3391 What is the encrypted message? - Correct Answers: 1117 (2317+2191) mod 3391=1117 2.22.4: A simple cryptosystem. The secret key is 2191, and N = 3391. Alice encrypts the message: 1117 Alice sends 1117 to Bob who decrypts the message. What is the decrypted message? - Correct Answers: 2317 (1117−2191) mod 3391=2317. 2.22.5: Simple encryption scheme let N = 79 and k = 43 Encrypt the plaintext m = 62. - Correct Answers: 26 c = (m + k) mod N = (62 + 43) mod 79 = 26. 2.22.5: Simple encryption scheme let N = 79 and k = 43 decrypt the ciphertext c = 26 - Correct Answers: 62 m = (c - k) mod N = (26 - 43) mod 79 = 62.Note that 62 was the original plaintext from the previous question, and 26 was the ciphertext. 2.22.5: Simple encryption scheme let N = 79 and k = 43 Decrypt the ciphertext c = 12 - Correct Answers: 48 m = (c - k) mod N = (12 - 43) mod 79 = 48. 2.22.1: Converting text to numerical messages One way to convert text messages to numerical values is to use the ASCII (American Standard Code for Information Interchange) character encoding scheme. In ASCII, a character is represented by a byte (8 bits) code. To convert a text message to a numerical value, concatenate together the codes for each character in the message. The resulting binary string is interpreted as an integer written in binary. The table below gives the ASCII codes for a few characters. Use the table to convert each word into an integer. Charcter ASCIIcode P s w d I N Pswd - Correct Answers: 1349744484 Pswd → ()₂ = 1349744484 2.22.1: Converting text to numerical messages One way to convert text messages to numerical values is to use the ASCII (American Standard Code for Information Interchange) character encoding scheme. In ASCII, a character is represented by a byte (8 bits) code. To convert a text message to a numerical value, concatenate together the codes for each character in the message. The resulting binary string is interpreted as an integer written in binary. The table below gives the ASCII codes for a few characters. Use the table to convert each word into an integer. Charcter ASCIIcode P s w d I N PIN - Correct Answers: 5261646 PIN → (1010000)₂ = 5261646 2.22.2: Deducing the key from a single (plaintext, ciphertext) pair Suppose Alice and Bob use the simple encryption scheme in which c = (m + k) mod N and m = (c − k) mod N. Suppose that Eve knows that N = 4657. Suppose that she also manages to learn that the message m corresponding to c = 1322 is 3411. Can she infer the value for k? What is k? - Correct Answers: 2568 If c = (m + k) mod N, then k = (c - m) mod N k = () mod 4657 = -2089 mod 4657 = 2568 2.23.2: Preparation of public and private keys in RSA Two primes: p = 31, q = 59 What is the public keys? - Correct Answers: N = 1829 e = 859 N = p ⋅ q = 31 ⋅ 59 = 1829 Phi = (p - 1) ⋅ (q - 1) = 30 ⋅ 58 = 1740 Guess e = 859 and check: gcd(859 , 1740 ) = 1 2.23.2: Preparation of public and private keys in RSA Two primes: p = 31, q = 59 What is the private key? - Correct Answers: d = 79 N = p ⋅ q = 31 ⋅ 59 = 1829 Phi = (p - 1) ⋅ (q - 1) = 30 ⋅ 58 = 174 Guess e = 859 and check: gcd(859 , 1740 ) = 1 Using Euclid's algorithm, find A and B such that A ⋅ 859 + B ⋅ 1740 = 1 79 * 859 + (-39)1740 = 1 79 * 859 mod 1740 = 1 d = 79 is the inverse of 859 mod 1740 2.23.3: Preparation of public and private keys Suppose Bob selects prime numbers p=5 and q =11. What is N? - Correct Answers: 55 N = p * q 2.23.3: Preparation of public and private keys Suppose Bob selects prime numbers p=5 and q =11. What is Phi? - Correct Answers: 40 Phi = (p - 1) ⋅ (q - 1) 2.23.3: Preparation of public and private keys Suppose Bob selects prime numbers p=5 and q =11. What integer "e" can be chosen between 5 and 8? - Correct Answers: 7 Since 40=2³ * 5, e cannot be divisible by either 2 or 5. Thus, e=7. The public key is N=55 and e=7. 2.23.3: Preparation of public and private keys Suppose Bob selects prime numbers p=5 and q =11. Given the value for "e" found in the previous question, what is "d"? - Correct Answers: 23 Since (−17)7+(3)40=1, d=−17. In practice, only positive integers are used. Thus, the private key is d=−17+40=23. 2.23.4: Encrypting plaintext into ciphertext using RSA. Given the public key N=1829 and e=859, find the ciphertext "c" for each letter using the ASCII alphabet. A B C D E F G H I J K L M N O P Q 80 81 R S T U V W X Y Z "N" - Correct Answers: 498 Using the ASCII table, "N" gives the plaintext M=78. Thus, C=78⁸⁵⁹ = 498 mod 1829. 2.23.4: Encrypting plaintext into ciphertext using RSA. Given the public key N=1829 and e=859, find the ciphertext "c" for each letter using the ASCII alphabet. A B C D E F G H I J K L M N O P Q 80 81 R S T U V W X Y Z "O" - Correct Answers: 737 2.24.1: Decrypting ciphertext using RSA. Given the public key N=1829 and e=859 and the private key d=79, and c = 40. What's M? - Correct Answers: 82 M = 40⁷⁹ = 82 mod 1829 2.24.1: Decrypting ciphertext using RSA. Given the public key N=1829 and e=859 and the private key d=79, and c = 1126. What's M? - Correct Answers: 80 m = 1126⁷⁹ = 80 mod 1829 2.24.1: Decrypting ciphertext using RSA. Given the public key N=1829 and e=859 and the private key d=79, and c = 1609. What's M? - Correct Answers: 81 m = 1609⁷⁹ = 81 mod 1829 2.24.1: Decrypting ciphertext using RSA. Given the public key N=1829 and e=859 and the private key d=79, and c = 509. What's M? - Correct Answers: 83 m = 509⁷⁹ = 83 mod 1829 2.24.2: Encrypting and decrypting a message using RSA The public keys are N = 1829 and e = 859. Alice encrypts message m = 1211. What is the encryption value? - Correct Answers: 388 c = m^e mod N 1211⁸⁵⁹ mod 1829 = 388 2.24.2: Encrypting and decrypting a message using RSA The private key is d = 79. Bob receives the cyphertext c = 388, N = 1829 What is the decryption value? - Correct Answers: 1211 388^d mod N 388⁷⁹ mod 1829 = 1211 2.24.3: Encrypting and decrypting a message with RSA Suppose that Alice and Bob are using the RSA cryptosystem to send a message. Bob selects p = 3 and q = 11. What is the value of N? - Correct Answers: 33 pq = 3·11 = 33. 2.24.3: Encrypting and decrypting a message with RSA Suppose that Alice and Bob are using the RSA cryptosystem to send a message. Bob selects p = 3 and q = 11. What is the value of Phi? - Correct Answers: 20 phi = (p-1)(q-1) = 2·10 = 20. 2.24.3: Encrypting and decrypting a message with RSA Suppose that Alice and Bob are using the RSA cryptosystem to send a message. Bob selects p = 3 and q = 11. If "e" is chosen to be 7, what is "d"? - Correct Answers: 3 d is chosen so that 7·d mod 20 = 1.(7·3) mod 20 = 1 2.24.3: Encrypting and decrypting a message with RSA Suppose that Alice and Bob are using the RSA cryptosystem to send a message. Bob selects p = 3 and q = 11. If Bob receives ciphertext c = 25, then what was Alice's plaintext m? (You will probably need a calculator for this question.) - Correct Answers: 16 m = c^d mod N = 25³ mod 33 = 16 2.24.3: Encrypting and decrypting a message with RSA Suppose that Alice and Bob are using the RSA cryptosystem to send a message. Bob selects p = 3 and q = 11. f the plaintext m = 2, then what is the ciphertext "c"? - Correct Answers: 29 c = m^e mod N = 2⁷ mod 33 = 29 2.24.1: Encrypting and decrypting a message with RSA. In this problem, we will implement the RSA algorithm to encrypt and decrypt the message "HI". For this exercise, you may want to use a calculator that can compute the mod function. (A-Z = 1-26) Use the scheme used in your text to convert the message "HI" into an integer. Call the integer m. - Correct Answers: 809 H → 08, I → 09. m = 0809 = 809 2.24.1: Encrypting and decrypting a message with RSA. In this problem, we will implement the RSA algorithm to encrypt and decrypt the message "HI". For this exercise, you may want to use a calculator that can compute the mod function. (A-Z = 1-26) Set the primes p and q as follows: p = 43 and q = 79. What are the values for N and Phi? - Correct Answers: N = 3397 Phi = 3276 N = 43·79 = 3397 Phi = (43 - 1)(79 - 1) = 42·78 = 3276 2.24.1: Encrypting and decrypting a message with RSA. In this problem, we will implement the RSA algorithm to encrypt and decrypt the message "HI". For this exercise, you may want to use a calculator that can compute the mod function. (A-Z = 1-26) The value for "e" is chosen to be 29. Use Euclid's algorithm to verify that "e" and Phi are relatively prime and to find "d", the multiplicative inverse of "e" mod Phi. N = 3397 Phi = 3276 - Correct Answers: d = 113 3276 mod 29 = 28 29 mod 28 = 1 The equations for substitution are: 1 = 29 - 28 28 = 3276 - 112·29 Substitute (3276 - 112·29) for 28 into the equation 1 = 29 - 28 1 = 29 - (3276 - 112·29) = 113·29 - 3276 gcd(3276, 29) = 1 = 113·29 - 3276 The coefficient of 29 in the equation above is 113. The multiplicative inverse of 29 mod 3276 is 113. Check: 29·113 mod 3276 = 3277 mod 3276 = 1 d = 113 2.24.1: Encrypting and decrypting a message with RSA. In this problem, we will implement the RSA algorithm to encrypt and decrypt the message "HI". For this exercise, you may want to use a calculator that can compute the mod function. (A-Z = 1-26) Encrypt the message "m" by computing m^e mod N - Correct Answers: 336 Refer to book for solution 2.24.1: Encrypting and decrypting a message with RSA. In this problem, we will implement the RSA algorithm to encrypt and decrypt the message "HI". For this exercise, you may want to use a calculator that can compute the mod function.(A-Z = 1-26) Decrypt the message, compute c^d mod N. c = 336 d = 113 N = 3397 - Correct Answers: 809 Refer to book for solution