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

DOI10.1007/S11425-016-9060-2zbMATH Open1414.11167arXiv1406.3523OpenAlexW2963690585MaRDI 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?)
• Fast multiplication of large numbers
• PRIMES is in P
• 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
• Advanced Topics in Computional Number Theory
• Title not available (Why is that?)
• Asymptotically Fast Triangularization of Matrices over Rings
• Fast construction of irreducible polynomials over finite fields
• Polynomial-time locality tests for finite rings
• Algorithms in Algebraic Number Theory
• Complexity of ring morphism problems
• The Complexity of Black-Box Ring Problems

Cited In (3)

• 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

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)