A Fast Randomized Geometric Algorithm for Computing Riemann-Roch Spaces
share
We propose a probabilistic Las Vegas 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 plane curve C over a sufficiently large perfect field k. Our main result shows that this algorithm requires at most O((deg( C)^2ω, deg(D_+)^ω)) arithmetic operations in k, where ω is a feasible exponent for matrix multiplication and D_+ is the smallest effective divisor such that D_+≥ 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((deg( C)^4, deg(D_+)^2)/ E), where 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 speed-up larger than 9 on several examples 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^ω) operations in k, which slightly improves in this context the best known complexity O(g^ω+ε) of Khuri-Makdisi's algorithm.
READ FULL TEXT