MATH2X88 SAMPLE QUIZ ANSWERS CONTENTS Question 1 2 Question 2 2 Question 3 2 Question 4 3 Question 5 3 Question 6 3 Question 7 3 Question 8 4 Question 9 4 Question 10 5 Question 11 5 Question 12 6 Question 13 6 Question 14 6 Question 15 6 Date: Semester 2 2021. 1 MATH2X88 SAMPLE QUIZ ANSWERS 2 Question 1: Find gcd(1020, 84). Note 84 = 22 · 3 · 7. gcd(1020, 84) = gcd(220 · 520, 22 · 3 · 7) = 22 = 4 Question 2: Find the smallest prime which divides 123456789123456789. We can simply check all prime numbers from 2 to √ 123456789123456789 = 3.51364 · · · × 108. 2 obviously can’t be a divisor as 123456789123456789 is odd, so we check 3. 123456789123456789 3 = 41152263041152263, so 3 | 123456789123456789, thus 3 is the smallest prime which divides 123456789123456789. Note: for a more rigorous answer we find the prime factorisation of 123456789123456789 using Fermat’s method and choose the smallest number, as it could be that the smallest prime is very large. Question 3: Find which element of {1, 2, . . . , 59} is the inverse to 17 modulo 59. We want some s, t ∈ Z such that s · 17 + t · 59 = 1, then we have s = 17−1 (mod 59). We can do this with the Extended Euclidean Algorithm 59 17 8 1 · · 3 2 1 0− 1 2− 0− 1 3− 7 As 59 = 3 · 17 + 8, 17 = 2 · 8 + 1. Then 1 = (−2) · 59 + 7 · 17. So 17−1 ≡ 7 (mod 59). Question 4: Find the order of 5 modulo 31. MATH2X88 SAMPLE QUIZ ANSWERS 3 ord31(5) is given by the smallest a such that 5a ≡ 1 (mod 31). a 1 2 3 5a (mod 31) 5 25 1 So ord31(5) = 3, thus the order of 5 modulo 31 is 3. Question 5: Find the residue of 31010 modulo 7. We want to evaluate 31010 (mod 7). Note 1010 ≡ 2 (mod 6), so 31010 ≡ 32 ≡ 2 (mod 7). So the residue of 31010 modulo 7 is 2. Question 6: Find the unique x ∈ {0, 1, 2, . . . , 194} such that x ≡ 3 (mod 13) and x ≡ 2 (mod 15). We have that x = 3 + 13a, a ∈ Z. 3 + 13a = 2 (mod 15) 13a = 14 (mod 15) As 13−1 ≡ 7 (mod 15). a = 14 · 7 (mod 15) a = 8 (mod 15) Then a = 8 + 15b, b ∈ Z. So we have x = 3 + 13(8 + 15b) = 3 + 104 + 195b = 107 + 195b. Therefore, x ≡ 107 (mod 195). So, x = 107 satisfies x ≡ 3 (mod 13) and x ≡ 2 (mod 15). Question 7: Find the residue of 21010 modulo 111. We want to evaluate 21010 (mod 111). Note that 111 = 3 · 37. MATH2X88 SAMPLE QUIZ ANSWERS 4 We then have that 1010 ≡ 0 (mod 1), so 21010 ≡ 20 ≡ 1 (mod 3). So the residue of 21010 modulo 3 is 1. Similarly, 1010 ≡ 2 (mod 36), so 21010 ≡ 22 ≡ 4 (mod 37). So the residue of 21010 modulo 37 is 4. Now we solve this system of equations using the Chinese remainder theorem. We have that 21010 = 1 + 3a, a ∈ Z. 1 + 3a = 4 (mod 37) 3a = 3 (mod 37) a = 1 (mod 37) As 3−1 ≡ 25 (mod 37)⇒ 12 · 25 ≡ 4 (mod 37). Then a = 1 + 37b, b ∈ Z. So we have 21010 = 1 + 3(1 + 37b) = 1 + 3 + 111b = 4 + 111b. Therefore, 21010 ≡ 4 (mod 111). So the residue of 21010 modulo 111 is 4. Question 8: Find σ(640), the sum of the positive integer divisors of 640. Note, 640 = 27 · 5. Then σ(640) = σ(27)σ(5) = (1 + 2 + 22 + 23 + 24 + 25 + 26 + 27)(1 + 5) = 255 · 6 = 1530 Question 9: What is the smallest positive integer with exactly 10 positive divisors? MATH2X88 SAMPLE QUIZ ANSWERS 5 For exactly 10 positive divisors we have τ(n) = 10, n ∈ Z. Note, we have n = pa11 pa22 pa33 . . . pakk , pk ∈ P, ak ∈ N. τ(n) = τ (pa11 ) τ (p a2 2 ) . . . τ (p ak k ) = (a1 + 1)(a2 + 1)(a3 + 1) . . . (ak + 1) We have that 10 = 10 · 1 = 1 · 10 = 2 · 5 = 5 · 2, so we have at most two product terms, (a1 + 1)(a2 + 1). We must have that for the smallest positive integer with exactly 10 positive divi- sors that a1 > a2 if we assume that p1 < p2, so (a1+1)(a2+1) = 10 ·1 or (a1+1)(a2+1) = 5 ·2. Let us check the two possibilities. The two smallest primes are 2 and 3, so set p1 = 2, p2 = 3. For (a1 + 1) = 10 ⇒ a1 = 9, (a2 + 1) = 1 ⇒ a2 = 0 we have n = 29 · 30 = 512. For (a1 + 1) = 5⇒ a1 = 4, (a2 + 1) = 2⇒ a2 = 1 we have n = 24 · 31 = 48. Therefore 96 is the smallest positive integer with exactly 10 positive divisors. Question 10: If a simple substitution cipher encrypts the word SUGAR as JWZXD, what is the decryption of XDZWJ? We have that S 7→ J, U 7→W, G 7→ Z, A 7→ X and R 7→ D. The decryption reverses the mappings, so J 7→ S, W 7→ U, Z 7→ G, X 7→ A and D 7→ R. We know that XDZWJ must decrypt to ARGUS. Question 11: What would the output be of the following MAGMA commands? > V:=VigenereCryptosystem(3); > encipheringkey:=V!”BAY”; > Enciphering(encipheringkey,Encoding(V,”HOTEL”)); This gives a shift of 1 letter for every third letter from the first, a shift of 0 letters for every third letter from the second and a shift of 24 letters for every third letter from the third. So H 17−→ I, O 07−→ O, T 247−→ R, E 17−→ J and L 07−→ L. So the output is IORFL. MATH2X88 SAMPLE QUIZ ANSWERS 6 Question 12: Suppose you are given two long ciphertexts sct1 and sct2 and told that one of them is some ordi- nary English text enciphered with a block transposition cipher and the other is the same English text enciphered with a Vigenere cipher. If you see the following MAGMA code, which one was (probably) enciphered using the block transposition cipher? > CoincidenceIndex(sct1); 0.0652012312147048057406882815071 > CoincidenceIndex(sct2); 0.0415879787948780874621427836594 Because sct2 has a coincidence index that is quite different from regular English text of approxi- mately 0.065, whilst sct1 has a coincidence index that is very close to regular English text, sct1 is probably enciphered using the block transposition cipher. Question 13: If an RSA cryptosystem has public key (22, 3), what is the decryption exponent? Note that 22 = 2 · 11, so ϕ(22) = (2− 1)(11− 1) = 10. The decryption exponent is then given by 3−1 ≡ 7 (mod 10). So the decryption exponent is 7. Question 14: Suppose that an RSA cryptosystem has public key of (33, 3). Encrypt the message [4, 6]. 43 ≡ 31 (mod 33) and 63 ≡ 18 (mod 33). So [4, 6] encrypts to [31, 18]. Question 15: What would be the output of the following MAGMA commands? > p:=NextPrime(100); > 6^p mod p; The next prime after 100 is 101. 6101 ≡ 6 (mod 101) by Fermat’s little theorem, so the output would be 6.