Linear algebra algorithms for divisors on an algebraic curve

DOI10.1090/S0025-5718-03-01567-9MaRDI QIDQ4433136zbMATH OpenFDO

Authors Kamal Khuri-Makdisi

Publication date 29 October 2003

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

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

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)

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)$.

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

Cites work

• scientific article; zbMATH DE number 1643937 (Why is no real title available?)
• scientific article; zbMATH DE number 3891516 (Why is no real title available?)
• scientific article; zbMATH DE number 3959303 (Why is no real title available?)
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• scientific article; zbMATH DE number 529172 (Why is no real title available?)
• scientific article; zbMATH DE number 1519869 (Why is no real title available?)
• scientific article; zbMATH DE number 790015 (Why is no real title available?)
• scientific article; zbMATH DE number 799760 (Why is no real title available?)
• scientific article; zbMATH DE number 799781 (Why is no real title available?)
• Arithmetic on superelliptic curves
• Computing Riemann-Roch spaces in algebraic function fields and related topics.
• Computing in the Jacobian of a Hyperelliptic Curve
• Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve
• Néron Models

Cited in

(31)

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

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)