For a finite field elliptic curve we can search for the first 50 points for a curve of \(y^2 = x^3 + ax +b\) and for a defined prime number (\(p\)) [Simple version]:
First 20 Elliptic Curve Points |
Coding
In this case we calculate \(x^3+ax+b \pmod p\) and then determine if we can find a value of \(y\) and equals this when we take \(y^2 \pmod p\). The outline code is:
# https://asecuritysite.com/encryption/ecc_points_real import sys import libnum def findit(start,p,a,b): x=start count=0 while True: val=((x*x*x) + a*x+ b) % p if (val==0): print (x,"0") count=count+1 rtn= libnum.jacobi(val,p) if (rtn==1): res=next(libnum.sqrtmod(val,{p:1})) print("(",x,int(res),")",end='') print("(",x,int(p-res),")",end='') count=count+2 x=x+1 if (count>50 or x==p): return count if (x-start>400): return count p=37 a=0 b=7 if (len(sys.argv)>1): p=int(sys.argv[1]) if (len(sys.argv)>2): a=int(sys.argv[2]) if (len(sys.argv)>3): b=int(sys.argv[3]) print ("Prime number:\t\t\t",p) print ("a,b",a,b) print ("y^2 = x^3 + ax +b (mod p)") count=findit(0,p,a,b) print ("\n\nOrder is ",count)
And a sample run:
Prime number: 37 a,b 0 7 (3, 16) (4, 16) (5, 13) (6, 1) (8, 1) (9, 12) (12, 12) (13, 13) (16, 12) (17, 6) (18, 17) (19, 13) (22, 6) (23, 1) (24, 17) (30, 16) (32, 17) (35, 6)