Suppose that I have $E$ which is an elliptic curve over finite field $\mathbb F_{23}$ expressed by the equation: $$E: y^2=x^3+7$$

The $n^{th}$ division polynomials $\psi_n$ are defined with:$$\psi_1=1$$ $$\psi_2=2y$$ $$\psi_3=3x^4+6ax^2+12bx-a^2$$ $$\psi_4=4y(x^6+5ax^4+20bx^3-5a^2x^2-4abx-8b^2-a^3)$$ $$\psi_{2m+1}=\psi_{m+2}\psi^3_m\psi_{m-1}\psi^3_{m+1}$$ $$\psi_{2m}=(2y)^{-1}(\psi_{m+2}\psi^2_{m-1}-\psi_{m-2}\psi^2_{m+1})\psi_m$$

In some papers there is a definition:

$\psi_n=y(nx^{(n^2-4)/2})$+(lower degree terms) for $n$ is even and:

$\psi_n=nx^{(n^2-1)/2}$+(lower degree terms) for $n$ is odd

Division polynomial is multivariate one(integers a,b,x,y is "input"). So all division polynomials can be rewritten to:$$\sum_{i_1,i_2,i_3,i_4=0}^n=a_{i_1i_2i_3i_4}x^{i_1}y^{i_2}A^{i_3}B^{i_4}$$

(from the definition of the polynomial)

My question is whether it is possible to derive equation for lower $n$-th degree terms just like equation for leading term written above to have full polynomial equation? If no, why leading term can be derived and lower terms cannot?

As far as I know all division polynomials form an polynomial ring. According to this paper (Lemma 2.1.5) for $n$ is odd $\psi_n$ is in $\mathbb Z[A,B,x,y^2]$ (in case of this finite field $\mathbb F_{23}[A,B,x,y^2]$) and for $n$ is even $(2y)^{-1}\psi_n$ is in $\mathbb F_{23}[A,B,x,y^2]$. Since $y^2=x^3+Ax+B$ the ring is in the form of $\mathbb F_{23}[A,B,x]$. So I had an idea to manage it from that ring which have coefficients to $\psi_n$ since $\mathbb F_{23}[A,B,x]$ is isomorphic to $\mathbb F_{23}[A][B][x]$ but I have trouble understanding it. And polynomial ring was my first idea for initial approach to the problem so my reasoning may be wrong.


1 Answer 1


Yes, you can do as you say, and write all odd division polynomials $\psi_n$ (or $(2y)^{-1}\psi_n$ for even $n$) for $y^2=x^3+Ax+B$ (or a long Weierstrass equation if needed) as polynomials in the ring $\mathbb{Z}[A,B,x]$. However, the polynomials are defined recursively, so I have never seen a closed formula for the $n$-th division polynomial. The highest-order term can be derived from the theory of formal groups for instance, but the lower order terms are messy... For example, here is $\psi_5(x)$: $$5x^{12} + 62Ax^{10} + 380Bx^9 - 105A^2x^8 + 240ABx^7 + (-300A^3 - 240B^2)x^6 - 696A^2Bx^5 + (-125A^4 - 1920AB^2)x^4 + (-80A^3B - 1600B^3)x^3 + (-50A^5 - 240A^2B^2)x^2 + (-100A^4B - 640AB^3)x + A^6 - 32A^3B^2 - 256B^4.$$ You can use a computer to compute any given division polynomial in $\mathbb{Z}[A,B,x]$. For example, I used Magma to compute the one above, using the following code:


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .