A fast randomized geometric algorithm for computing Riemann-Roch spaces

Source abstract

We propose a probabilistic variant of Brill-Noether’s algorithm for computing a basis of the Riemann-Roch space L ( D ) L(D) associated to a divisor D D on a projective nodal plane curve C \mathbb {C} over a sufficiently large perfect field k k . Our main result shows that this algorithm requires at most O ( max ( deg ⁡ ( C ) 2 ω , deg ⁡ ( D + ) ω ) ) O(\max (\deg (\mathbb {C})^{2\omega }, \deg (D_+)^\omega )) arithmetic operations in k k , where ω \omega is a feasible exponent for matrix multiplication and D + D_+ is the smallest effective divisor such that D + ≥ D 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 ⁡ ( C ) 4 , deg ⁡ ( D + ) 2 ) / | E | ) O(\max (\deg (\mathbb {C})^4, \deg (D_+)^2)/\lvert \mathcal E\rvert ) , where E \mathcal E is a finite subset of k 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 g within O ( g ω ) O(g^\omega ) operations in k k , which equals the best known complexity for this problem.