Fast computation of integral bases
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909209028722688 |
|---|---|
| author | Poteaux, Adrien Weimann, Martin |
| author_facet | Poteaux, Adrien Weimann, Martin |
| contents | 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 output when the residual characteristic is zero or big enough. Analogous results are 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 algorithm of Stainsby, together with optimal truncation bounds and a precise complexity analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_13577 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast computation of integral bases Poteaux, Adrien Weimann, Martin Number Theory Algebraic Geometry 11Y40, 68W30, 12F05 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 output when the residual characteristic is zero or big enough. Analogous results are 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 algorithm of Stainsby, together with optimal truncation bounds and a precise complexity analysis. |
| title | Fast computation of integral bases |
| topic | Number Theory Algebraic Geometry 11Y40, 68W30, 12F05 |
| url | https://arxiv.org/abs/2405.13577 |