程序代写案例-MATH2088/2988-Assignment 1

The University of Sydney
School of Mathematics and Statistics
Assignment 1
MATH2088/2988: Number Theory and Cryptography Semester 2, 2021
Web P
age: 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作业君
51作业君 51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: ITCSdaixie