54 2. Elliptic curves

it is enough to show that x(2P ) = x1, because 2P is a point on E(Q)

and if x(2P ) = x(Q), then Q = 2(±P). Hence, our goal will be to

construct (x0,y0) ∈ E(Q) such that

x(2P ) =

x0

4

− 2Ax0

2

− 8Bx0 +

A2

4y0 2

= x1.

The formula for x(2P ) above is given in Exercise 2.12.16.

Once again, for simplicity, let us assume y(Q) = y1 = 0 and, as

stated above, we assume δ(Q) = (1,1,1). Hence, x1 − ei is a square

in Q for i = 1,2,3. Let us write

x1 − ei = ti

2,

for some ti ∈

Q×.

(2.6)

We define a new auxiliary polynomial p(x) by

t1

(x − e2)(x − e3)

(e1 − e2)(e1 − e3)

+ t2

(x − e1)(x − e3)

(e2 − e1)(e2 − e3)

+ t3

(x − e1)(x − e2)

(e3 − e1)(e3 − e2)

.

The polynomial p(x) is an interpolating polynomial (or Lagrange

polynomial) which was defined so that p(ei) = ti. Notice that p(x) is

a quadratic polynomial, say p(x) = a + bx +

cx2.

Also define another

polynomial q(x) = x1 − x −

p(x)2

and notice that

q(ei) = x1 − ei −

p(ei)2

= x1 − ei − ti

2

= 0

from the definition of ti in Eq. (2.6). Since q(ei) = 0, it follows that

(x − ei) divides q(x) for i = 1,2,3. Thus, (x − e1)(x − e2)(x − e3) =

x3

+Ax+B divides q(x). In other words, q(x) ≡ 0 mod

x3

+Ax+B.

Since q(x) = x1 − x −

p(x)2,

we can also write

x1 − x ≡

p(x)2

≡ (a + bx +

cx2)2

mod

(x3

+ Ax + B).

We shall expand the square on the right-hand side, modulo f(x) =

x3

+ Ax + B. Notice that

x3

≡ −Ax − B, and

x4

≡

−Ax2

− Bx

modulo f(x):

x1 − x ≡

p(x)2

≡ (a + bx +

cx2)2

≡

c2x4

+

2bcx3

+ (2ac +

b2)x2

+ 2abx +

a2

≡

c2(−Ax2

− Bx) + 2bc(−Ax − B)

+(2ac +

b2)x2

+ 2abx +

a2

≡ (2ac +

b2

−

Ac2)x2

+(2ab −

Bc2

− 2Abc)x +

(a2

− 2bcB),