The complexity of computing all subfields of an algebraic number field

DOI10.1016/J.JSC.2018.06.001MaRDI QIDQ1733310zbMATH OpenOpenAlexWikidataFDO

Authors Jonas Szutkoski, Mark van Hoeij

Publication date 21 March 2019

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.01140

zbMATH Keywords

latticepartitionssubfields

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Algebraic number theory computations (11Y40) Symbolic computation and algebraic computation (68W30)

Abstract: For a finite separable field extension K/k, all subfields can be obtained by intersecting so-called principal subfields of K/k. In this work we present a way to quickly compute these intersections. If the number of subfields is high, then this leads to faster run times and an improved complexity.

Recommendations

• scientific article; zbMATH DE number 4200323
• scientific article; zbMATH DE number 4137898
• Algorithmic Number Theory
• Complexity of computation in finite fields
• Publication:3197949
• Polynomial computability of fields of algebraic numbers
• Fields of algebraic numbers computable in polynomial time. II
• Computing subfields of number fields and applications to Galois group computations
• Fields of algebraic numbers computable in polynomial time. I
• scientific article; zbMATH DE number 3983069

Cites work

• A polynomial reduction algorithm
• A relative van Hoeij algorithm over number fields
• Block Systems of a Galois Group
• Computing congruences efficiently
• Factoring polynomials with rational coefficients
• Generating subfields
• scientific article; zbMATH DE number 421665 (Why is no real title available?)
• scientific article; zbMATH DE number 4200323 (Why is no real title available?)
• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• scientific article; zbMATH DE number 3785004 (Why is no real title available?)
• scientific article; zbMATH DE number 691245 (Why is no real title available?)
• scientific article; zbMATH DE number 2151224 (Why is no real title available?)
• scientific article; zbMATH DE number 939802 (Why is no real title available?)
• Isomorphisms of algebraic number fields
• Meet and join within the lattice of set partitions
• Modern computer algebra
• On computing subfields. A detailed description of the algorithm
• Powers of tensors and fast matrix multiplication
• Sharp estimates for triangular sets
• Symmetric Functions, m-Sets, and Galois Groups
• The Magma algebra system. I: The user language

Cited in

(8)

• On computing subfields. A detailed description of the algorithm
• Generating subfields
• Identifying central endomorphisms of an abelian variety via Frobenius endomorphisms
• scientific article; zbMATH DE number 421665 (Why is no real title available?)
• scientific article; zbMATH DE number 4200323 (Why is no real title available?)
• Ring extensions of length two
• Factorization and root-finding for polynomials over division quaternion algebras
• Computing quadratic subfields of number fields

Describes a project that uses

Uses Software

• Magma
• PARI/GP

This page was built for publication: The complexity of computing all subfields of an algebraic number field

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1733310)