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),
