关键词 > MATH2068/2988
MATH2068/2988: Number Theory and Cryptography Semester 2, 2016
发布时间：2022-11-06
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CC9178
Semester 2, 2016
MATH2068/2988: Number Theory and Cryptography
1. (a) (i) [2 marks] Find an inverse of 5 modulo 37.
(ii) [2 marks] Solve the congruence 5x ≡ 4 (mod 37).
(b) (i) [2 marks] Find the order of 3 modulo 11.
(ii) [2 marks] Compute the residue of 32016 modulo 11.
(c) [2 marks] Complete the deinition: a function f(n) of a positive integer variable n is said to be multiplicative if . . . .
(d) [2 marks] Find a quadratic polynomial Q(x) = ax2 + bx + c, where the coe
cients a,b,c belong to {0, 1, 2, 3, 4, 5, 6}, such that the following all hold:
Q(1) ≡ 2 (mod 7),
Q(2) ≡ 4 (mod 7),
Q(3) ≡ 1 (mod 7).
2. (a) [3 marks] A Vigen、ere cipher with encryption key FOX has been used to produce the ciphertext ROQMG. What was the plaintext?
(b) [3 marks] Suppose you are given a long ciphertext in capital letters (of the
ordinary alphabet) and told that it was produced by enciphering ordinary English text using either a simple substitution cipher or a transposition cipher. What statistical feature of the ciphertext would you consider to decide which of the two types of cipher was used, and why?
(c) [3 marks] Suppose that an RSA cryptosystem has public key (119, 5). What is the decryption exponent?
(d) [3 marks] Suppose that you are an Elgamal user with public key (59, 2, 5) and private key 6. Note that this is consistent, because 26 ≡ 5 (mod 59). You receive the message (3, [21, 4]) . Decrypt it.
3. This question is for students enrolled in the mainstream unit MATH2068 only. Do not answer this if you are in the advanced unit MATH2988.
Throughout this question, a and b are positive integers with a > b. Suppose that when we apply the Euclidean Algorithm to a and b, we obtain the following m equations (for some positive integer m):
a = q1 b + r1
b = q2r1 + r2
r1 = q3r2 + r3
ri—2 = qiri— 1 + ri
rm —3 = qm — 1 rm —2 + rm — 1
rm —2 = qmrm — 1 + rm
Here, for every i ∈ {1, · · · ,m}, qi and ri are the quotient and remainder when ri—2 is divided by ri— 1 . To make the notation consistent in the case when i ∈ {1, 2}, we set r— 1 = a and r0 = b. We suppose that the algorithm has terminated after these m equations, i.e. rm — 1 
0 and rm = 0.
(a) [4 marks] Give the proof of a result from lectures: namely, the fact that
gcd(ri—2 ,ri— 1 ) = gcd(ri— 1 ,ri ) for all i ∈ {1, · · · ,m}.
(b) [4 marks] Give the proof of a result from lectures: namely, the fact that
ri < 1
2ri—2 for all i ∈ {1, · · · ,m}.
(c) [4 marks] Suppose that a and b are both less than 2k for some positive integer k . Give the proof of a result from lectures: namely, the fact that m < 2k . (This uses the result from the previous part (b).)
4. (a) [4 marks] Give the proof of a result from lectures: namely, the fact that if a,b,c are integers such that gcd(a,b) = 1 and a | bc, then a | c.
(b) [2 marks] Complete the deinition: if m is a positive integer, the Euler
phi-function 
(m) is . . . .
(c) [6 marks] Recall that the Euler–Fermat Theorem says that if m is a positive integer and b is an integer such that gcd(b,m) = 1, then b
(m) = 1 (mod m). Now suppose that m = pq where p,q are distinct prime numbers. Give the proof of a result from lectures: namely, the fact that
a
(m)+1 = a (mod m) for every integer a.
You may assume the Euler–Fermat Theorem and that 
(m) = (p−1)(q−1).
5. In this question you can use any results proved in lectures or tutorials.
(a) [4 marks] Let p be an arbitrary prime number such that p = 1 (mod 3).
Prove that there exists some integer x such that x2 + x + 1 = 0 (mod p).
(b) [4 marks] Prove that there are ininitely many prime numbers p such that
p = 2 (mod 3).
(c) [4 marks] Prove that 2 and 6 are the only positive integers n satisfying the inequality 
(n)2 < n.
6. This question is for students enrolled in the advanced unit MATH2988 only. Do not answer this if you are in the mainstream unit MATH2068.
(a) [5 marks] Let a and b be integers satisfying a ≥ 1, b > 1, gcd(a,b) = 1, and
gcd(b, 10) = 1. The rational number a
b has some ininite decimal expansion
a
b = tk tk — 1 · · · t1t0 .t— 1t—2t—3t—4 · · ·
where each ti is a digit from the set {0, 1, 2, · · · , 9}. Note that the digits ti indexed by negative integers i are the ones that come after the decimal point. Show that if i and j are negative integers such that i = j (mod ordb (10)), then ti = tj .
(b) [3 marks] Let i ∈ Z+ . Show that if m1 and m2 are odd integers such that
m1(2) = m2(2) (mod 2i+1), then m1 = m2 (mod 2i ) or m1 = −m2 (mod 2i ).
(c) [4 marks] Describe a polynomial-time algorithm which determines whether a given positive integer n is a perfect square. (Here, as usual, to say that the algorithm is polynomial-time means that there is some positive integer a such that the maximum number of bit operations required when the algorithm is applied to an arbitrary positive integer n with k binary digits is O(ka ).)
