The University of Sydney
School of Mathematics and Statistics
Assignment 1
MATH2088/2988: Number Theory and Cryptography Semester 2, 2024
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 2.5% of your total mark, so the assignment
as a whole is worth 5% 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 5 September, 2024, before 11:59pm.
Both parts of the assignment must be submitted through the MATH2088/2988 Canvas
page. Note that there is a separate submission for each part; please make sure you
submit the right file to the right 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 PDF file. 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
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 Canvas,
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© 2024 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) Solve the linear congruence
20x ≡ 24 (mod 164).
(b) Solve the system of congruences{
20x ≡ 24 (mod 164)
x ≡ 15 (mod 73)
(c) Use the Fermat factorisation method to find a non-trivial divisor of 295091,
i.e. a divisor which is between 2 and 295090.
2. This question is for all students in both MATH2088 and MATH2988.
(a) Let m ∈ Z+ and a ∈ Z be such that gcd(a,m) = 1 and ad ≡ 1 (mod m).
Prove that ordm(a) | d.
(b) Let p be prime and integers a, b be such that ordp(a) = 2 and ordp(b) = 3.
(i) Show that ordp(ab) | 6.
(ii) Do such numbers a, b exist for p = 101?
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) Does there exist a positive integer number n such that 3n is a cube of an
integer number, 4n is the fourth power of an integer and 5n is the fifth power
of an integer number? If it exists, provide an example of such a number. If
not then justify your answer.
(b) Does there exists a positive integer number n that satisfies all the conditions
from the previous part, and on top of that 6n is the sixth power of an integer
number? Justify your answer.
2
Computer part: This is to be done using MAGMA, either in the computer labs (the
lab session in Week 6 has been set aside for this purpose) or on your own computer if
you have successfully installed MAGMA there (see the instructions on the unit web page).
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.
If you complete the assignment in the labs, you could (probably) do the submission
there too, but in any case please email yourself a copy of your log file(s).
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.