Python Program for Reduced Elliptic Curves

EC Cryptography Tutorials - Herong's Tutorial Examples

∟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) 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 E₂₃(1,4):

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)