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?



Schoof's Algorithm for Hyperelliptic curves over $\mathbb{F}_q$ : Question regarding computation of resultant: Gaudry
*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](https://hal.inria.fr/inria-00512403/document) 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.


