动机
知道含 个符号的域存在,并没有指明它的算术。具体计算需要选定一个不可约多项式、一种系数表示,以及乘法和除法的算法。反过来,若不加检验就把随机的模多项式当作不可约的,则可能产生零因子,使后续所有译码方程失效。
我们把存在性定理与一个有限的过程联系起来。首先在给定的多项式商中计算。然后用 Frobenius 幂和多项式最大公因式检验该商是否为域。最后,利用已证明的不可约多项式的密度,以规定的成功概率和有界的随机性进行搜索。搜索不成功时报告失败;它绝不会把未经验证的环标为域。
最后一步还区分了不可约模多项式与本原乘法元素。BCH 码需要特定阶的根,这是一个额外条件,而不是表示该域后的自动结果。
定义
取给定的素数 和首一 次多项式 ,其中 。每个剩余类用其系数列表 表示,意为 ,其中 。常数嵌入素域。若模多项式经验证不可约,则商是大小为 的域 。
本章中的多项式除法和最大公因式计算在已知的系数域 上进行。它们并不假设所给的商是域。定义余式
于是 是 的余式。对 也作约化,可使公式对一次模多项式仍然正确。
一个域符号的算术表示使用变量 。消息或循环码字多项式可以使用另一个变量 ,以域元素为系数。把一个符号对 取模,与把一个循环码字对 取模,是不同多项式环中的不同运算。
定理/命题
定理 14.2.1
(已验证的商中的算术与逆元)
剩余类的加法按系数模 进行。乘法则将代表元相乘后再对 取模。由 代表的剩余类是单位,当且仅当 ;Bézout 恒等式 给出其逆元 。特别地,若 不可约,则每个非零剩余类都有这样的逆元。
定理 14.2.2
(有限的不可约性检验)
首一 次多项式 不可约,当且仅当
当 时,素因数列表为空。使用普通的精确多项式与模整数算术,该检验的代价关于 和 是多项式的。
定理 14.2.3
(失败概率与运行时间有界的构造)
给定 和有理数 ,存在一个随机算法,其运行时间关于 、 和 的编码长度是多项式的(特别地,当 时,关于 是多项式的),它以至少 的概率返回一个不可约的 次模多项式,否则报告失败。每个返回的模多项式都经确定性检验验证;随机性只影响发现过程,不影响所声称的域的正确性。
证明思路或证明
算术就是多项式算术再取余
证明
(余式保持环运算)
除以首一多项式 ,在每个剩余类中给出一个次数小于 的代表元。先对这些代表元作加法和乘法再约化,保持环运算,因为 的倍数构成理想。若 ,约化后得 ,这就证明了逆元公式。反之,模 的逆元会给出这样的恒等式,因此不可能存在非常数的公因式。
即使模多项式可约,这些论述仍然有效,只是某些非零剩余类可能没有逆元。例如,若 ,且两个因式的次数都更小且为正,则 的非零剩余类相乘为零。多项式最大公因式的计算会检测出这一障碍,而不是试图除以零因子。
对于已验证的域,普通多项式乘法后接长除法,其代价是素域运算次数的多项式。随着次数下降,扩展 Euclid 算法的代价也是多项式的。以二进制整数为指数的幂运算采用反复平方。这些过程作用于由 个模 的剩余组成的列表,没有浮点舍入。打包的整数标记只是一种存储约定,并不允许用模 的算术代替。
Frobenius 映射区分各种可能的因式次数
证明
(Frobenius 整除性与素数下标的最大公因式)
前面关于存在性的一章证明了:次数为 的首一不可约多项式 整除 ,当且仅当 。它还证明了该多项式无平方因式,因为其导数为负一。
若 是 次不可约多项式,则它整除 ,所以 。它不整除下标 处的任何更小的多项式,所以每个所示的最大公因式都为一。
反之,假设检验通过。第一个条件使 成为无平方因式的多项式 的因式。因此它的不可约因式互不相同,且次数 整除 。若有某个 ,取素数 整除 。则 ,于是该因式会同时整除 和 ,与其最大公因式检验矛盾。因此每个因式的次数都是 ,而 的次数只允许恰有一个这样的因式。这就在不假设所给商已是域的前提下证明了不可约性。
巨大的指数 不必写成多项式次数。迭代 使每个中间代表元的次数都低于 ;每一步使用 次商环乘法。共有 步,随后是多项式最大公因式。整数次数 的素因数可以用试除法求得,其代价关于 是多项式的,而 本来就是显式多项式输入规模的一部分。该域检验不需要对 作因数分解。
证明透视
两个条件如何分工
最后的条件 表示 ;由存在性一章,这把 的每个不可约因式的次数限制为 的因数。最大公因式条件再排除各个真因数,而且只需检查少数几个: 的每个真因数 都整除某个极大真因数 ( 为素数),所以对 的每个素因数做一次最大公因式检验,就涵盖了全部真因数。两步之后,每个不可约因式的次数都是 ,而 只容得下一个; 无平方因式固然方便,但这个计数并不需要它。所有除法都在系数域已知的 中进行,从不用到受检商环中的逆元,所以论证不是循环的。
检验的两半各自都不可缺少。
反例模式
单有最大公因式条件不能认证域
在 上取 ,次数为素数 。 的素因数只有它本身,所以检验的最大公因式部分只要求 ,即 在 中没有根。确实 、。然而 是可约的。最后的条件能发现这一点: 整除 ,而它整除 仅当 ,所以 。反方向上,例题中的四次式 通过最后的条件,却不通过一个最大公因式检验。正如定理所述,只有两个条件合起来才刻画不可约性。
不可约多项式足够多,短搜索即可
证明
(不可约多项式的计数与固定的候选预算)
令 为 次首一不可约多项式的个数。此前的计数恒等式给出 。对 ,真因数的贡献为 。对 ,真因数的几何级数上界小于 。因此对每个 ,都有 ;而当 时每个首一一次多项式都不可约,同样的下界成立。
因此,均匀随机选取的首一 次多项式通过检验的概率至少为 。取正整数 使 ,并尝试 个独立候选。在理想的系数均匀实验中,所有候选都可约的概率至多为
对每个候选作确定性检验,返回第一个通过者。这一理想分析已经给出固定的候选预算;剩下的问题是如何用有界数量的公平比特抽取其系数。
明确核算系数抽样
证明
(有上限的系数抽样与耦合)
要在 中抽取一个系数,抽取 个公平比特,若所得整数小于 则接受。一次尝试成功的概率为 ,且被接受的整数在 种选择中是均匀的。每次系数调用至多尝试 次,其中 。这类调用至多有 次,所以某次达到上限而失败的概率至多为 。
为严格起见,把有上限的算法与使用相同新鲜尝试比特的理想无上限系数抽取作比较。在出现上限失败之前,它们产生相同的候选。并集界控制了第一次分歧,而无需以所有调用均成功为条件来讨论整个搜索。合并两个失败事件,得到至多 。所有计数器和比特预算都在执行前就有界,且不可约性检验是多项式的。合适的 通过对有理输入作二的幂次整数比较而算出,因此不需要隐藏的数值舍入。
该算法以所述概率和资源界认证一个模多项式。它并不选出各实现共同使用的标准模多项式;所选多项式和基仍须作为约定表示的一部分被传达或固定。
概念视角代数
两个模多项式,同一个域的不同坐标
不同的 次不可约模多项式给出同构的域,而同构由一个根给出。若 与 都是 次不可约多项式, 是 在 中的根,则 定义一个从 出发的环同态;由于源是域,它是单射,再由计数知它是双射。对 上的 与 ,记 ,由 得 ,所以 是 的根。
单独检验乘法阶
假设域已验证,并且给出了 的因数分解。非零元素 生成其乘法群,当且仅当
证明
(阶整除 )
事实上,它的阶整除 。若阶是真因数,则整除商的某个素数会使所示的某个幂等于一。反之,阶为 的元素通过每个检验。对于 ,素数列表为空,唯一的非零元素生成平凡群。
在给定该整数分解的前提下,阶的检验是高效的;这并不是说对每个 作因数分解都高效。若已知本原元 且 ,则由幂的阶公式, 的阶恰为 。这解释了在 BCH 构造中得到单位根假设的一条标准途径,同时使其前提条件清晰可见。
例题详解
例题 14.2.4
(八符号字母表中的显式逆元)
在 上, 没有根,因此不可约。记 。两个一次项和两个常数项抵消后,乘法给出 。对于除法,注意如下精确的 Bézout 恒等式
因此 。在基 下,向量 与 相乘得 。若把它们的打包整数标记模八相乘,则是在有零因子的环中进行的另一种计算。
例题 14.2.5
(三元域中的符号)
取 。该模多项式在 中没有根,所以商是九元域,且 。我们有 ,其在素域中的逆元是二。因此 ;直接相乘得 。
该域的特征为三:三个 相加为零。它不是模九的整数算术。另外 的阶是四而不是八,这说明了为什么不可约模多项式并不自动使其剩余变量成为本原元。
例题 14.2.6
(通过检验的四次式,以及一个错误的捷径)
对 上的 ,相继的余式为 ,, 和 。四的唯一素因数是二,且 ,所以最大公因式为一,检验证明其不可约。
相比之下, 能通过最后的 Frobenius 检验:在其商中 ,所以 。但较小的检验中 ,最大公因式为 而不是一。该模多项式可约,其非零剩余类 与 相乘为零。仅凭最后的 Frobenius 等式无法区分域与这个环。
常见错误
常见错误
(把两个多项式变量分开)
在 上的码中, 描述单个符号的内部。码字多项式 以许多这样的符号为系数。对其 分量取模 ,并不意味着把码字多项式 对同一个多项式取模。循环码字的约化改用 ,而求值则是把一个域元素代入 。
常见错误
(压缩标签不是模 的整数)
在 中,以整数 作为 的标签。于是 的标签是 , 的标签是 ,而第一个例题表明两者之积为 。把标签模 相乘却得到 ,即 的标签。更糟的是 ,但 。标签只是存储方式;算术必须作用于系数列表。
常见错误
(找不到模多项式并不是错误的证书)
随机搜索总会检验其结果。它可能在预算内找不到模多项式,但绝不可能把可约的候选作为已认证的域返回。增大预算会改变失败概率的上界,而有效性的判据始终是确定性的。反过来,存在性证明或看似合理的乘法表都不是不可约性的证明。
总结
多项式余式给出精确的符号算术,素域上的 Euclid 算法给出逆元。Frobenius 余式与选定的最大公因式在多项式时间内证明不可约性。不可约多项式的密度进而给出带明确失败预算、随机性有界的构造。乘法阶的验证是单独的一步,其对因数分解的前提必须说明。
练习
快速检查
(为什么 要对 取模,而不总是存为字面上的多项式 ?)
考虑一次的模多项式。
解答
对一次模多项式, 已经约化为一个常数。统一的公式将 与同一个剩余类 比较。若把常数余式与未约化的一次表达式比较,会错误地拒绝有效的一次模多项式。
快速检查
(六次不可约性检验中,哪些更小的 Frobenius 下标已足够?)
列出 的素因数。
解答
六的素因数是二和三,所以下标 和 已足够,再加上最后的下标六。任何整除六的真因式次数至少整除这两个较小下标之一,因而被某个最大公因式检验排除。
快速检查
(在八元域中,为什么每个异于一的非零元素都是本原元?)
求乘法群的阶。
解答
其乘法群是七阶循环群,七为素数。异于乘法单位元的非零元素的阶整除七且不为一,所以是七。这一特殊情形不能推广到所有域的大小,九元域的例子就说明了这一点。
快速检查
(为什么生成算法的正确性不依赖于随机候选很可能不可约这一统计性保证?)
把“返回什么”与“多常返回”分开考虑。
解答
每个返回的候选都通过精确的充要检验。密度下界只控制有界搜索返回候选而不是报告失败的机会。偶然出现的一连串可约样本会耗尽预算,但绝不会产生虚假的域证明。