For a finite field elliptic curve we have for a curve of \(y^2 = x^3 + ax +b \pmod p\) and for a defined prime number (\(p\)). If we have a point \(P\), we can then calculate \(2P\) (and use this to find \(nP\) - where \(n\) is the number of times we add \(P\)) [Calculating nP] In this case we will add two points on the elliptic curve together to get a resultant point:
ECC Point Addition Calculator |
Coding
In this case we calculate \(x^3+ax+b \pmod p\). We can add two points \((x_1,y_1)\) and \((x_2,y_2)\):
Let \(s = (y_1-y_2)/(x_1-x_2)\)
Then:
\(x_2 = s^2 - x_1 - x_2\)
\(y_2 = s(x_1 - x_2) - y_1\)
import sys import libnum a=0 b=7 p=37 x1=6 x2=8 if (len(sys.argv)>1): x1=int(sys.argv[1]) if (len(sys.argv)>2): x2=int(sys.argv[2]) if (len(sys.argv)>3): p=int(sys.argv[3]) if (len(sys.argv)>4): a=int(sys.argv[4]) if (len(sys.argv)>5): b=int(sys.argv[5]) print("a=",a) print("b=",b) print("p=",p) print("x-point=",x1) print("x-point=",x2) z=(x1**3 + a*x1 +b) % p if (libnum.has_sqrtmod(z,{p:1} )): y1=next(libnum.sqrtmod(z,{p:1})) z=(x2**3 + a*x2 +b) % p if (libnum.has_sqrtmod(z,{p:1} )): y2=next(libnum.sqrtmod(z,{p:1})) print("\nP1\t(%d,%d)" % (x1,y1)) print("P2\t(%d,%d)" % (x2,y2)) s=(y2-y1)* libnum.invmod(x2-x1,p) x3=(s**2-x2-x1) % p y3=((s*(x2-x3)-y2)) % p print("P1+P2\t(%d,%d)" % (x3,y3))
And a sample run:
a= 0 b= 7 p= 37 x-point= 6 x-point= 8 P1 (6,1) P2 (8,1) P1+P2 (23,36)
Presentation
The following is a presentation: