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 = (xP, yP)
   Q = (xQ, yQ)
  
R = P + Q is a third point on the curve: 
   R = (xR, yR)

Where:    
   xR = m2 - xP - xQ              (8)
   yR = m(xP - xR) - yP           (9)   
   
If P != Q, m is determined by:
       yP - yQ 
   m = ---------                (10)
       xP - xQ

If P = Q, m is determined by:
       3(xP)2 + a
   m = ---------                 (6)
         2(yP) 

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 (xR, yR) 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 = (xP, yP)
   Q = (xQ, yQ)
  
R = P + Q is a third point on the curve: 
   R = (xR, yR)

Where:    
   xR = m2 - xP - xQ (mod p)     (11)
   yR = m(xP - xR) - yP (mod p)  (12)   
   
If P != Q, m is determined by:
       yP - yQ 
   m = ---------                (10)
       xP - xQ

If P = Q, m is determined by:
       3(xP)2 + a
   m = ---------                 (6)
         2(yP) 

If m is an integer, (xR, yR) of the resulting point R will be integers. Applying modular arithmetic reduction on integers is easy.

However, if m is rational number, (xR, yR) 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.

Last update: 2019.

Table of Contents

 About This Book

 Geometric Introduction to Elliptic Curves

 Algebraic Introduction to Elliptic Curves

 Abelian Group and Elliptic Curves

 Discrete Logarithm Problem (DLP)

 Finite Fields

 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 - E23(1,4)

 Reduced Elliptic Curve Group - E97(-1,1)

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

 Reduced Elliptic Curve Group - E1931(443,1045)

 What Is Hasse's Theorem

 Finite Elliptic Curve Group, Eq(a,b), q = p^n

 Elliptic Curve Subgroups

 tinyec - Python Library for ECC

 EC (Elliptic Curve) Key Pair

 ECDH (Elliptic Curve Diffie-Hellman) Key Exchange

 ECDSA (Elliptic Curve Digital Signature Algorithm)

 ECES (Elliptic Curve Encryption Scheme)

 Terminology

 References

 Full Version in PDF/EPUB