A fast randomized geometric algorithm for computing Riemann-Roch spaces

DOI10.1090/MCOM/3517zbMATH1454.14140OpenAlexW2901954812MaRDI QIDQ5113675FDOQ5113675

Authors Aude le Gluher, Pierre-Jean Spaenlehauer

Publication date 15 June 2020

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

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

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational aspects of algebraic curves (14Q05)

Abstract: We propose a probabilistic variant of Brill-Noether's algorithm for computing a basis of the Riemann-Roch space $L(D)$ associated to a divisor $D$ on a projective nodal plane curve $mathcalC$ over a sufficiently large perfect field $k$. Our main result shows that this algorithm requires at most $O(max(mathrmdeg(mathcalC{)}^{2omega},mathrmdeg(D_{+}{)}^{o}mega))$ arithmetic operations in $k$, where $omega$ is a feasible exponent for matrix multiplication and $D_{+}$ is the smallest effective divisor such that $D_{+}geqD$. This improves the best known upper bounds on the complexity of computing Riemann-Roch spaces. Our algorithm may fail, but we show that provided that a few mild assumptions are satisfied, the failure probability is bounded by $O(max(mathrmdeg(mathcalC{)}^4,mathrmdeg(D_{+}{)}^2)/lvertmathcalEvert)$, where $mathcalE$ is a finite subset of $k$ in which we pick elements uniformly at random. We provide a freely available C++/NTL implementation of the proposed algorithm and we present experimental data. In particular, our implementation enjoys a speedup larger than 6 on many examples (and larger than 200 on some instances over large finite fields) compared to the reference implementation in the Magma computer algebra system. As a by-product, our algorithm also yields a method for computing the group law on the Jacobian of a smooth plane curve of genus $g$ within $O(g^{o}mega)$ operations in $k$, which equals the best known complexity for this problem.

Recommendations

• Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve
• scientific article; zbMATH DE number 1504672
• Computing Riemann-Roch spaces in algebraic function fields and related topics.
• Computing Riemann-Roch spaces via Puiseux expansions
• Publication:4509883

Cites work

• scientific article; zbMATH DE number 3664349 (Why is no real title available?)
• scientific article; zbMATH DE number 1057752 (Why is no real title available?)
• scientific article; zbMATH DE number 194422 (Why is no real title available?)
• scientific article; zbMATH DE number 799781 (Why is no real title available?)
• scientific article; zbMATH DE number 6665535 (Why is no real title available?)
• A Gröbner free alternative for polynomial system solving
• Algorithme de Brill-Noether et codes de Goppa
• An elementary approach to subresultants theory.
• Asymptotically fast group operations on Jacobians of general curves
• Computing Riemann-Roch spaces in algebraic function fields and related topics.
• Effective construction of algebraic geometry codes
• Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve
• Fast computation of generic bivariate resultants
• Fast computation of the roots of polynomials over the ring of power series
• Faster algorithms for the characteristic polynomial
• Geometry of algebraic curves. Volume II. With a contribution by Joseph Daniel Harris
• Le formalisme du résultant. (The formalism of resultant)
• Modern computer algebra
• On computing the resultant of generic bivariate polynomials
• On fast multiplication of polynomials over arbitrary algebras
• Powers of tensors and fast matrix multiplication
• The Magma algebra system. I: The user language
• Triangular Factorization and Inversion by Fast Matrix Multiplication

Cited in

(13)

• Fast Algorithms for Pseudoarboricity
• Projective toric codes
• Efficient algorithms for the Riemann-Roch problem and for addition in the Jacobian of a curve
• Upper bounds for some Brill–Noether loci over a finite field
• Computing Riemann-Roch spaces in algebraic function fields and related topics.
• On the generating matrices of Goppa codes over hyperelliptic curves
• Computing Riemann-Roch spaces via Puiseux expansions
• Mumford representation and Riemann-Roch space of a divisor on a hyperelliptic curve
• Asymptotically-good arithmetic secret sharing over \(\mathbb{Z}/p^{\ell }\mathbb{Z}\) with strong multiplication and its applications to efficient MPC
• Quasi-equivalence of heights in algebraic function fields of one variable
• A fast randomized algorithm for computing an approximate null space
• Efficient computation of Riemann-Roch spaces for plane curves with ordinary singularities
• Linear algebra algorithms for divisors on an algebraic curve

Describes a project that uses

Uses Software

• Magma

This page was built for publication: A fast randomized geometric algorithm for computing Riemann-Roch spaces

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