Linear algebra algorithms for divisors on an algebraic curve

DOI10.1090/S0025-5718-03-01567-9zbMATH Open1095.14057arXivmath/0105182MaRDI QIDQ4433136FDOQ4433136

Kamal Khuri-Makdisi

Publication date: 29 October 2003

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: We use an embedding of the symmetric $d$th power of any algebraic curve $C$ of genus $g$ into a Grassmannian space to give algorithms for working with divisors on $C$, using only linear algebra in vector spaces of dimension $O(g)$, and matrices of size $O(g^2)imesO(g)$. When the base field $k$ is finite, or if $C$ has a rational point over $k$, these give algorithms for working on the Jacobian of $C$ that require $O(g^4)$ field operations, arising from the Gaussian elimination. Our point of view is strongly geometric, and our representation of points on the Jacobian is fairly simple to work with; in particular, none of our algorithms involves arithmetic with polynomials. We note that our algorithms have the same asymptotic complexity for general curves as the more algebraic algorithms in Hess' 1999 Ph.D. thesis, which works with function fields as extensions of $k[x]$. However, for special classes of curves, Hess' algorithms are asymptotically more efficient than ours, generalizing other known efficient algorithms for special classes of curves, such as hyperelliptic curves (Cantor), superelliptic curves (Galbraith, Paulus, and Smart), and $C_{ab}$ curves (Harasawa and Suzuki); in all those cases, one can attain a complexity of $O(g^2)$.

Full work available at URL: https://arxiv.org/abs/math/0105182

Recommendations

• Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve
• Linearizing torsion classes in the Picard group of algebraic curves over finite fields
• Asymptotically fast group operations on Jacobians of general curves
• A fast randomized geometric algorithm for computing Riemann-Roch spaces
• scientific article; zbMATH DE number 799781

Mathematics Subject Classification ID

Jacobians, Prym varieties (14H40) Curves over finite and local fields (11G20) Number-theoretic algorithms; complexity (11Y16) Computational aspects of algebraic curves (14Q05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing in the Jacobian of a Hyperelliptic Curve
• Néron Models
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing Riemann-Roch spaces in algebraic function fields and related topics.
• Title not available (Why is that?)
• Arithmetic on superelliptic curves
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve
• Title not available (Why is that?)

Cited In (31)

• Generators of graded rings of modular forms
• Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve
• Study of Semi-projective Retractable Modules
• Essentially slightly compressible modules and rings.
• Asymptotically-good arithmetic secret sharing over \(\mathbb{Z}/p^{\ell }\mathbb{Z}\) with strong multiplication and its applications to efficient MPC
• Overview of the Work of Kumar Murty
• Upper bounds for some Brill–Noether loci over a finite field
• Geometric quadratic Chabauty and \(p\)-adic heights
• Moduli interpretation of Eisenstein series
• Rigorous computation of the endomorphism ring of a Jacobian
• Approximating Euler products and class number computation in algebraic function fields
• Two Recent p-adic Approaches Towards the (Effective) Mordell Conjecture
• Halving for the 2-Sylow subgroup of genus 2 curves over binary fields
• Linearizing torsion classes in the Picard group of algebraic curves over finite fields
• Asymptotically fast group operations on Jacobians of general curves
• Hensel-lifting torsion points on Jacobians and Galois representations
• On spaces of modular forms spanned by eta-quotients
• Division algorithm and construction of curves with many points
• On Jacobian group arithmetic for typical divisors on curves
• Group Law Computations on Jacobians of Hyperelliptic Curves
• The arithmetic of Jacobian groups of superelliptic cubics
• Explicit Arithmetic on Abelian Varieties
• ON THE MAPS FROM X(4p) TO X(4)
• Factoring polynomials over finite fields
• A geometric linear Chabauty comparison theorem
• Moduli-friendly Eisenstein series over the \(p\)-adics and the computation of modular Galois representations
• Title not available (Why is that?)
• Computing modular Galois representations
• Fast Jacobian Group Operations for C_3,4 Curves over a Large Finite Field
• Computing an order-complete basis for \(M^{\infty}(N)\) and applications
• Computing in Picard groups of projective curves over finite fields

This page was built for publication: Linear algebra algorithms for divisors on an algebraic curve

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4433136)