Fast Integral Bases Computation

Poteaux, Adrien; Weimann, Martin

Document type :

Pré-publication ou Document de travail

Title :

Fast Integral Bases Computation

Author(s) :

Poteaux, Adrien [Auteur]

Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Weimann, Martin [Auteur]
Laboratoire de Mathématiques Nicolas Oresme [LMNO]

English keyword(s) :

Fields
Fractional ideals
Integral bases
OM algorithm.

HAL domain(s) :

Mathématiques [math]

English abstract : [en]

We obtain new complexity bounds for computing a triangular integral basis of a number field or a function field. We reach for function fields a softly linear cost with respect to the size of the outputwhen the residual ...
Show more >We obtain new complexity bounds for computing a triangular integral basis of a number field or a function field. We reach for function fields a softly linear cost with respect to the size of the outputwhen the residual characteristic is zero or big enough. Analogous resultsare obtained for integral basis of fractional ideals, key ingredients towards fast computation of Riemann-Roch spaces. The proof is based on the recent fast OM algorithm of the authors and on the MaxMin algorithmof Stainsby, together with optimal truncation bounds and a precise complexity analysis.Show less >

Language :

Anglais

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Files

document
Open access
Access the document

integral.pdf
Open access
Access the document

Fast Integral Bases Computation BibTeX CSV Excel RIS

Files

Fast Integral Bases Computation

BibTeX

CSV

Excel

RIS