关键词 > MATH2088/2988
MATH2088/2988: Number Theory and Cryptography Semester 2, 2022 Assignment 1
发布时间：2022-09-15
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Assignment 1
MATH2088/2988: Number Theory and Cryptography
Semester 2, 2022
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 三 88 (mod 164).
(b) Solve the system of congruences
{ x(20)x三 15(三)
(c) Find the last digit of the decimal expansion of 7(77 ) . Justify your answer.
2. This question is for all students in both MATH2088 and MATH2988.
(a) Find the order of 4 modulo 83.
(b) Two sequences of integer numbers an and bn satisfy the following conditions: a1 = 1, b1 = 2; an+1 三 5an + 1 (mod 2022), bn+1 三 5bn + 1 (mod 2022)
for all integer n 2 1. Show that for all n e Z>0 , an 三\ bn (mod 2022).
(c) For each positive integer value n find the greatest common divisor of n! + 1 and (n + 1)! + 1.
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) Let a(x) and b(x) be two polynomials with rational coefficients and deg(b) 2 1. Show that there exist polynomials q(x), r(x) with rational coefficients such that
a(x) = q(x)b(x) + r(x), deg(r) < deg(b).
Recall that a polynomial p(x) has degree n if it is written as p(x) = anxn + an_1 xn_1 + . . . + a1 x + a0 where an 
0. By convention, the degree of zero is -o.
(b) Let a(x) and b(x) be two polynomials with rational coefficients that do not share common factors. That is, there are no polynomials d(x) with rational coefficients such that deg(d) 2 1 and a(x) = d(x)a1 (x), b(x) = d(x)b1 (x) for some polynomials a1 (x), b1 (x) with rational coefficients. Verify that there exist polynomials s(x), t(x) with rational coefficients such that
1 = s(x)a(x) + t(x)b(x).
[Hint: the previous part of the question may help]
(c) Let p(x) = a5 x5 + a4 x4 + a3 x3 + a2 x2 + a1 x + a0 be a polynomial with positive integer coefficients. You are given that p(1), p(2), p(3), . . . , p(10) are all prime numbers. Show that p(x) is irreducible, i.e. it can not be written as a product p(x) = a(x)b(x), where a(x), b(x) are some polynomials with integer coefficients and deg(a), deg(b) 2 1.
Here, you may use the Fundamental Theorem of Algebra (a polynomial of degree d has at most d complex roots) without proof.
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 Vigen`ere cipher, and the other two were enciphered using simple substitution ciphers.
You need to determine which of the three is the Vigen`ere ciphertext, and decipher it (you can ignore the others). To find the period and decryption key of the Vigen`ere cipher, you can use either the javascript Vigen`ere 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 Vigen`ere key finder.
Once you have printed the plaintext in capitals, you have finished the question.
