Skip to Main content Skip to Navigation
Journal articles

A Fast Randomized Geometric Algorithm for Computing Riemann-Roch Spaces

Aude Le Gluher 1 Pierre-Jean Spaenlehauer 1
1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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 $\mathcal C$ over a sufficiently large perfect field $k$. Our main result shows that this algorithm requires at most $O(\max(\deg(\mathcal 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(\mathcal 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.
Complete list of metadatas

https://hal.inria.fr/hal-01930573
Contributor : Pierre-Jean Spaenlehauer <>
Submitted on : Thursday, November 22, 2018 - 10:07:41 AM
Last modification on : Friday, January 17, 2020 - 10:16:07 AM

Links full text

Identifiers

Collections

Citation

Aude Le Gluher, Pierre-Jean Spaenlehauer. A Fast Randomized Geometric Algorithm for Computing Riemann-Roch Spaces. Mathematics of Computation, American Mathematical Society, In press, ⟨10.1090/mcom/3517⟩. ⟨hal-01930573⟩

Share

Metrics

Record views

146