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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)

• Title not available (Why is that?)
• Title not available (Why is that?)
• A prolongation-projection algorithm for computing the finite real variety of an ideal
• Intrinsic factorization of ideals in Dedekind domains
• 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)