Definition

An elliptic curve (EC) is the set of all points satisfying the equation of the form

$y^2 = x^3 + ax + b$ mod p

• where p is 256 bit prime
• Elliptic curves are horizontally symmetrical along the x-axis.
• A non vertical line will intersect an EC in at most 3 points

• An EC cryptosystem can be defined by picking a prime number as a maximum, a curve equation and a public point on the curve called the generator. Аn elliptic curve over a finite field can form a finite cyclic algebraic group, which consists of all the points on the curve. A cyclic group contains an element g (generator), such that that every other element of the group may be obtained by repeatedly applying the group operation to g or its inverse.
• also, $4a^3+27b^2\neq 0$ , this is an edge case, prevents us from using a degenerate curve

Order and Cofactor of Elliptic Curve

• For finite groups, P have the property that if you add P to itself, you eventually get back to the identity, i.e. P, 2P, 3P, 4P,...,m * P = {0, 0} And (m + 1) * P = P, 2P, 3P,.... This m is called the order of P
• There exists a number m such that P * m = 0 for any P (and of course, P * (m+1) = P, P * (7*n + 5) = P * 5, and so on). See explanation below,
  • Example , consider a curve , $y = x^3+3$, here a = 0, b =3.
  • We will use an elliptic curve over the field $F_{101}$
  • Let’s take (1,2) to be the generator of the field , G = (1,2)
  • Then we can find G, 2G, 4G,8G, 16G using point doubling below
  • 16 G = (1,99), - 16G = (1,2)
  • therefore 17G = 0, hence the order of this group is 17, m = 17
  • $18G = P *(n+1) = (1,2)$ will again be equal to Generator (1,2)
• The order of the curve is the total number of all EC points on the curve. This total number of points includes also the special point called "point at infinity", which is obtained when a point is multiplied by 0.
• Some curves form a single cyclic group (holding all their EC points), while others form several non-overlapping cyclic subgroups (each holding a subset of the curve's EC points). In the second scenario the points on the curve are split into h cyclic subgroups (partitions), each of order r (each subgroup holds equal number of points). The order of entire group is n = h * r (the number of subgroups, multiplied by the number of points in each subgroup).
• The number of subgroups h holding the EC points is called cofactor