Skip to Main content Skip to Navigation
Journal articles

Computing Riemann-Roch spaces via Puiseux expansions

Abstract : Computing large Riemann-Roch spaces for plane projective curves still constitutes a major algorithmic and practical challenge. Seminal applications concern the construction of arbitrarily large algebraic geometry error correcting codes over alphabets with bounded cardinality. Nowadays such codes are increasingly involved in new areas of computer science such as cryptographic protocols and "interactive oracle proofs". In this paper, we design a new probabilistic algorithm of Las Vegas type for computing Riemann-Roch spaces of smooth divisors, in characteristic zero, and with expected complexity exponent 2.373 (a feasible exponent for linear algebra) in terms of the input size.
Complete list of metadata

https://hal.inria.fr/hal-03281757
Contributor : Elena Berardini Connect in order to contact the contributor
Submitted on : Wednesday, June 22, 2022 - 4:52:08 PM
Last modification on : Tuesday, June 28, 2022 - 10:30:06 AM

File

rrgeneral (1).pdf
Files produced by the author(s)

Identifiers

Citation

Simon Abelard, Elena Berardini, Alain Couvreur, Grégoire Lecerf. Computing Riemann-Roch spaces via Puiseux expansions. Journal of Complexity, Elsevier, 2022, ⟨10.1016/j.jco.2022.101666⟩. ⟨hal-03281757v2⟩

Share

Metrics

Record views

195

Files downloads

260