Bisection and squares in genus 2

We show how to compute the pre-images of multiplication-by-2 in Jacobians of genus 2 curves C : y(2) = f (x) over F-q with q odd. We characterize D = [u(x),v(x)] is an element of 2Jac(C)(F-q) in terms of the quadratic character of u(x) at the roots of f (x) in imaginary models, and in terms of the quadratic character of the quotients of u(x) at pairs of roots of f (x) in real models. Our method reduces the problem to the computation of at most 5 square roots over the splitting field of f(x) plus the solution of a system of linear equations. (C) 2015 Elsevier Inc. All rights reserved.