0
$\begingroup$

Given an elliptic curve $E: y^2 = x^3 + ax + b$ over a finite field $\mathbb{F}_q$ and a point $P$ with coordinates $(x,y)$, we have from the point addition formula that

\begin{align*} 2P =&(\lambda^2-2x,\: \lambda(x-(\lambda^2-2x))-y) \\ =& (\lambda^2-2x,\: \lambda(3x -\lambda^2) -y) \\ =&\left( \left( \frac{3x^2+a}{2y} \right)^2 -2x,\: \frac{3x^2+a}{2y} \left( 3x -\left( \frac{3x^2+a}{2y} \right)^2 \right) -y \right) \\ =& \left( \frac{9x^4+6ax^2+a^2}{4y^2} -2x,\: \frac{3x^2+a}{2y} \left( 3x -\frac{9x^4+6ax^2+a^2}{4y^2} \right) -y \right) \\ =& \left( \frac{9x^4+6ax^2+a^2-8xy^2}{4y^2} ,\: \frac{3x^2+a}{2y} \left( \frac{12xy^2-(9x^4+6ax^2+a^2)}{4y^2} \right) -y \right) \\ =& \left( \frac{9x^4+6ax^2+a^2-8xy^2}{4y^2} ,\: \frac{(3x^2+a)(12xy^2-9x^4-6ax^2-a^2)}{8y^3} -y \right) \\ =& \left( \frac{9x^4+6ax^2+a^2-8xy^2}{4y^2} ,\: \frac{36x^3y^2 -27x^6 -27ax^4 +12axy^2 -9a^2x^2 -a^3}{8y^3} -y \right) \\ =& \left( \frac{9x^4+6ax^2+a^2-8xy^2}{4y^2} ,\: \frac{36x^3y^2 -27x^6 -27ax^4 +12axy^2 -9a^2x^2 -a^3 -8y^4}{8y^3} \right) \\ =& \left( \frac{9x^4+6ax^2+a^2-8xy^2}{(2y)^2} ,\: \frac{36x^3y^2 -27x^6 -27ax^4 +12axy^2 -9a^2x^2 -a^3 -8y^4}{(2y)^3} \right). \end{align*} Since $P$ lies on $E$ we can substitute $y=x^3 +ax + b$, so we have (leaving denominators as they are) \begin{align*} =& \left( \frac{9x^4+6ax^2+a^2-8x(x^3 +ax + b)}{(2y)^2} , \frac{36x^3(x^3 +ax + b) -27x^6 -27ax^4 +12ax(x^3 +ax + b) -9a^2x^2 -a^3 -8(x^3 +ax + b)^2}{(2y)^3} \right) \\ =& \left( \frac{x^4-2ax^2+a^2-8bx}{(2y)^2} ,\: \frac{x^6+5ax^4-5a^2x^2+20bx^3-a^3-4abx-8b^2}{(2y)^3} \right) . \end{align*} So we now have an explicit description of the coordinates of $2P$ in terms of the coordinates of $P$.

However, when I try to find the same thing using division polynomials, I cannot get them to agree. We have $$ 2P = \left( x- \frac{\psi_{1}\psi_3}{\psi_2^2} ,\: \frac{\psi_4}{2\psi_2^4} \right) $$ where $$ \psi_1 = 1, \quad \psi_2 = 2y, \quad \psi_3 = 3x^4 + 6ax^2 + 12bx -a^2, \quad \psi_4 = 4y(x^6 + 5ax^4 +20bx^3 -5a^2x^2 -4abx -8b^2 -a^3). $$ So (doing the algebra in Maple) we find $$ 2P = \left( \frac{-3x^4-6ax^2+(4y^2-12b)x+a^2}{(2y)^2},\: \frac{x^6+5ax^4-5a^2x^2+20bx^3-a^3-4abx}{(2y)^3} \right). $$ Substituting $y^2=x^3 + ax +b$ again and rearranging we can find $$ = \left( \frac{x^4-2ax^2+a^2-8bx}{(2y)^2},\: \frac{x^6+5ax^4-5a^2x^2+20bx^3-a^3-4abx}{(2y)^3} \right), $$ but we're still missing that spurious $-8b^2$ term in the second numerator.

I've checked all my computations in Maple and can't find an arithmetic error, so its more likely to be a mistake in my understand somewhere. What's my error here? Many thanks in advanced.

$\endgroup$
  • $\begingroup$ Those are terribly long and messy computations there. Perhaps a few will even attempt to follow them but it is highly unlikely... Anyway, did you try some examples? Say, $\;y^2=x^3+1\pmod p\;$ for two or three values of the prime $\;p\;$ ? Or maybe some other E.C. ....? $\endgroup$ – DonAntonio Feb 10 '17 at 14:09
  • $\begingroup$ Look after "So (doing the algebra in Maple) we find" in the second numerator where did $-8b^2$ disappear to? It is clearly in $\psi_4$. Could it be you just forget to write it in maple? $\endgroup$ – i9Fn Feb 10 '17 at 14:13
  • $\begingroup$ @i9Fn ah yes, that is undoubtedly the source of my error. I didn't save my worksheet so I can't check what I entered into Maple, but doing it again I find the $-8b^2$ just fine. Thanks for the help and sorry to waste peoples' time with such a trivial error. $\endgroup$ – user406579 Feb 10 '17 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.