Schoof's Algorithm for Hyperelliptic curves over $\mathbb{F}_q$ : Question regarding computation of resultant: Gaudry

Question

I am new to StackExchange and I am currently going through Gaudry's paper on counting points on hyperelliptic curves (see https://hal.inria.fr/inria-00512403/document). As a part of the generalization of Schoof s algorithm for genus 2, we have to compute l-torsion points. For this we use Cantor s division polynomials, and the problem reduces to solving the following two equations: $$ \begin{align} E_1(x_1,x_2) &= (d_1(x_1)d_2(x_2)-d_1(x_2)d_2(x_1))/ \langle x_1-x_2 \rangle = 0 \\ E_2(x_1,x_2) &= (d_0(x_1)d_2(x_2)-d_0(x_2)d_2(x_1))/\langle x_1-x_2 \rangle =0 \end{align} $$ where deg($d_0$)=$2l^2-1$, deg($d_1$)=$2l^2-2$, deg($d_2$)=$2l^2-3$. We eliminate $x_2$ by computing the resultant wrt to $x_2$ denoted as $R(x_1)$.

I understood that the maximum degree of $R(x_1)$ is $ 2(2l^2-3)(2l^2-2)$. Then the author claims that a high power of $d_2(x_1)$ denoted as $\delta$ divides $R(x_1)$ and $\delta = 2l^2 - 2$ and in some current papers $\delta = 2l^2 -3$.

I fail to understand how they could compute $\delta$ and is the degree of $R(x_1)$ its maximum degree?

Answer 1

Answer:

The resultant $R(x_1)$ vanishes at $x_1=X_1$ iff $E_1(X_1,x_2)=0=E_2(X_1,x_2)$ for some $x_2=X_2$. Take $X_2$ to be one of the $\delta={\rm deg}\,(d_2)=2l^2-3$ roots of the polynomial $d_2$. Then $E_1(x_1,X_2)$ and $E_2(x_1,X_2)$ vanish if $d_2(x_1)=0$, so $d_2(x_1)$ is a factor of $R(x_1)$ with multiplicity $\delta$.

---

Discussion:

This answer $\delta=2l^2-3$ differs from the value $2l^2-2$ given in the cited paper by Gaudry and Harley, so as a test I used Mathematica to calculate the resultant for a simple case of $l=2$:

$$d_0(x)=x^7+x^6+x^5+x^4+x^3+x^2+2 x+1$$ $$d_1(x)=x^6+x^5+x^4+x^3+x^2+x+1$$ $$d_2(x)=x^5+x^4+x^3+x^2+2 x+1$$

These three polynomials are irreducible, of degrees ${\rm deg}(d_0)=2l^2-1=7$, ${\rm deg}(d_1)=2l^2-2=6$, and ${\rm deg}(d_2)=2l^2-3=5$. The resultant over $x_2$ of

\begin{align} E_1(x_1,x_2) &= [d_1(x_1)d_2(x_2)-d_1(x_2)d_2(x_1)] (x_1-x_2 )^{-1} \\ E_2(x_1,x_2) &= [d_0(x_1)d_2(x_2)-d_0(x_2)d_2(x_1)](x_1-x_2 )^{-1} \end{align}

equals

_{$$R(x_1)=\left(x_1^5+x_1^4+x_1^3+x_1^2+2 x_1+1\right)^5 \left(7 x_1^{30}+19 x_1^{29}+43 x_1^{28}+79 x_1^{27}+127 x_1^{26}+188 x_1^{25}+286 x_1^{24}+384 x_1^{23}+491 x_1^{22}+591 x_1^{21}+675 x_1^{20}+736 x_1^{19}+805 x_1^{18}+804 x_1^{17}+774 x_1^{16}+713 x_1^{15}+630 x_1^{14}+531 x_1^{13}+455 x_1^{12}+342 x_1^{11}+250 x_1^{10}+175 x_1^9+117 x_1^8+72 x_1^7+52 x_1^6+24 x_1^5+12 x_1^4+6 x_1^3+3 x_1^2+x_1+2\right)$$}

So indeed, $R(x_1)$ contains a factor $d_2(x_1)$ to the power $\delta=2l^2-3$.

The quotient $$\tilde{R}(x_1)=\frac{R(x_1)}{[d_2(x_1)]^\delta}$$ is an irreducible polynomial of degree $30$, in accord with the value $4l^4-10l^2+6$ in Gaudry & Harley. I would conclude that their value of $\delta$ is simply a misprint. Note that the degree of $\tilde{R}$ is one half the maximum degree of $R$ mentioned in the OP.