Multi-Page Printing

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 4y2 0 = 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 = t2, i 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 − t2 i = 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),