1. Computing Riemann-Roch spaces via Puiseux expansions
- Author
-
Simon Abelard, Elena Berardini, Alain Couvreur, Grégoire Lecerf, Thales SIX GTS France, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Geometry, arithmetic, algorithms, codes and encryption (GRACE), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), This paper is part of a project of École polytechnique, that has received funding from the French 'Agence de l'innovation de défense'. Simon Abelard was partially funded by this grant, when he was hosted at École polytechnique, Institut Polytechnique de Paris (91120 Palaiseau, France), from October 2019 to the end of December 2020., École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), and This paper is part of a project of École polytechnique, that has received funding from the French 'Agence de l'innovation de défense'. Simon Abelard was partially funded by this grant, when he was hosted at École polytechnique, Institut Polytechnique de Paris (91120 Palaiseau, France), from October 2019 to the end of December 2020. Elena Berardini has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 899987.
- Subjects
Statistics and Probability ,[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] ,Numerical Analysis ,Control and Optimization ,Algebra and Number Theory ,Applied Mathematics ,General Mathematics ,Algebraic curves ,Complexity ,Riemann-Roch spaces ,ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION ,[MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG] ,Puiseux expansions ,Algorithms - Abstract
International audience; 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.
- Published
- 2021