The University of Sydney
School of Mathematics and Statistics
Assignment 2
MATH2088/2988: Number Theory and Cryptography Semester 2, 2023
Web Page: https://canvas.sydney.edu.au/courses/53120
Lecturer: Dzmitry Badziahin
Like Assignment 1, this assignment is in two parts: a “non-computer part” and a “com-
puter 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 19 October, 2023, before 11:59pm.
Both parts of the assignment must be submitted to 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 2 Non-Computer Part” or “Assignment 2 Computer Part” respectively.
You do not need to submit the two parts at the same time, but the same deadline applies
to both of them.
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. Check that your file
displays correctly in the Canvas preview window before you submit it. Unviewable or
illegible submissions will get a mark of 0. For the computer part, your submission
will be a text file which is the record of a MAGMA session (perhaps edited), and should
be given the name “asst2-[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 your assign-
ment, 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”.
Copyright c© 2023 The University of Sydney 1
Non-computer part: Write or type complete answers to the two questions appropriate
to your unit, showing all working. You should work under assumption that your calculator
can only deal with numbers up to 10 digits long. That is, if the numbers involved in an
arithmetic operation are at most 10 digits long, you may provide the result of that
operation without justification. Otherwise, a justification is required. Also, you do not
have to justify the primality of a number below 100 but you can not assume that a number
bigger than one hundred is prime or composite without justification.
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) Suppose you are an RSA user with public key (4171, 1613) and private key 5.
If you receive a ciphertext [3605, 1542, 3995], what is the decrypted message?
(b) Find the order of 11 modulo 53.
2. This question is for all students.
(a) Find an integer x ∈ {0, . . . , 138} which solves the equation
x83 ≡ 7 (mod 139).
(b) One has two algorithms A and B which take an integer number n as an
input and compute the same value A(n) as an output. The complexity of
the algorithm A for a k-bit input is{
O(k3) EBO’s if n is even;
O(2k) EBO’s if n is odd.
The complexity of the algorithm B for the same input is{
O(3k) EBO’s if n is even;
O(k4) EBO’s if n is odd.
Compose a polynomial time algorithm that computes A(n) for a k-bit input.
Justify your answer.
(c) Consider an RSA cryptosystem with public key (n, e), where n = pq and p, q
are distinct odd primes. Explain why the value of e can not be even.
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) Show that there are infinitely many primes q such that 2 is not a primitive
root modulo q. Hint. It may help to consider prime divisors of numbers
2p − 1 where p is prime. Question 6(d) from Week 2 tutorial sheet may also
help.
(b) You are given a ∈ Z,m, n ∈ Z+ such that gcd(a,m) = gcd(a, n) = gcd(m,n) =
1, the order of a modulo m is 5 and the order of a modulo n is 7. Find the
order of a modulo mn. Justify your answer.
2
Computer part: This is to be done using MAGMA, either in the computer labs (the
lab session in Week 11 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).
If you are completing Q5 outside the computer labs, you will need to download the file
asst2definitions.txt from the Resources Table on the web page.
What you need to submit is a “log file” or record of your MAGMA session; to get
MAGMA to generate this automatically and give it the right name, you can make your first
command SetLogFile("asst2-[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. You may use a source file for all commands but in
that case you need to concatenate it with the log files. In any case, the marker should
be able to see all the commands you typed and MAGMA’s response to them.
As well as the MAGMA commands, you may wish to add comments such as “Question
4” or “This is my answer”: you can start and end comments by typing /* and */.
If you complete the assignment in the labs, you could (probably) do the Turnitin
submission there too, but in any case please email yourself a copy of your log file(s).
4. In MAGMA define p to be the smallest prime which is greater than or equal to
your student ID and is also congruent to 1 modulo 4. Ask MAGMA to choose a
primitive root b modulo p with the command b:=PrimitiveRoot(p);. Then use
appropriate MAGMA commands to find a nonnegative integer less than p which is
a square root of −1 modulo p. There are two such integers; you can stop once you
have found one of them, except that you should then get MAGMA to check that
your answer does square to something congruent to −1 modulo p.
5. Load the file asst2definitions.txt. It defines an RSA public key (n,e) and a cipher-
text ct which has been encrypted using this public key; ct is a sequence of residues
modulo n, which happens to consist of just a single residue.
Before encryption, the original message (four words in ordinary Roman letters)
was encoded as a residue modulo n using the NaiveEncoding function in the file
MagmaProcedures.txt. Your task is to find this original message by decrypting
ct as in Computer Tutorial 6, for which you will first need to find the decryption
exponent d, the inverse of e modulo ϕ(n).
The problem is that n has 1250 decimal digits, which is far too large to use the
MAGMA commands Factorization(n); or EulerPhi(n); (don’t bother trying
them; MAGMA will just hang or run out of time). This RSA cryptosystem would
be unbreakable, except that someone has let slip the information that the two
primes of which n is the product are a Germain prime x and its corresponding safe
prime 2x + 1. Knowing this, you can find x as the unique positive solution of the
quadratic equation 2x2+x−n = 0. To apply the quadratic formula, you will need
to find the square root of the discriminant D as an exact integer: Q4 of Computer
Tutorial 8 explains how to do this.