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),
Previous Page Next Page