TITLE: Schoof's Algorithm for Hyperelliptic curves over $\mathbb{F}_q$ : Question regarding computation of resultant: Gaudry
QUESTION [7 upvotes]: 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?

REPLY [4 votes]: 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.
{"set_name": "stack_exchange", "score": 7, "question_id": 315009}