Department of Mathematics
MATHS 328 Assignment 3 Due: 6 May 2024
1. (a) List all quadratic residues in Z11;
(b) List all elements of the group E of points of the elliptic curve over Z11 given by Y 2 = X3+5X+7.
(c) What is the lower and upper bounds for the number of points of an elliptic curve over Z11?
2. (a) Do there exist elements of order 121 and 209 in the group E of points of elliptic curve Y 2 =
X3 + 12X + 345 over Z43261? Do something smarter than checking orders of all elements of E.
(b) Find an element of order 121 or an element of order 209 in E (depending on which of them
exists). Explain how you did it.
3. Let g, h, k, ` be elements of a finite abelian group G of orders
11490055587882733971157745622141044411,
63642900438454938873473894132841241058592519601,
3810716361,
1885175497551,
respectively. Use g, h, k.` to construct an element e of G of order
362508549058231790456378224742027510209972363534502717904836842272670521.
Express it in terms of g, h, k, `.
4. Encode message CRYPTO as a sequence of two points of elliptic curve Y 2 = X3 + 111x + 1111
mod 65231563. Use the method with the failure rate 1/210. Use the following numerical encodings
for the letters of English alphabet:
A = 11, B = 12, . . . , Z = 36.
(Note that it is not necessary to generate the full group of points for this question.)
5. Let E be an elliptic curve over Zp with a point P be on E. Suppose m is a unique positive integer
such that mP = ∞ and (√p − 1)2 ≤ m ≤ (√p + 1)2. Say with reason what is the order of the
group for this curve. Quote all theorems you use.
6. Alice and Bob have agreed to use the Elgamal cryptosystem based on the multiplicative
group of field Zp for p = 37. They also have agreed to use 2 as the primitive element
of Zp. Since p is small their messages consist of a single letter which is encoded as
A = 11, B = 12, . . . , Z = 36.
Alice’s public key is 32 and Bob sent her the message (5, 30). Which letter did
Bob send to Alice in this message?
7. (Bonus question) Let p be a prime and g be a primitive element in Zp.
(a) Prove that
logg(ab) = logg(a) + logg(b) mod p−1.
(b) Deduce that the product of a two quadratic non-residues is a quadratic residue.
MATHS 328 Assignment 3 Page 1 of 1