Fast Integral Bases Computation

Poteaux, Adrien; Weimann, Martin

Type de document :

Pré-publication ou Document de travail

Titre :

Fast Integral Bases Computation

Auteur(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]

Mot(s)-clé(s) en anglais :

Fields
Fractional ideals
Integral bases
OM algorithm.

Discipline(s) HAL :

Mathématiques [math]

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Collections :

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

Source :

Harvested from HAL

Fichiers

document
Accès libre
Accéder au document

integral.pdf
Accès libre
Accéder au document

Fast Integral Bases Computation BibTeX CSV Excel RIS

Fichiers

Fast Integral Bases Computation

BibTeX

CSV

Excel

RIS