有限域正规基的次二次时间算法研究

"这篇论文探讨了在有限域中构建正规基的次二次时间算法，重点关注有限伽罗瓦域扩张的情况。正规基在伽罗瓦群理论、多环群和亚循环群的研究中扮演着重要角色，同时在快速计算、如快速幂运算等领域有广泛应用。文章提出了一种概率算法，用于检验元素是否属于正规元，特别是针对有限交换群和亚循环群的情况。算法的核心是通过判断特定伽罗瓦群元素的性质来确定正规性，这涉及到次二次操作次数的计算。一旦找到正规元，文章还提供了在工作基和正规基之间转换的方法，其代价与找正规元的过程具有相同的渐近代价。此外，文中引用了先前的工作，如von zur Gathen和Giesbrecht的算法以及Kaltofen和Shoup的算法，这些算法在确定有限域中的正规元时已经实现了较低的时间复杂度。Kedlaya和Umans进一步改进了这一复杂度，使得在比特复杂度模型下，指数可以降低到1.6。" 这篇论文的主要知识点包括： 1. 正规基：在有限伽罗瓦域扩张中，如果一个元素的伽罗瓦共轭集构成了域的基，那么这个元素被称为正规元，其集合称为正规基。正规基的存在性和构造方法在代数学中有经典证明。 2. 伽罗瓦群：Galois群是域扩张的自同构群，它揭示了域扩张的结构和代数性质。在有限域扩张中，Galois群通常是有限的。 3. 概率算法：文章提出了一个概率算法来检验元素是否为正规元，尤其适用于有限交换群和亚循环群。这种方法基于检测群元素的某些属性是否满足可逆条件。 4. 次二次时间复杂度：算法的核心操作次数是次二次的，这意味着其复杂度比线性或二次时间复杂度更低，提高了计算效率。 5. 转换算法：找到正规元后，论文还提供了一个算法，可以在保持相同渐近代价的前提下，将工作基转换为正规基，这对于实际应用如快速幂运算至关重要。 6. 历史算法比较：文中提到了其他研究者的工作，如von zur Gathen和Giesbrecht的随机算法（O(n^2+nlogq)操作复杂度）和Kaltofen和Shoup的更快速算法（O(n^{1.82}logq)操作复杂度），以及Kedlaya和Umans的进一步优化，使得指数降低到1.6。 7. 应用领域：正规基在有限域的快速幂运算、乘法不变量理论等领域有广泛应用，特别是在计算乘法不变量时，正规基能够帮助显式地进行计算。 8. 主题分类：论文涉及的数学领域包括伽罗瓦理论、多环群、亚循环群和算法复杂度理论，同时也与计算机科学中的算法设计和分析相关，因此被归类在12Y05、12F10、11Y16和68Q25这些主题下。