An algorithm for computing the factor ring of an ideal in Dedekind domain with finite rank

DOI10.1007/S11425-016-9060-2zbMATH Open1414.11167OpenAlexW2963690585MaRDI QIDQ1650656FDOQ1650656

Authors Dandan Huang, Yingpu Deng

Publication date 5 July 2018

Published in Science China. Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Dedekind domainsbasis representationdeterministic polynomial-time testHermite and Smith normal forms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algebraic number theory computations (11Y40)

Abstract: We give an algorithm for computing the factor ring of a given ideal in a Dedekind domain with finite rank, which runs in deterministic and polynomial-time. We provide two applications of the algorithm: judging whether a given ideal is prime or prime power. The main algorithm is based on basis representation of finite rings which is computed via Hermite and Smith normal forms.

Recommendations

• Intrinsic factorization of ideals in Dedekind domains
• Hermite and Smith normal form algorithms over Dedekind domains
• A new computational approach to ideal theory in number fields
• scientific article; zbMATH DE number 1273653
• scientific article; zbMATH DE number 2186836

Cites work

• scientific article; zbMATH DE number 843465 (Why is no real title available?)
• scientific article; zbMATH DE number 3279238 (Why is no real title available?)
• Advanced Topics in Computional Number Theory
• Algorithms in Algebraic Number Theory
• Asymptotically Fast Triangularization of Matrices over Rings
• Complexity of ring morphism problems
• Fast construction of irreducible polynomials over finite fields
• Fast multiplication of large numbers
• PRIMES is in P
• Polynomial-time locality tests for finite rings
• The Complexity of Black-Box Ring Problems
• Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix

Cited in

(5)

• Intrinsic factorization of ideals in Dedekind domains
• scientific article; zbMATH DE number 3870585 (Why is no real title available?)
• scientific article; zbMATH DE number 1567893 (Why is no real title available?)
• A prolongation-projection algorithm for computing the finite real variety of an ideal
• Power detection over number fields

This page was built for publication: An algorithm for computing the factor ring of an ideal in Dedekind domain with finite rank

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