2007 - Exercises VIII.
1. Consider the elliptic curve y2
= x3
+ x + 6 over the field Fn.
(a) Determine the number of multiple roots of this elliptic curve.
(b) Compute in detail the points (2, 7) + (5, 2) and (3, 6) + (3, 6).
2. Let E be the elliptic curve y2
= x3
+ 2 over the field F7.
(a) Find the points of E.
(b) Which group is the elliptic curve E isomorphic to?
3. Let y2
= x3
+ 9x+17 be the elliptic curve over the field F23. What is the discrete
logarithm k of Q = (4,5) to the base P = (16, 5)?
4. Consider the following elliptic curve cryptosystem.
An elliptic curve E : y2
= x3
+ ax + b over the field Zp and a generator point
G E E of order n are public parameters.
Each user U selects as a private key a number su < n and computes the corresponding
public key Pu = suG.
To encrypt a message point M, one selects a random k and computes the ciphertext
pair of points C = [(kG), (M + kPu)](a)
Show how the user U can decrypt C and obtain M.
(b) Let E be y2
= x3
+ x + 6 (mod 11), G = (2, 7) and sA = 7.
Recover the plaintext message point M from C = [(8, 3), (10, 2)].
5. Factorize n = 4453 using the elliptic curve y2
= x3
+ lOx -- 2 (mod n) and the
point P= (1,3).
6. (a) Factorize the following numbers n\ = 527 and n2 = 1241 using the Pollarďs
p-algorithm (the first one from the lecture) with f(x) = x2
+ 1 and Xo = 0.
(b) Factorize the following numbers n\ = 65 (6 = 10) and n2 = 15770708441
(b = 200) using the Pollarďs p -- 1 algorithm.
7. Consider the Pollarďs p-algorithm with a pseudo-random function f(x) = x2
+ c
(mod n) with a randomly chosen c, 0 < c < n. Why should be the values c = 0
and c = n -- 2 avoided?
8. Show that n13
-- n is a multiple of 420 for any odd n.