The University of Sydney School of Mathematics and Statistics Assignment 1 MATH2088/2988: Number Theory and Cryptography Semester 2, 2021 Web Page: https://canvas.sydney.edu.au/courses/36130 Lecturer: Dzmitry Badziahin This assignment is in two parts: a “non-computer part”1 and a “computer part”. Each part consists of two questions: in the non-computer part, which two questions you need to do depends on whether you are enrolled in the mainstream unit MATH2088 or the advanced unit MATH2988; in the computer part, all students do the same two questions. Each part will be marked out of 10 and is worth 5% of your total mark, so the assignment as a whole is worth 10% of your total mark. Except for students who have registered with Disability Services or who apply success- fully for Special Consideration or Special Arrangements, the due date for this assignment is Thursday 16 September, 2021, before 11:59pm. Both parts of the assignment must be submitted through Turnitin on the MATH2088/2988 Canvas page. Note that there is a separate Turnitin submission for each part; please make sure you submit the right file to the right Turnitin submission. To find the submission links on the Canvas page, you firstly click on “Assignments” link in the menu on the left and then click on “Assignment 1 Non-Computer Part” or “Assignment 1 Computer Part” respectively. You do not need to submit the two parts at the same time, but the same deadline applies to both parts. For the non-computer part, your submission can be either typed or a scan/photo of handwritten answers, but it must be submitted as a single file that Turnitin can accept (e.g. a PDF or a Word document). For the computer part, your submission will be a text file which is the record of a MAGMA session (perhaps edited; see below for more details), and should be given the name “asst1-[sid].txt” where “[sid]” is your student ID. After you make your submission, open it on Canvas and make sure that your sub- mission contains all the pages and is legible. Markers will see it in exactly the same form as you see it. If some pages are missing or illegible, you will loose marks. If you discover a problem with a file you have submitted, you can submit a new version before the deadline (which will simply replace your previous submission). It is your responsibility to leave enough time before the assignment deadline to complete both Turnitin submissions, and to ensure that your submissions are legible. While discussion with other students in the course is allowed, including on the Ed forum, what you submit must be your own work. When you submit via Turnitin, you agree to an Academic Honesty statement which says in part “I certify that this work is substantially my own, and where any part of this work is not my own, I have indicated as such by acknowledging the source of that part or those parts of the work”. 1The name “non-computer part” just means that this part doesn’t involve MAGMA. You can certainly use a computer to type your answers to it if you want! Copyright c© 2021 The University of Sydney 1 Non-computer part: Write or type complete answers to the two questions appropriate to your unit, showing all working (in Q1, Q2) or all logical steps (in Q2, Q3). 1. This question is for students enrolled in the mainstream unit MATH2088 only. Do not answer this if you are in the advanced unit MATH2988. (a) Use the Fermat factorisation method to find a non-trivial divisor of 154009. Non-trivial divisor means that it is between 2 and 154008. (b) Find an integer x such that x79 ≡ 7 (mod 277). (c) Find an integer x such that{ x79 ≡ 7 (mod 277) x ≡ 10 (mod 93) 2. This question is for all students in both MATH2088 and MATH2988. A sequence an of integer numbers is called periodic if there exists a positive integer p such that for all n ∈ Z+, an+p = an. The number p is then called a period of the sequence an. For example, the sequence 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, . . . is periodic with period 3. (a) Let an and bn be two periodic sequences with periods p and q respectively. Show that the sequence an + bn is also periodic with period pq. (b) Show that the sequence an ∈ Z such that 0 ≤ an < 2021 and an ≡ n+ 2n (mod 2021), is periodic. (c) Show that there are infinitely positive integer values n such that 2n + n− 3 is a multiple of 2021. 3. This question is for students enrolled in the advanced unit MATH2988 only. Do not answer this if you are in the mainstream unit MATH2088. (a) You are given that p = 456821 is prime and that 28p+1 ≡ 2 (mod 8p+ 1). Deduce that 8p+ 1 is also prime. (b) Find all natural solutions m,n ∈ N of the equation 2m + 1 = 3n. [Hint: with help of modular arithmetic one can verify that for m ≥ 2 the value of n must be even.] 2 Computer part: This is to be done using MAGMA. To complete Q5, you will need to download the file asst1ciphertexts.txt from the Resources Table on the web page. What you need to submit is the “log file” or record of your MAGMA session; to name this correctly, make your first command SetLogFile("asst1-[sid].txt"); where [sid] is replaced by your student ID. You could answer the two questions in different MAGMA sessions, but in that case you would have to concatenate the log files (e.g. using a text editor) so that you have a single text file to submit to Turnitin. It would be simpler to answer both questions in the same MAGMA session if you can. Warning: Turnitin may object to a submission that has too many “words” which it can’t make sense of, including the long strings of capital letters which are our ciphertexts and plaintexts. If you get this error message, you should edit your log file (using a text editor) to remove as many of these long strings as possible while still leaving all the essential commands: for instance, if you asked MAGMA to print one of the ciphertexts, you could delete that from the log file. Alternatively, to minimize your chance of having to do this editing, don’t ask MAGMA to print the ciphertexts (you can always see them by opening the file asst1ciphertexts.txt in the lab or from the web page). 4. In this question you will do a simple “experimental test” of the Euler–Fermat Theorem using your student ID as the modulus. In MAGMA give the name sid to your student ID (a nine-digit number). Use MAGMA commands from Computer Tutorial 1 to select random nine-digit numbers until you find one that is coprime to sid, and call this number num. Now ask MAGMA to compute the order of num modulo sid and the Euler phi- function of sid, using the commands Modorder(num,sid); and EulerPhi(sid); Finally, use MAGMA to verify that the first of these numbers divides the second. 5. Type the command load "asst1ciphertexts.txt"; The file you have loaded defines three ciphertexts called sct1, sct2 and sct3 (all of type String). The original plaintexts were all in English, and all concerned the military applications of mathematics. One of the three was enciphered using a Vigene`re cipher, and the other two were enciphered using simple substitution ciphers. You need to determine which of the three is the Vigene`re ciphertext, and decipher it (you can ignore the others). To find the period and decryption key of the Vigene`re cipher, you can use either the javascript Vigene`re key finder on the MATH2088 web page or the MAGMA methods of Computer Tutorial 3. Beware that the plaintexts were relatively short, so the most frequent letter in a decimation is not guaranteed to be E; you will need to check other letters, or use the correlation data provided by the javascript Vigene`re key finder. Once you have printed the plaintext in capitals, you have finished the question. 3
欢迎咨询51作业君
