Linearizing torsion classes in the Picard group of algebraic curves over finite fields (Q1024380)

This article describes algorithms for computing in Picard groups of algebraic curves over finite fields. Fix a finite field \(\mathbb F_{q}\) and let \(C \subset \mathbb P^{2}_{\mathbb F_{q}}\) be a geometrically integral curve of degree \(d\) and geometric genus \(g\) with smooth model \(\mathcal X\). After recalling how computations are done in the Jacobian variety \(\mathcal J = \mathcal J (\mathcal X)\) [\textit{E. Volcheck}, Lect. Notes Comput. Sci. 877, 221--233 (1994; Zbl 0826.14040)] and how to compute the Weil pairing on the \(n\)-torsion points \(\mathcal J [n]\) [\textit{A. Menezes, T. Okamoto}, and \textit{S. Vanstone}, IEEE Trans. Inf. Theory 39, 1639--1646 (1993; Zbl 0801.94011)], the author computes the general Kummer map \(K_{n,q}: \mathcal J /n \mathcal J \to \mathcal J [n]\) when \(\mathcal J [n]\) splits completely over \(\mathbb F_{q}\) and more specifically the Kummer map for an \(l\)-divisible subgroup \(\mathbb G \subset \mathcal J [l^{\infty}]\) with \(l\) a prime not dividing \(q\). For a power \(l^{k}\) of such a prime, the main result is a Monte Carlo algorithm that that gives divisor classes \(g_{i}\) in the Picard group of \(\mathcal X/\mathbb F_{q}\) such that \({\roman {Pic}}(\mathcal X/\mathbb F_{q}) [l^{k}]\) is the direct product of the cyclic groups \(<g_{i}>\) with non-decreasing orders. The algorithm runs in (probabilistic) polynomial time in \(d,g,\log q\) and \(l^{k}\) and delivers the correct answer with probability \(\geq \frac{1}{2}\). An algorithm is also given which computes the Ramanujan subspace.