On Jacobian group arithmetic for typical divisors on curves (Q2316147)

Let \(C\) be a smooth projective algebraic curve of genus \(\geq 1\) over a field \(K\), and \(C\) has a \(K\)-rational point \(P_{\infty}\). In case where \(K\) is a large finite field, previous results on certain degree 3 covers of \(P^1\) give fast algorithms for Jacobian group arithmetic under the hypothesis that the pairs of divisors one encounters are typical, and that the result of the group operation is typical. On the other hand, there is not a test to verify whether the input divisors or output data are typical and so, the algorithms might return wrong results without this being detected during the computation. In this paper, an explicit condition for a divisor to be typical, for arbitrary \(C\) is obtained. For the case of \(C_{3,4}\) curves two inversions and approximately 125 multiplications in \(K\) per group operation in the Jacobian of a \(C_{3,4}\) curve give correct results and yield typical divisors as output, provided that both inversions can be carried out. For an arbitrary curve \(C\) with a distinguished point \(P_{\infty}\), a modification of the algorithms described in [\textit{F. K. A. Salem} and \textit{K. Khuri-Makdisi}, LMS J. Comput. Math. 10, 307--328 (2007; Zbl 1221.14062)] that allows us to carry out Jacobian arithmetic for typical elements is presented. Furthermore, a nontrivial speedup of this algorithms that saves 19 multiplications in \(K\) per operation in the Jacobian, a speedup of approximately 15\%, is given.