An elliptic curve is a curve with equation y2 = x3 + Ax + B. Taking x and y as integers modulo P produces a finite set of points which satisfy this equation. Addition can be performed, and the result will be another point on the curve. This addition operation is not simply addition of coordinate values, but follows complicated rule.
When P is prime the points will always form a group under the elliptic curve addition operation. If P is not prime, the points can still be plotted, but addition may not always work and the points may not form a group. P must be a positive integer greater than 3. It is necessary that 4A3 + 27B2 (mod P) ≠ 0, so that the cubic in x does not have repeated roots. The identity is the point conventially written '0'. This point is at infinity. Here it is notated as (zero, zero), distinct from (0, 0), which may or may not be a point on the curve.
The 'orbit' of P is a list of all points generated by P, so consists of P, P + P = 2P, P + 2P = 3P, 4P, ... until reaching (zero, zero), which is the group identity. For example, with A = 1, B = 0 and P = 13, the elliptic curve has 20 points. Choosing P = (2, 7), the orbit of P becomes a subgroup with 10 points. Choosing P = (9, 6) the orbit is a subgroup of 5 points. There is clearly also at least one subgroup with two points. Finding such a subgroup is left as an exercise.
With A = -4, B = 0 and P = 2017, the elliptic curve has 2000 points. This offers plenty of scope for finding subgroups of different sizes.
|
y2 = x3 + x + (mod) [It is necessary that 4A3 + 27B2 (mod P) ≠ 0] P = (,) Q = (,) [Type 'zero' as the first coordinate of P or Q to enter 'zero' - the point at infinity] |