Algorithms for Commutative Algebras Over the Rational Numbers
Algorithms for Commutative Algebras Over the Rational Numbers
复制标题
有理数上的交换代数算法
DOI：
--
复制
发表时间：
2015
影响因子：
3
通讯作者：
A. Silverberg
中科院分区：
文献类型：
--
作者：
H. Lenstra;A. Silverberg
本文考虑的代数是交换环，其加法群是有理数域上的有限维向量空间。我们提出了确定性的多项式时间算法，给定这样的代数，确定其零根，其所有的素理想，以及相应的本地化和剩余类字段，其最大的可分离子代数，其原始幂等元。我们还解决了代数乘法群中的离散对数问题。虽然确定性的多项式时间算法是已知的早期，我们的方法是从以前的不同。我们的工具之一是本原元算法;它决定代数是否有一个本原元，如果有，就找到一个，所有这些都在多项式时间内完成。一种新奇是使用导数来代替亨塞尔-牛顿迭代。它导致了一个明确的公式提升幂等元对幂零是有效的任何交换环。
The algebras considered in this paper are commutative rings of which the additive group is a finite-dimensional vector space over the field of rational numbers. We present deterministic polynomial-time algorithms that, given such an algebra, determine its nilradical, all of its prime ideals, as well as the corresponding localizations and residue class fields, its largest separable subalgebra, and its primitive idempotents. We also solve the discrete logarithm problem in the multiplicative group of the algebra. While deterministic polynomial-time algorithms were known earlier, our approach is different from previous ones. One of our tools is a primitive element algorithm; it decides whether the algebra has a primitive element and, if so, finds one, all in polynomial time. A methodological novelty is the use of derivations to replace a Hensel–Newton iteration. It leads to an explicit formula for lifting idempotents against nilpotents that is valid in any commutative ring.