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

Curves over finite and local fields (11G20) Number-theoretic algorithms; complexity (11Y16) Jacobians, Prym varieties (14H40) 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

• Arithmetic on superelliptic curves
• Computing in the Jacobian of a Hyperelliptic Curve
• Computing Riemann-Roch spaces in algebraic function fields and related topics.
• Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve
• 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?)
• Néron Models

Cited in

(35)

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