Python Program for Reduced Elliptic Curves

This section provides a Python program that finds all points on a reduced elliptic curve group, Ep(a,b).

I implemented the algorithm presented in the previous tutorial in a Python program:

# ReducedEllipticCurve.py
# Copyright (c) 2018, HerongYang.com, All Rights Reserved.
#
import sys

if (len(sys.argv) < 4):
   print("Usage: python ReducedEllipticCurve.py a b p")
   exit()

aa = sys.argv[1]
bb = sys.argv[2]
pp = sys.argv[3]
a = int(aa)
b = int(bb)
p = int(pp)

r = 4*a**3 + 27*b**2
if (r == 0): 
   print("Error: (a, b) = ("+aa+", "+bb+") and 4a^3 + 27b^2 == 0")
   exit()
   
if (p < 3): 
   print("Error: p = "+pp+" is too small")
   exit()

print("Elliptic equation: y^2 = x^3 + ax + b with (a, b) = ("
   +aa+", "+bb+")")
print("Modular arithmetic: p = "+pp)

# Possible left hand side values
left = []
lMap = {}
for i in range(0,int((p+1)/2)):
   l = (i*i) % p
   left.append(l)
   if (l in lMap):
      lMap[l].append(i)
   else:
      lMap[l] = [i]
print("Left hand side: "+str(lMap))

# Possible right hand side values
right = []
rMap = {}
for i in range(0,p):
   r = (i*i*i+a*i+b) % p
   right.append(r)
   if (r in rMap):
      rMap[r].append(i)
   else:
      rMap[r] = [i]
print("Right hand side: "+str(rMap))

# Common values
left = list(set(left))
right = list(set(right))
left.sort()
right.sort()
common = []
j = 0
for i in range(0,len(left)):
   while (j<len(right) and left[i]>right[j] ):
      j = j+1
   if (j<len(right) and left[i]==right[j]): 
      common.append(left[i])
print("Common values: "+str(common))

print("Elliptic curve group points:")
width = str(len(str(p)))
word = "({:"+width+"d},{:"+width+"d})"
blank = "("+("-"*len(str(p)))+","+("-"*len(str(p)))+")"
count = 0
k = 0
line = ""
while (k<len(common)):
   c = common[k]
   for i in range(0,len(rMap[c])):
      x = rMap[c][i]
      for j in range(0,len(lMap[c])):
         y = lMap[c][j]
         line = line+"  "+word.format(x,y)
         if (y>0):
            line = line+"  "+word.format(x,p-y)
         if (y==0):
            word.format(x,y) 
            line = line+"  "+blank
         count = count+2
         if (count%6 == 0):
            print(line)
            line = ""       
   k = k+1
print(line)

Let's verify this program with E23(1,4):

C:\herong> python ReducedEllipticCurve.py 1 4 23

Elliptic equation: y^2 = x^3 + ax + b with (a, b) = (1, 4)
Modular arithmetic: p = 23

Left hand side: 
   {0: [0], 1: [1], 4: [2], 9: [3], 16: [4], 2: [5], 13: [6], 
    3: [7], 18: [8], 12: [9], 8: [10], 6: [11]}
    
Right hand side: 
   {4: [0], 6: [1, 9, 13], 14: [2], 11: [3], 3: [4], 19: [5, 6, 12], 
    9: [7], 18: [8], 2: [10, 14, 22], 12: [11, 17, 18], 13: [15], 
   22: [16], 5: [19], 20: [20], 17: [21]}
   
Common values: [2, 3, 4, 6, 9, 12, 13, 18]

Elliptic curve group points:
  (10, 5)  (10,18)  (14, 5)  (14,18)  (22, 5)  (22,18)
  ( 4, 7)  ( 4,16)  ( 0, 2)  ( 0,21)  ( 1,11)  ( 1,12)
  ( 9,11)  ( 9,12)  (13,11)  (13,12)  ( 7, 3)  ( 7,20)
  (11, 9)  (11,14)  (17, 9)  (17,14)  (18, 9)  (18,14)
  (15, 6)  (15,17)  ( 8, 8)  ( 8,15)

The output matches well with my manual calculation! So I assume the program works.

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