Reduced Elliptic Curve Group

EC Cryptography Tutorials - Herong's Tutorial Examples

∟Reduced Elliptic Curve Group - E127(-1,3)

This section provides an example of a reduced Elliptic Curve group E127(-1,3). An example of addition operation is also provided.

Let's take a look at another reduced elliptic curve group, E₁₂₇(-1,3), as discussed in "Elliptic Curve Cryptography: finite fields and discrete logarithms" by Andrea Corbellini at andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/.

Here is the reduced elliptic curve group using modular arithmetic of prime number 127, E₁₂₇(-1,3):

   y² = x³ - x + 3 (mod 127)

The above diagram provides all points in this group. It also illustrates an example of the reduced addition operation:

Given two points on the curve:
   P = (16,20)
   Q = (41,120)

Draw a straight line passing through A and B,
And wrap the line around when it reaches the boundary of the region.
It will reach another point -R on the curve.
Take the symmetric point R of -R:
   R = A + B
   R = (86,81)

Let's verify R = P+Q using algebraic equations given by the reduced elliptic curve group definition:

For any two given points on the curve:
   P = (x_P, y_P) = (16,20)
   Q = (x_Q, y_Q) = (41,120)

R = P + Q is a third point on the curve:
   R = (x_R, y_R)

Where:
   x_R = m² - x_P - x_Q (mod p)     (11)
   y_R = m(x_P - x_R) - y_P (mod p)  (12)
   m(x_P - x_Q) = y_P - y_Q (mod p)  (18)

Calculation:
   m*(16-41) = 20-120 (mod 127)
   m*(-25) = -100 (mod 127)
   102*m = 27 (mod 127)
   m = 27 * 1/102 (mod 127)
   m = 27*66 (mod 127)
   m = 1782 (mod 127)
   m = 4

   x_R = 4*4 - 16 - 41 = -41 (mod 127)
   x_R = 86

   y_R = 4*(16 - 113) - 20 = -300 (mod 127)
   y_R = 81

   C = (86,81)