Bisection and squares in genus 2 (Q747978)

Let \(q\) be a power of an odd prime, \(\mathbb F_q\) the finite field of \(q\) elements and consider a curve over \(\mathbb F_q\), \(C : y^2=f(x)\) of genus 2, so that \(\deg f =5\) or \(6\). A divisor \(D_2\) in the Jacobian of \(C\) has a Mumford representation as \([u_2(x), v_2(x)]\) where \(u_2, v_2\) are polynomials over \(\mathbb F_q\), \(f(x)\equiv v_2(x)^2\pmod{u_2(x)}\), \(u_2\) is monic and \(\deg v_2<\deg u_2\leq 2\) (it is slightly different if \(\deg f=6\) and the support of \(D_2\) includes points at infinity). The goal is to find bisections of \(D_2\), that is, divisors \(D_1\) such that \(2D_1=D_2\). Let \(\varphi (x)\) be an irreducible factor, over \(\mathbb F_q\), of \(f(x)\). Define \(N_{\varphi}(u_2)=\prod u_2(\theta_j)\), the product over the roots of \(\varphi\) in a splitting field. Suppose the support of \(D_2\) contains two affine points (the case of less than two affine points is done differently). The main result when \(\deg f=5\) is: \(D_2\) has a bisection iff for any irreducible factor \(\varphi\) of \(f\), \(N_{\varphi}(u_2)\) is a square in \(\mathbb F_q\). The statement for \(\deg f=6\) is slightly more complicated when there are factors of odd degree. This leads to an efficient method of computing bisections that requires finding at most five square roots over the splitting field of \(f(x)\) plus the solution of a system of linear equations.