Python Program for Reduced Elliptic Curves

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

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

```# ReducedEllipticCurve.py
#
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):

```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.