# Elliptic curve point multiplication with division polynomials

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.

• 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. ....? – DonAntonio Feb 10 '17 at 14:09
• 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? – i9Fn Feb 10 '17 at 14:13
• @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. – user406579 Feb 10 '17 at 16:23