ELLIPTIC CURVES AND APPLICATIONS

March 16, 2001

1. Consider the elliptic curve analog of El Gamal cryptosystem with

E : y^{2} = x^{3} − x + 188

defined over F_{751} and with the base point Q = (0, 376). Suppose that your correspondent’s public key is the point (201, 5) and your random integer k is 386. Use this cryptosystem to send the message represented by the point P_{m} = (562, 201) on E.

2. Consider the elliptic curve

E : y^{2} = x^{3} + 71x + 602

over the field F_{1009}. Using the baby step/giant step method solve the following ECDLP:

Q = m P,

where P = (32, 737) and Q = (364, 669).

3. For each of the following elliptic curves over Q, determine all of the points of finite order:

a) y^{2} = x^{3} + 4,

b) y^{2} = x^{3} − x,

c) y^{2} = x^{3} − 43x + 166.

4. Choose F, one of fifteen admisible torsion groups for an elliptic curve over Q. Find an elliptic curve with E(Q)_{tors} ≃ F and relatively high rank (say, #F · rank ≥ 20). Describe your algorithm.

Andrej Dujella