有限域扩张中的正规基与次二次算法

"这篇论文主要探讨了正规基及其在次二次时间算法中的应用，特别是针对有限Galois域扩张的情况。研究重点在于如何检测和利用正规元，以及在不同基之间的转换。" 正规基和Galois群是域扩张中的核心概念。在数学的数域论中，当一个域K在另一个域F上的Galois扩张，Galois群G是K相对于F的所有自同构的集合。如果存在域K中的一元素α，它的所有Galois共轭（即G作用于α的结果）构成了K作为F向量空间的基，那么α被称为正规元，相应的基称为正规基。正规基的存在性是Galois理论的基本结果，它们在很多代数问题中有着重要作用。 这篇论文特别关注有限交换群和亚循环群的Galois群。对于这些类型的群，作者提出了一个概率算法来检验域K中的元素α是否是正规的。这个检验涉及到判断g(α)g是否属于K[G]的逆元，这是在异常情况下的故障检测问题，可以通过次二次操作次数完成。 一旦找到了正规元，论文接着讨论如何在工作基和正规基之间进行转换，这同样具有次二次的时间复杂度。这对于快速计算和算法设计至关重要，特别是在有限域的快速幂运算中。例如，Gao等人(2000)的工作就展示了正规基在有限域中的应用。 此外，正规基在特征为零的域中也有应用，如在乘法不变量理论中。给定一个置换格和相关Galois扩张，正规基有助于显式计算乘法不变量，这对理解代数结构非常有用。 在寻找正规元的算法方面，文献中已经存在多种方法，尤其是在有限域中。von zur Gathen和Giesbrecht(1990)提出了一种随机算法，成本为O(n^2 + n log q)，而Kaltofen和Shoup(1998)的算法将成本降低到O(n^(1.82) log q)。更进一步，Kedlaya和Umans通过比特复杂度模型将n的指数减少到1.6，显著提升了效率。 这篇论文不仅提供了正规基和Galois群的理论分析，还介绍了相关的快速算法，这些算法在实际计算中具有重要的应用价值，特别是在高效处理域扩张和计算不变量时。