Implementation of prime decomposition of polynomial ideals over small finite fields
Implementation of prime decomposition of polynomial ideals over small finite fields
复制标题
DOI：
10.1145/990353.990366
复制
发表时间：
2003-09
期刊：
影响因子：
--
通讯作者：
M. Noro;K. Yokoyama
中科院分区：
文献类型：
--
作者：
M. Noro;K. Yokoyama
提出并实现了小有限域上多项式理想素数分解的算法。这里的“小”意味着有限域的阶小到足以容纳单个机器字。特别是，我们对阶数太小的情况感兴趣，以至于我们无法应用在特征为0的情况下成功的通常方法。为了克服这个困难，[8]引入了“可分离理想”和“可分离理想闭包”的概念，并且我们在[8]的基础上提出了一种精确的算法，用于小有限域上多项式理想的素数分解。我们的最终目标是开发一种实用的算法，用于有限域上多项式理想的初级分解。为此，我们可以应用[7]的“本地化技术”，它使我们能够从素因数中提取主要成分。这不依赖于系数域的特性。因此，一次分解计算可以有效地简化为素数分解计算。
An algorithm for the prime decomposition of polynomial ideals over small finite fields is proposed and implemented. Here "small" means that the order of a finite field is small enough to fit in a single machine word. In particular, we are interested in cases where the order is so small that we cannot apply usual methods which is suc- cessful in cases of characteristic 0. To overcome this difficulty, [8] introduced the notion of "separable ideals" and "separable closure of ideals", and we propose a precise algorithm for the prime decomposition of polynomial ideals over small finite fields based on [8]. Our final goal is to develop a practical algorithm for the primary decomposition of a polynomial ideal over a finite field. For this purpose we can apply the "localization technique" of [7], which enables us to extract primary components from prime divisors. This does not depend on the characteristic of the coefficient field. Therefore primary decomposition computations can be efficiently reduced to prime decomposition computations.