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

F正规基的次二次时间算法MARK GIESBRE cHT，ARMIN JAMSHIDPEY，和 E'rIcScHOST2020年5月8日抽象。 对任意有限Galois域扩张K/F，若Galois群G = Gal（K/F），则存在一个元素α ∈ K，其轨道G·α构成K的F-基.这样的α称为正规元，G·α是正规基。 当G是有限交换群或亚循环群时，我们给出了一个检验α ∈ K是否正规的概率算法.所有这些都是基于在不正常的情况下进行的故障检测可归结为判定g∈Gg（α）g∈K[G]是否可逆，需要稍微次二次的操作次数。 一旦我们知道证明了α是正态的，我们给出了如何在K/F的工作基和正态基之间进行具有相同渐近代价的转换。关键词正规基;伽罗瓦群;多环群; Meta循环群;快速算法主题分类。12Y05、12F10、11y16、68Q251. 介绍对于有限伽罗瓦域扩张K/F，伽罗瓦群G= Gal（K/F），若元素α∈K的伽罗瓦共轭集G·α={g（α）：g∈G}构成K作为上的向量空间的基，则称元素α是正规的任何有限伽罗瓦扩张的正规元的存在性是经典的，并且在大多数代数文本中提供 了 构 造 性 证 明 （ 参 见 ， 例 如 ， （ Lang2002 ， 第 6.13节））。arXiv：2005.03497v1 [cs.SC] 2020年5月2贾姆希德佩？舍斯特？吉斯布雷希特虽然正规基在有限域中有广泛的公知应用，例如快速取幂（例如， （Gao et al. 2000）），也存在特征零点中的正规元素的应用。例如，在乘法不变量理论中，对于给定的置换格和相关的伽罗瓦扩张，正规基在显式计算乘法不变量时是有用的（Jamshidpey，Lemire Schost2018）。有许多算法可用于在特征零点和有限域中寻找正规元素。由于它们在有限域中的直接应用，在这种情况下确定正规元的算法是最常见的。 一vonzurGathenGiesbrecht（1990）给出了一个确定有限域Fqn/Fq中正规元的快速随机算法，其中Fqn是具有qn个元素的有限域，其中q为任意素数幂q，n >1，其代价为O（n2+nlogq）在Fq中的操作。一个更快的随机化算法是由Kaltofen&Shoup（1998），成本为O（n1. 82logq）操作。 在比特复杂度模型中，Kedlaya和Umans展示了如何将n的指数减少到1。63，通过利用他们的准线性模 块 化 组 合 的 时 间 算 法 （ Kedlaya Umans2011 ） 。 Lenstra（1991）引入了一种确定性算法来构造一个正规元，它在Fqn/Fq中使用n个O（1）运算。据我们所知，Augot Camion（1994）的算法是最有效的确定性方法，与成本的O（n3+n2logq）的操作在Fq。在特征零中，Schlickewei Stepanov（1993）给出了一个算法，用于寻找Q上数域的正规基，该数域具有基数为n的循环伽罗瓦群，需要在Q中进行n次O（1）运算。Poli（1994）给出了一个算法，用于在阿贝尔扩张K/F中寻找正规基的更一般的情况，这需要在F中进行n个O（1）运算。更一般地，在特征零，对于任何n次伽罗瓦扩张K/F，其伽罗瓦群由aGirstmair（1999）给出了一个算法，该算法需要在F中进行O（n4）次运算来构造K中的正规元。在本文中，我们提出了一个新的随机算法，确定是否一个给定的元素在阿贝尔或亚循环扩张是正常的，与运行时次二次的次数为n正规基3⟨ ⟩∈∈→我扩展名.所有算法的成本都是通过计算F中的算术运算的单位成本来衡量的。与我们的算法的位复杂性相关的问题是具有挑战性的，超出了本文的范围。我们的主要惯例如下。假设1.1。 设K/F是有限Galo扩张，表示为K =F[x]/P（x），对于一个非线性多项式PF[x]为n次，F的特征为零。然后，◦ K的元素写在幂基1，k，. . . ，n−1，其中n：= x mod P;◦ G的元素通过它们对π的作用来表示。在一般情况下，对于g∈Ggiven，通过对fγ：=g（k）∈K，β=0≤inβi <$i∈K，g是F-自同构的事实意味着g（β）等于β（γ），β在γ处的多项式合成（约化模P）。我们的算法结合的技术和想法冯祖尔Gathen Giesbr（1990）和Kaltofe&n Shoup（1998）：α∈K是nmal，如果n如果元素Sα：=g∈Gg（α）g∈K[G]在群代数K[G].然而，写下Sα涉及F中的Θ（n2）个元素，这排除了次二次运行时间。 相反，知道α，算法使用F [ G ]中类似问题的随机化约简，这相当于应用随机投影：对Sα的所有元素，给出一个元素sα ， <$F[G]。为此，我们适应算法（KaltofenShoup1998），这些算法是为有限域的伽罗瓦群开发的。有了sα ， β，我们需要检验它的可逆性。为了做到这一点，我们提出了一个算法在阿贝尔的情况下，它依赖于这样一个事实，即F[G]同构于一个多元多项式环模一个理想（xei−1）1≤i≤m，其中ei对于亚循环群，我们利用了sα乘矩阵的块-Hankel结构.关于F[G]中算术运算代价的这些后一问题与G上的傅立叶变换的代价密切相关，值得一提的是，有大量关于快速算法的文献4贾姆希德佩？舍斯特？吉斯布雷希特·∈·∈对于傅立叶变换（在基域C上）。与我们当前的目标相关，目标是（Clausen&Müller200 4）和（Masleneetal. 2018年）和参考文献中的详细信息。在这个阶段，清楚我们如何在我们的上下文中应用这些方法（我们在任意F上工作，不一定代数封闭）。本文从获得改进的渐近复杂性估计的角度出发.由于我们的主要目标是在运行时分析中突出显示指数（以n为单位）一个新的例子是t-O notaton的解：S（n）在O∞（T（n））中，如果它在时间复杂度为O（T（n）log（T（n））c）。本文的第一个主要结果是下面的定理;我们使用一个ω（4/3）的系数来确定在矩形矩阵乘积中的系数（见本节末尾）。第1.2节. 在假设1.1下，若G是阿贝尔的或广义的，则当αK在F中不为O∞（n（3/4）·ω（4/ 3））时，可满足（3/4）ω（4/3）<1.九十九这是一个很好的机会蒙特卡洛类型的随机化一旦知道α是正态的，我们还讨论了幂基1，n，. . .，n−1与它的正规基G α。再次受到Kaltofen Shoup（1998）以前工作的启发，我们得到以下结果。第1.3节.在Assumption1.1下，如果G是阿贝尔的或亚循环的，并且已知αK是正规的，我们可以执行在幂基1，k，. . . ， n−1，它的n个最小值为G·αusingO（n （3/4 ） ·ω（4/3））o perans. 这些算法是随机的蒙特卡罗类型。在这两个定理中，运行时间几乎是次二次的，指数为1。99是通过快速矩阵乘法算法获得的，该算法对于合理的n很可能是不切实际的。然而，这些结果特别表明，我们可以在不写下正规基本身的情况下进行基转换（这需要F中的Θ（n2）个元素）。REMARK 1.4.上述两种算法都是随机化的Monte Carlo类型。在我们的模型中，这意味着他们被允许绘制正规基5⌈⌉≤∈对于K的一个规定子集和一个控制参数λ，随机元素产生正确答案的概率大于1 −λ（见注2.8）。本文第二在第3节中，给出了一个次二次时间算法，用于将我们的主要问题随机化约化为F[G]中的可逆性检验;该算法适用于任何有限多循环群，特别是阿贝尔群和亚循环群。在第4节中，我们证明了对于阿贝尔群，在F[G]中检验可逆性和进行除法的问题可以在拟线性时间内解决;对于亚循环群，我们给出了一个基于结构线性代数算法的次二次时间算法（这将完成定理1.2的证明）。最后，第5节证明了定理1.3。我们的算法广泛使用已知的多项式和矩阵算术算法;特别是，我们重复使用的事实，即多项式的次数n在F[x]，对任何领域对于字符串，可以在O/n（n）操作中执行F（Schéonhage&S trass e n197 1）。ASARESULT，ARRHMETIOPERA-K中的tios（+，x，n）可以通过使用Oios（n）操作来实现F（von zur Gathen Gerhard2013）.我们还假设，在F中生成一个随机元素需要恒定的时间。对于矩阵算术，我们将依赖于Lotti Romani（1983）提出的矩形矩阵乘法的一些非平凡结果。对于kR，我们用ω（k）表示一个常数，在任何环上，大小为（n，n）乘（n，nk）的矩阵可以是多个的，在O（nω（k））环运算中使用（所以ω（1）是方阵乘法的通常指数，我们简单地写为ω）。的对于大多数矩形格式，迄今为止已知的最尖锐的值是Le Gall&Urrutia（2018）;对于k = 1，最知名的值是ω 2。373Le Gall（2014）。在一个域上，进一步的矩阵运算（如求逆）也可以在O（nω）基域运算中完成。本文的部分结果（交换群的定理1.2）已经发表在会议论文（Giesbrecht et al. 2019年）。6贾姆希德佩？舍斯特？吉斯布雷希特···∈ {}/∈.∈...2. 预赛有限伽罗瓦扩张的正规元存在性的一个众所周知的证明，例如Lang（2002，Theorem 6.13.1），提出了一个寻找这样一个元 素 的 随 机 算 法 设 K/F 是 有 限 伽 罗 瓦 扩 张 ， 伽 罗 瓦 群 G={g1，. . .，g n}。如果α∈K是正规元，则卢恩（2.1）j=1cjgj（α）= 0，cj∈F意味着c1==cn= 0。 对于每个i1，. . . ，n，将g i应用于方程（2.1），（二、二）卢恩j=1c j g i g j（α）= 0.利用式（2.1）和式（2.2），可以形成线性系统MC=0，其中c= [c1· · ·cn]T，其中，对于α∈K，g1g1（α）g1g2（α）···g1gn（α）（2.3）M=<$g2g1（α）g2g2（α）···g2gn（α）<$∈M（K）。巴恩gn g1（α） g n g2（α） ··· g n g n（α）经典的证明接着证明存在αK，det（M）= 0。这种方法可以作为一个程序的基础来测试如果给定αK是正规的，则通过计算矩阵M的所有元素并使用线性代数计算其行列式;使用快速矩阵运算，这需要在K中进行O（n ω）次运算，在F中进行O<$（nω+1）次运算。这是一个在n中很常见的问题;本文的主要贡献是展示如何加快这一点验证在开始讨论之前，我们简单地评论一下α是正规元素的概率：如果我们写α=a0+n−1· · ·+an−1<$，M的行列式是a（不恒为零）n次齐次多项式在（a0，. . .，a n−1）。 如果人工正规基7⊂−⟨ − ⟩⇒∈在有限集合X F中均匀随机选择，Lipton-DeMillo-Schwartz-Zippel引理意味着αben或mal是tl e的概率是t1−n/|X|.如果G是由一个线性方程g表示的环，其中hg1=id且gi+1=ggiforalli，vonzurGathenGiesbrecht（1990m）avoidcomp uting通过计算Sα的GCD得到行列式：=ni=1 gi（α）xi−1，Xn1. 实际上，这相当于测试Sα是否可逆在环K[G]中，它与K[x]/xn同构1.一、这是一个普遍的事实：对任意G，上述矩阵M是左乘轨道和卢恩Sα：=i=1gi（α）gi∈K[G]，在这里，我们通过g1，. . .，g n和列的倒数g−1，. . . ，g−1. 在符号方面，对于任何域L（通常，我们将1N取L=F或L=K），β在L[G]中，我们将使用上面所示的两个基，将左乘矩阵ML（β）写为L[G]中的β换句话说，式（2.3）的矩阵M是MK（Sα）。前面的讨论表明，α是正规的等价于Sα是K[G]中的单位。这种观点可能会避免K上大小为n的线性代数，但写Sα本身仍然涉及F中的Θ（n2）个元素。下面的引理是我们算法中的主要新成分：它给出了一个随机化的约简，以检验Sα在F[G]中的一个合适的投影是否是一个单位。2.4. 对α ∈ K，MK（S α）可逆当且仅当<$（MK（Sα））：=[<$（gigj（α））]ij∈Mn（F）对于一般的F-线性投影K：K → F是可逆的。P屋顶。（ ）对于固定的αK，MK（S α）的任何项可以写为：（二、五）乌斯季-1一个Ijk的，k=0对于k：k F，则（MK（Sα））中的相应条目可以被写为n−1a，与 =（k）。 用以下内容代替这些内容k=0IJK K K K8贾姆希德佩？舍斯特？吉斯布雷希特∈⇐不确定LkF [L1，. . . ，L n]。 在K [L1，. . . ，Ln]，则有P（1，n，. . . ，n−1）= det（MK（Sα）），根据假设，它是非零的。因此，P不恒为零，结论如下。（）设 MK（Sα）不可逆。在Jamshidpey等人的证明之后（2018，引理4），我们首先证明了在MK（Sα）的核中存在非零u∈FnG的元素按元素方向作用于MK（Sα）的行上，操作将排列矩阵中的行。设G→Sn是群同态使得g（ Mi）=MK（g）（i），其中Mi是MK（Sα）的第i由于MK（Sα）是奇异的，存在一个非零的v∈Kn使得MK（Sα）v= 0;我们选择具有最小数量的非零条目。设i∈ {1，. . .，n}，使得v为0。定义u = 1/v iv. 那么，MK（S α）u = 0，这意味着对于j∈{1，. . .，n}。对于g∈G，我们有g（Mju）= M（g ）（j ）g（u）= 0。由于这对任何j都成立，我们得出结论MK（Sα）g（u）= 0，因此g（u）−u在MK（S α）的核中。另一方面，由于u的第i项是1，g（u）−u的第i项是0。因此，关于v的极小性假设表明g（u）− u = 0，等价地g（u）=u，因此u∈Fn。现在我们证明了，对于所有的选择，- 是的 通过公式（2.5），我们可以写乌斯季-1MK（Sα）= j=0M（j）<$j，M（j）∈ Mn（F）.因为u在F中有元素，所以MK（Sα）u= 0产生M（j）u= 0，j∈ {1，. . . ，n}。因此，我们认为，乌斯季-1j=0M（j）=0对于F中的任意n_Q我们的算法可以概括如下：给定K中的α，选择一个随机数：K→F，令卢恩(2.6)sα，ε：=正规基9i=1<$（gi（α））gi∈F[G].10贾姆希德佩？舍斯特？吉斯布雷希特→--⟨ ⟩→注意，MK（Sα））等于MF（sα，M α），即F[G]中sα，的乘法矩阵，其中，如上所述，我们通过g1，. . . ，g n，列数为g−1，. . . ，g−1. 那么，前面的引理1N可以改写如下：2.7. 对 于 一般的F -线性投影<$K →F，α是正规的当且仅当s α，<$在F [G]中可逆.因此，一旦sα，n是已知的，我们就剩下检验它是否是F[G]中的单位。在接下来的两节中，我们分别讨论了计算sα，ε和检验其在F[G]中的可逆性的问题REMARK 2.8. 如果α不正规，则S α不是单位。在这种情况下，引理2.4的证明确定了s α，ε不是任何ε的单位，所以我们的算法在这种情况下总是返回正确的答案。如 果 α 是 正 规 的 ， 则在引理2.4的证明中的 多 项 式 P 是 在（L1，. . . ，L n）。因此，如果我们在任何固定的有限子集X ∈ F中随机一致地选择λ的系数，则通过Lipton-DeMillo-Schwartz-Zippel引理，我们可以用hpro bbbi i tleast1−n/|X|.3. 计算轨道和在这一节中，我们提出了一个算法来计算s α，当G = g1，. . .，gn是多环的（我们给出了这类群的定义，并回忆了3.2小节中关于这类群的一些著名结果）。为了激发我们的算法，我们从循环群的简单情况我们将看到，它们严格遵循Kaltofen Shoup（1998）在有限域上使用的思想假设G=g，因此给定K中的α和K：K F，我们的目标是计算(3.1)（g i（α）），对于0 ≤i≤n− 1。Kaltofen& Shoup（1998）称之为自同构投影问题，并给出了在次二次时间内求解该问题的算法，其中g是q次幂Frobenius FqnFqn。他们算法中的关键思想是使用婴儿步/巨人步技术：对于一个合适的参数t，公式3.1中的值可以重写为：（？？g tj）（g i（α）），当0 ≤ j z。 为了应用引理，我们必须检查这些指数s1，. . . 因此，时间复杂度为O（n）。事实上，这款产品最多.√nΣ√√e1··· ez−1+1个e1··· ez−1n+ e1· · ·e z−1≤ 2 n。此时，该算法是一个简单的算法，其代价为O∞ （n （ 3/4 ） ·ω（4/3））。步骤2. 计算Gz=gsz，对于sz如上。其代价是O（log（n））的模块组合，与前一步的代价相比可以忽略不计步骤3. 使用引理3.5，i1 = 0，对于所有i1，. . .，i r，以计算Lj，...，J =（gjr···gjz+1Gjz）=（gjr···gjz+1gszjz），1z≤18贾姆希德佩？舍斯特？吉斯布雷希特1z−1√1RRz+1zz−11对于所有的指数0≤jz∈z/sz∈和0≤jm ∈m，对于m> z。这相当于使用索引为s′=· · ·=s′= 1的引理，当m > z时，s′= εez/szε，s′=em。 同样，我们必须核实兹海姆时间复杂度O（n）我确已s′· · · s′、、、=ez e···e.Σ≤ez+1eS···e1RSZz+1rzz+1r≤ez···er+eS· · ·e.z+1rz通过定义，w具有vesz≥n/（e1···ez−1），soez···er/sz≤e1···er/n=n。当e=1· ··ez≥n时，则e= 1 ···e z≥ n。第二项也至多为n，因此乘积s′· · ·s′至多为2n. 因此，引理3.5适用，并且计算所有的jz使用O∈（n（3/4）·ω（4/3））算子在F中的推广.步骤4. 将矩阵的行乘以所有L jr，.，jz乘以矩阵，矩阵的列是所有G iz，...，i1.这将产生值<$（gjr· · ·gjz+1gszjz+izgiz−1· · ·gi1（α）），索引如下：• 0≤ i m

下载后可阅读完整内容，剩余1页未读，立即下载