**EC Cryptography Tutorials - Herong's Tutorial Examples** - v1.03, by Herong Yang

Reduced Point Additive Operation

This section describes what is the reduced point additive operation in algebraic format, which is the same as the original additive operation reduced by modular arithmetic of prime number p.

From the previous tutorial, we learned that the original additive operation based on the rule of chord operation failed to construct an Abelian group on a reduced elliptic curve.

Let's look at the algebraic equations for the additive operation presented earlier in the book again:

Original addition operation based rule of chord operation: For any two given points on the curve: P = (x_{P}, y_{P}) Q = (x_{Q}, y_{Q}) R = P + Q is a third point on the curve: R = (x_{R}, y_{R}) Where: x_{R}= m^{2}- x_{P}- x_{Q}(8) y_{R}= m(x_{P}- x_{R}) - y_{P}(9) If P != Q, m is determined by: y_{P}- y_{Q}m = --------- (10) x_{P}- x_{Q}If P = Q, m is determined by: 3(x_{P})^{2}+ a m = --------- (6) 2(y_{P})

The issue with this addition operation is that the resulting point R is not an integer point and it is not in the first region of [(0,0) ... (p-1,p-1)]!

One quick way to resolve the issue to apply the same modular arithmetic reduction
as the reduced elliptic equation on coordinates (x_{R}, y_{R})
of the resulting point R. This will bring it into the first region as an integer point.

Reduced addition operation based rule of chord operation: For any two given points on the curve: P = (x_{P}, y_{P}) Q = (x_{Q}, y_{Q}) R = P + Q is a third point on the curve: R = (x_{R}, y_{R}) Where: x_{R}= m^{2}- x_{P}- x_{Q}(mod p) (11) y_{R}= m(x_{P}- x_{R}) - y_{P}(mod p) (12) If P != Q, m is determined by: y_{P}- y_{Q}m = --------- (10) x_{P}- x_{Q}If P = Q, m is determined by: 3(x_{P})^{2}+ a m = --------- (6) 2(y_{P})

If m is an integer, (x_{R}, y_{R}) of the resulting point R
will be integers. Applying modular arithmetic reduction on integers is easy.

However, if m is a rational number, (x_{R}, y_{R}) of the result point R
will be rational numbers.
Applying modular arithmetic reduction on rational numbers is tricky.
We will discuss it in the next tutorial.

By the way, m will never be a true real number. Because P and Q are integer points and coefficients of the elliptic curve are integers. Equation (10) or (6) will only results to integers or rational numbers.

After reducing the resulting point to an integer point in the first region, we need to proof that it is still on the reduced elliptic curve. See next tutorials for more details.

Table of Contents

Geometric Introduction to Elliptic Curves

Algebraic Introduction to Elliptic Curves

Abelian Group and Elliptic Curves

Discrete Logarithm Problem (DLP)

Generators and Cyclic Subgroups

►Reduced Elliptic Curve Groups

Converting Elliptic Curve Groups

Elliptic Curves in Integer Space

Python Program for Integer Elliptic Curves

Elliptic Curves Reduced by Modular Arithmetic

Python Program for Reduced Elliptic Curves

Point Pattern of Reduced Elliptic Curves

Integer Points of First Region as Element Set

►Reduced Point Additive Operation

Modular Arithmetic Reduction on Rational Numbers

Reduced Point Additive Operation Improved

What Is Reduced Elliptic Curve Group

Reduced Elliptic Curve Group - E_{23}(1,4)

Reduced Elliptic Curve Group - E_{97}(-1,1)

Reduced Elliptic Curve Group - E_{127}(-1,3)

Reduced Elliptic Curve Group - E_{1931}(443,1045)

Finite Elliptic Curve Group, E_{q}(a,b), q = p^{n}

tinyec - Python Library for ECC

ECDH (Elliptic Curve Diffie-Hellman) Key Exchange

ECDSA (Elliptic Curve Digital Signature Algorithm)