The University of Sydney School of Mathematics and Statistics Number Theory and Cryptography Semester 2, 2019 MATH2088/2988 Sample Quiz Student ID Tutor’s name Tutorial room Tutorial time and day Time allowed: 45 minutes The quiz for MATH2088/2988 will be held in the tutorials in Week 8 (25–26 September). This quiz, which is the same for both units, contributes 10% towards the final mark, except that the better mark principle applies: if your mark in the exam is better than your mark in the quiz, then your exam mark will count for 70% rather than 60%, and your quiz mark will not count. For this reason, there is no point applying for Special Consideration or Special Arrangements in relation to the quiz: the mark reweighting it would produce is automatic anyway. The quiz will cover material relating to weeks 1–6 of the MATH2088/2988 lectures, up to and including multiplicative functions, the Möbius Inversion Formula, and the RSA cryptosystem, and the associated Tutorials 1–6 (including Tutorial 6 in Week 7) and Computer Labs 1–6 (including Computer Lab 6 in Week 7). For the purposes of this quiz, which consists of short-answer questions, only the unstarred computational questions in those tutorials are relevant, not the proof questions or starred questions; and only the underlying ideas in those computer labs will be tested, not the details of MAGMA syntax or programming skills. This sample quiz will give you an idea of the sorts of questions that will be asked. (The order of the questions here does not necessarily indicate anything about the order of questions in the actual quiz.) It is strongly recommended that you try to complete this sample quiz under exam conditions in the assigned time, before looking at the solutions. This should help you identify which topics you need to focus on in your revision. 1. Each question has a box for your working and a smaller box for your final answer. You must write your answer in the answer box even if it is included in the working. 2. If your answer is correct, you will receive full marks for the question; if your answer is incorrect, partial marks may be awarded for your working. 3. Please write carefully and legibly using ink and not pencil. 4. The complete quiz paper, together with any other pages used for working, must be handed in at the end of the quiz. 5. Only University-approved non-programmable calculators, with the sticker from the Student Centre, may be used. This quiz paper has two pages and 15 questions. MATH2088/2988: Sample Quiz © 2019 The University of Sydney Number Theory and Cryptography MATH2088/2988 1. Find gcd(1020, 84). Answer 2. Find the smallest prime which divides 123456789123456789. Answer 3. Find which element of {1, 2, · · · , 58} is inverse to 17 modulo 59. Answer MATH2088/2988: Sample Quiz Page 2 of 2 MATH2088/2988 Sample Quiz 4. Find the order of 5 modulo 31. Answer 5. Find the residue of 31010 modulo 7. Answer 6. Find the unique x ∈ {0, 1, 2, · · · , 194} such that x ≡ 3 (mod 13) and x ≡ 2 (mod 15). Answer MATH2088/2988: Sample Quiz Page 3 of 2 Number Theory and Cryptography MATH2088/2988 7. Find the residue of 21010 modulo 111. Answer 8. Find σ(640), the sum of the positive integer divisors of 640. Answer 9. What is the smallest positive integer with exactly 10 positive divisors? Answer MATH2088/2988: Sample Quiz Page 4 of 2 MATH2088/2988 Sample Quiz 10. If a simple substitution cipher encrypts the word SUGAR as JWZXD, what is the decryption of XDZWJ? Answer 11. What would be the output of the following MAGMA commands? > V:=VigenereCryptosystem(3); > encipheringkey:=V!”BAY”; > Enciphering(encipheringkey,Encoding(V,”HOTEL”)); Answer 12. Suppose you are given two long ciphertexts sct1 and sct2 and told that one of them is some ordinary 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 Answer MATH2088/2988: Sample Quiz Page 5 of 2 Number Theory and Cryptography MATH2088/2988 13. If an RSA cryptosystem has public key (22, 3), what is the decryption exponent? Answer 14. Suppose that an RSA cryptosystem has a public key of (33, 3). Encrypt the message [4, 6]. Answer 15. What would be the output of the following MAGMA commands? > p:=NextPrime(100); > 6∧p mod p; Answer This is the last page of the quiz paper. MATH2088/2988: Sample Quiz Page 6 of 2