[Back] 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 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]) def modular_sqrt(a, p): """ Find a quadratic residue (mod p) of 'a'. p must be an odd prime. Solve the congruence of the form: x^2 = a (mod p) And returns x. Note that p - x is also a root. 0 is returned is no square root exists for these a and p. The Tonelli-Shanks algorithm is used (except for some simple cases in which the solution is known from an identity). This algorithm runs in polynomial time (unless the generalized Riemann hypothesis is false). """ # Simple cases # if legendre_symbol(a, p) != 1: return 0 elif a == 0: return 0 elif p == 2: return p elif p % 4 == 3: return pow(a, (p + 1) / 4, p) # Partition p-1 to s * 2^e for an odd s (i.e. # reduce all the powers of 2 from p-1) # s = p - 1 e = 0 while s % 2 == 0: s /= 2 e += 1 # Find some 'n' with a legendre symbol n|p = -1. # Shouldn't take long. # n = 2 while legendre_symbol(n, p) != -1: n += 1 # Here be dragons! # Read the paper "Square roots from 1; 24, 51, # 10 to Dan Shanks" by Ezra Brown for more # information # # x is a guess of the square root that gets better # with each iteration. # b is the "fudge factor" - by how much we're off # with the guess. The invariant x^2 = ab (mod p) # is maintained throughout the loop. # g is used for successive powers of n to update # both a and b # r is the exponent - decreases with each update # x = pow(a, (s + 1) / 2, p) b = pow(a, s, p) g = pow(n, s, p) r = e while True: t = b m = 0 for m in xrange(r): if t == 1: break t = pow(t, 2, p) if m == 0: return x gs = pow(g, 2 ** (r - m - 1), p) g = (gs * gs) % p x = (x * gs) % p b = (b * g) % p r = m def legendre_symbol(a, p): """ Compute the Legendre symbol a|p using Euler's criterion. p is a prime, a is relatively prime to p (if p divides a, then a|p = 0) Returns 1 if a has a square root modulo p, -1 otherwise. """ ls = pow(a, (p - 1) / 2, p) return -1 if ls == p - 1 else ls def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(a, m): g, x, y = egcd(a, m) if g != 1: print "x-point is not on the curve. Please select another point." sys.exit() else: return x % m z=(x**3 + a*x +b) % p y=modular_sqrt(z, p) s=((3*x**2)+a) * modinv(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: