Skip to main content
MathOverflow

Return to Question

Notice removed Draw attention by Steffen Plunder
Bounty Ended with Carlo Beenakker's answer chosen by Steffen Plunder
Notice added Draw attention by Steffen Plunder
Bounty Started worth 100 reputation by Steffen Plunder
Brackets in the equation to avoid confusion
Source Link
AVP82000
AVP82000
  • 125
  • 5

I am new to StackExchange and I am currently going through Pierrick'sGaudry'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} $$$$ \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?

I am new to StackExchange and I am currently going through Pierrick'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?

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?

Post Migrated Here from math.stackexchange.com (revisions)
Source Link
AVP82000
AVP82000

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

I am new to StackExchange and I am currently going through Pierrick'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?