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