For a finite field elliptic curve we have for a curve of \(y^2 = x^3 + ax +b\) 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\)). In this case we will define an x-point on the curve and determine its y co-ordinate and 2P [Real curves]:
Finding 2P when we have P for EC |
Coding
In this case we calculate \(x^3+ax+b \pmod p\). For point addition of \(P\) (\(x,y\)) we calculate the point addition for a given point (\(P+P\)) and represent it by (\(2P\)). For this we have:
\(2P = (x_2, y_2)\)
Let \(s = (3x^2 + a)/(2y)\)
Then:
\(x_2 = s^2 - 2x\)
\(y_2 = s(x - x_2) - y\)
import sys import libnum a=0 b=7 p=37 x=6 if (len(sys.argv)>1): x=int(sys.argv[1]) if (len(sys.argv)>2): p=int(sys.argv[2]) if (len(sys.argv)>3): a=int(sys.argv[3]) if (len(sys.argv)>4): b=int(sys.argv[4]) z=(x**3 + a*x +b) % p if (libnum.has_sqrtmod(z,{p:1} )): y=next(libnum.sqrtmod(z,{p:1})) s=((3*x**2)+a) * libnum.invmod(2*y,p) x2=(s**2-2*x) % p y2=((s*(x-x2))-y) % p print("a=",a) print("b=",b) print("p=",p) print("s=",s) print("\nP=(",x,",",y,")") print("2P=(",x2,",",y2,")") print("\n=== Just checking for (x2, y2).") print("These have to be the same, to prove that 2P is on the elliptic curve:") print("\nx^3+ax+b (mod p)=",(x2**3+a*x+b) % p) print("y^2 (mod p)=", (y2**2)% p)
And a sample run:
a= 0 b= 7 p= 37 s= 29478 P=( 17 , 6 ) 2P=( 13 , 24 ) === Just checking for (x2, y2). These have to be the same, to prove that 2P is on the elliptic curve: x^3+ax+b (mod p)= 21 y^2 (mod p)= 21
Presentation
The following is a presentation: