EC Cryptography Tutorials - Herong's Tutorial Examples - v1.02, by Dr. Herong Yang
Elliptic Curves in Integer Space
This section describes the fact that elliptic equations in 2-dimensional integer space can not be used to construct Abelian groups.
Earlier in the book, we learned how to use elliptic equations in 2-dimensional real number space to construct Abelian groups.
Can we use elliptic equations in 2-dimensional integer space to construct an Abelian group?
Let's try to define an element set with elliptic equations in 2-dimensional integer space and the same rule of chord operation.
Element Set:
All P = (x,y), such that:
y2 = x3 + ax + b
where:
a and b are integers
4a3 + 27b2 != 0
x and y are integers
Operation:
Rule of chord
Identity Element:
The infinite point of 0 = (∞, ∞)
Is the above definition provides any Abelian Groups? The answer is no.
Let's take (a,b) = (1,4) as an example:
All P = (x,y), such that: y2 = x3 + x + 4 where: x and y are integers
We can see that P = (0,2) is a valid element in the set, because it satisfy the curve equation:
22 = 03 + 0 + 4
If P = (0,2) in the element set, 2P = P + P must be in the element set too because of the "Closure" condition of Abelian groups. So let's verify this by calculating 2P using the algebraic equations provided earlier in the book, assuming 2P = R = (xR, yR):
xR = m2 - 2xP (4) yR = m(xP - xR) - yP (5) 3(xP)2 + a m = --------- (6) 2(yP)
Here is the result of the calculation:
Calculation using equations (4), (5), and (6): m = (3*0*0 + 1)/(2*2) = 1/4 xR = (1/4)*(1/4) - 2*0 = 1/16 yR = (1/4)*(0 - 1/16) - 2 = -1/64 - 2 = -129/64 Result: 2P = R = (xR, yR) = (1/16, -129/64) Verification to see if (x, y) = (1/16, -129/64) is on the curve: y2 = x3 + x + 4 (-129/64)*(-129/64) = (1/16)*(1/16)*(1/16) + 1/16 + 4 16641/4096 = 1/4096 + 256/4096 + 16384/4096 16641/4096 = 16641/4096 Result: (x, y) = (1/16, -129/64) is on the curve
But (x, y) = (1/16, -129/64) is not in the element set, because its coordinates are not integers!
So elliptic equations in 2-dimensional integer space can not be used to construct Abelian groups.
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 - E23(1,4)
Reduced Elliptic Curve Group - E97(-1,1)
Reduced Elliptic Curve Group - E127(-1,3)
Reduced Elliptic Curve Group - E1931(443,1045)
Finite Elliptic Curve Group, Eq(a,b), q = p^n
tinyec - Python Library for ECC
ECDH (Elliptic Curve Diffie-Hellman) Key Exchange
ECDSA (Elliptic Curve Digital Signature Algorithm)