Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A fast randomized geometric algorithm for computing Riemann-Roch spaces

Authors: Aude Le Gluher and Pierre-Jean Spaenlehauer
Journal: Math. Comp. 89 (2020), 2399-2433
MSC (2010): Primary 14Q05, 68W30
Published electronically: February 18, 2020
MathSciNet review: 4109572
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

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 $ \mathbb{C}$ over a sufficiently large perfect field $ k$. Our main result shows that this algorithm requires at most $ O(\max (\deg (\mathbb{C})^{2\omega }, \deg (D_+)^\omega ))$ arithmetic operations in $ k$, where $ \omega $ is a feasible exponent for matrix multiplication and $ D_+$ is the smallest effective divisor such that $ D_+\geq D$. 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 (\deg (\mathbb{C})^4, \deg (D_+)^2)/\lvert \mathcal E\rvert )$, where $ \mathcal E$ 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^\omega )$ operations in $ k$, which equals the best known complexity for this problem.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 14Q05, 68W30

Retrieve articles in all journals with MSC (2010): 14Q05, 68W30

Additional Information

Aude Le Gluher
Affiliation: CARAMBA project, Université de Lorraine; and Inria Nancy – Grand Est; and CNRS, UMR 7503, LORIA, Nancy, France

Pierre-Jean Spaenlehauer
Affiliation: CARAMBA project, INRIA Nancy – Grand Est; and Université de Lorraine; and CNRS, UMR 7503, LORIA, Nancy, France

Received by editor(s): May 16, 2019
Received by editor(s) in revised form: October 8, 2019, and December 6, 2019
Published electronically: February 18, 2020
Article copyright: © Copyright 2020 American Mathematical Society