动机
勒让德(Legendre)符号用于检测模素数下的平方数,但它的定义本身就假定分母为素数。雅可比(Jacobi)符号把算术互反律的规则推广到每个正奇数分母。它的定义用到素因数分解,但借助互反律,我们可以在不求出这些素因子的情况下计算它。
这一区别在计算上很有用,在概念上却很危险。雅可比符号取值为一,并不能证明它是模合数的平方;符号被快速算出,也不能证明分母是素数。我们将证明精确的规则,在算法中维护一个带符号的不变量,并准确指出其输出究竟能确立什么。
本章使用前面的素数二次互反律及其补充定律、唯一分解定理、欧几里得(Euclid)余数与最大公因数。输入要求中并未暗含任何素性判定或因数分解算法。本章所有分母都是正奇数;推广到偶数分母的克罗内克(Kronecker)符号不在本章范围之内。
定义
定义 6.3.1
(不以因数分解为输入的因数分解式定义)
对奇数 ,设其素因数分解为 ,定义
右边的符号是勒让德符号。对每个整数 (包括 ),规定 。雅可比符号为 当且仅当 ;否则它等于 或 。它只依赖于 模 的剩余类,并且对分子具有乘性。它对奇数分母也具有乘性,而且不要求两个分母因子互素。
该记号是数学记号,而不是有理数的商。在分母为素数时它就是勒让德符号;在分母为合数时,它把各素数处的结果连同重数组合在一起,因而可能损失信息。
概念视角组合
符号即一个置换的符号
对奇数 及 ,乘以 置换模 的剩余,而雅可比符号等于这个置换的符号;这里只陈述这一描述,不作证明。对 、,循环为 、、、 和 。四个偶数长度的循环给出符号 ,与 相符。这一描述同样不需要分解,但要处理全部 个剩余,工作量远多于欧几里得算法。
定理
定理 6.3.2
(奇数分母的互反律及两条补充定律)
对每个正奇数 ,
对互素的正奇数 ,
更一般地,重排后的规则
对所有正奇数 都成立:当它们有公因子时,两边都是零。
定理 6.3.3
(带符号的欧几里得算法可计算该符号)
对任意整数 与正奇数 ,下列算法返回 。先将 模 约化,令 ,当 时重复以下步骤:
- 将 写成 ,其中 为奇数。若 为奇数且 或 ,则把 换成 。
- 若 ,则把 换成 。
- 将 替换为 。
终止时,若 则返回 ,否则返回 。每连续两次非终止迭代,模数至少减半,因此在初始约化之后共有 次迭代。对于 比特的已约化输入,采用普通的竖式算术, 次比特运算是一个有效的保守界。若初始分子更长,则其约化的代价须另行计入。
证明思路
证明
(由素数互反律得到奇数分母互反律)
剩余性质与乘积规则。 每个素因子对应的勒让德符号都具有剩余性质与乘性,因此它们的乘积也具有这些性质。若存在公因子,则至少有一个勒让德因子为零;若不存在公因子,则每个因子都是 。奇数分母相乘就是把它们的素数指数相加,所以即使两个分母的分解有重叠,分母乘性仍然成立。
补充定律。 对奇数 ,
由于 ,这是偶数。所以 的奇偶性等于 与 各自对应量的奇偶性之和。将各素数关于 的补充定律按重数相乘,便得到 。同样,
是偶数,因为 且 。将各素数关于二的补充定律相乘,便得到 。这些论证同样适用于素数幂的情形;若把分母当作无平方因子数处理,就会得到错误的符号。
互反律。 设 与 互素。每一对交叉的素数贡献 次素数互反律的符号,总奇偶性为
由奇数乘积的奇偶性恒等式,这两个因子模 分别与 和 同余。于是互反律得证。若某个素数同时整除 与 ,则两个雅可比符号均为零;这就给出了算法所需的重排规则,而无须事先知道最大公因数。乘积形式的陈述仍须保留互素假设:两个零符号之积并不等于所示的符号。
证明
(带符号欧几里得算法的正确性)
在每一阶段,不变量是
其中 是原来的输入,而 是奇数。初始约化保持该不变量,因为符号只依赖于 模 。去掉 相当于把当前符号乘以 ,这正是第一次符号更新。重排后的互反律给出 ,其符号就是第二次符号更新;而 给出新的数对。无论是否存在公因子,这些步骤都保持不变量,而且新分母 仍是奇数。
约化之后 ,所以当前分母严格递减,循环必以 终止。对 ,;对 ,按空积约定它为 。这就证明了返回规则。最大公因数也保持不变:因为 是奇数,,而 。因此最终的 等于 ;零的结果并不是某个未完成计算中遗留下来的部分符号。
证明透视
奇数性、零规则与不变量各在何处使用
证明从不直接计算该符号;它一直携带“原来的符号等于 乘以当前符号”这条等式,只改变当前数对。三个假设在特定位置被使用。当前分母为奇数,才使两条补充定律与互反律可以应用,也使去掉二的因子不影响最大公因数;算法只把奇部 移入分母,从而维持这一点。第二次符号更新用的是在最大公因数大于一时仍然成立的重排互反律;互素的乘积形式需要预先知道最大公因数,而这正是算法尚未算出的东西。最后,关于二的补充定律要读取当前分母,因为不变量讲的是当前符号。
论证在 处闭合,此时两件事相遇:空积约定在分母为一时给出值一,而最大公因数的保持说明终止时的分母就是原来的最大公因数。缺少后者,返回的零便无从解释。整个过程从不索取输入的素因子,所以快速求值并不是素性证书或平方根证书。
证明
(迭代次数与比特开销界)
约化之后,正的分子小于分母 ,其奇部 也是如此,而 就是下一个分母。若 ,一次迭代便使分母减半。否则 ;若它为零,算法停止;若不为零,再下一个分母是它的奇部,至多为 。因此每两次迭代分母至少减半,而多去掉的二的因子只会使它更小。
设初始约化后的分母有 比特,则迭代次数为 。读取模 或模 的余数以及剥去末尾零比特只需 次比特运算,而不超过 比特的两数之间的竖式带余除法代价为 。由此得到总计 的界。这是一个保守的、已证明的界,并不是对快速算术下最优性的断言。若分子的比特数远多于 ,则其初始模约化必须另行计入;仅以 表示的代价界会遗漏输入的一部分。
例题详解
例题 6.3.4
(不分解分母的多步求值)
对 ,相继得到的已约化数对为
偶数分子 贡献一个因子二,而分母 ,所以符号不变。没有任何一次互反律交换中的两个奇数参数同时模 余 。在数对 处,去掉三个因子二会使符号改变,因为 。最后的奇数分子为 ,得到最终数对 。因此该符号等于 。余数的检验包括 与 ;计算中既没有使用也没有断言 的任何因数分解。
例题 6.3.5
(公因子由终止时的分母检测出来)
对 ,第一次交换时 ,符号不变,得到 。去掉一个因子二会使符号改变,因为 ,留下的奇部为 。下一个余数是 ,所以终止时的分母为 。返回值为 ,与公因子 一致。
中间的符号为负,但它要与终止时的零符号相乘。若只返回该符号,就会把一个部分不变量误当作答案。该算法无须先对任何一个整数作因数分解,便能检测出非平凡的最大公因数。
例题 6.3.6
(雅可比值为一并不是平方证书)
对 ,由素因子得 与 ,因此两者之积为 。然而 并不是模 的平方,因为模 约化后需要一个模 余 的平方数。等价地,互反律给出 。
损失的信息是各素数处分别的符号:两个负的结果相乘得到正的结果。对于奇数平方分母,这种损失更为明显:每个与分母互素的分子,其符号都是 ,因为每个素数的指数都是偶数。素性检验必须把该符号与额外的模幂信息作比较,而不能把它当作单独的判决。
常见错误
反例模式
互素时的乘积形式不能用于有公因子的情形
取 ,则两个雅可比符号之积为零,而互反律中的符号为负一,因为两数模四都余三。这并不矛盾:那条乘积等式要求互素。重排后用于算法的规则读作“零等于带符号的零”,仍然成立。只有当这些符号都是非零的符号时,这两种写法才等价。
常见错误
(用最初的分母读取关于二的补充定律)
去掉因子二时的符号取决于当前分母模 的余数。在 中,因子二是在数对 处去掉的,而 ,符号不变。若改用 ,便会把符号翻转而返回 ,正确值却是 。二的因子只从分子中去掉;分母始终保持为奇数。
常见错误
(终止分母大于一时仍返回累积符号)
约定 只适用于分母为 的情形。若循环终止于 且 ,则无论 是什么,答案都是 ;在 中累积符号是 ,但该符号等于 。
快速检查
快速检查
(若算法输出 ,原来的分子是否必定模 为 ?)
解答 · 答案
不必。输出 表示终止时的分母,即 ,大于 。取 、,输出为 ,但 ;最大公因数是 。
快速检查
(若输出为 且 , 是否必定有模 的平方根?)
解答 · 答案
不必。,但 不是模 的平方,因此也不是模 的平方。两个负的素数符号相乘得到 。
练习
练习 6.3.7
(用该算法求 ,并交代每一次符号更新与剩余约化。)
基础
解答(3)
- 1
约化并作第一次交换
。由于 是奇数且 ,符号不变,下一个数对是 。
- 2
去掉因子二并交换
,且 ,所以关于二的补充定律为正。此时 ,故 ,下一个数对是 。
- 3
完成循环
给出 与数对 ,然后是 。答案为 ,与 一致。
练习 6.3.8
(证明:对奇数 ,当 时 ,否则为 。并给出一个模 下与 互素的非平方例子。)
核心证明
解答(3)
- 1
按因数分解写出平方分母
若 ,则 ,所以 。
- 2
利用每个指数都是偶数
关键一步
若 ,每个勒让德因子都是 ,其偶次幂为 。若 ,则某个 ,给出一个零因子。
- 3
给出例子
∎模 的单位平方数是 。所以 与 互素且 ,但它不是模 的平方。
练习 6.3.9
(在下一个奇数分母 大于旧分母 一半的情形下,验证“两次迭代减半”的论证。为何去掉二的因子不会破坏该界?)
核心证明
解答(3)
- 1
计算下一个余数
。
依据: 迫使商为 。
- 2
再跟进一次迭代
若 ,算法已经终止。否则再下一个分母是 的奇部,至多为 。
- 3
计入去掉的二的因子
∎去掉二的因子是把一个数换成它的一个因数,所以只会使下一个分母变小。至多两步之后,原来的大小便减半。
练习 6.3.10
(说明分母的因数分解如何验证雅可比符号的计算、为何寻找它不是算法的一步,并由输出 给出一个有效结论和一个无效结论。)
综合
解答(3)
- 1
以因数分解作独立检验
给定 ,可以把勒让德符号 相乘;这是按定义重新计算同一个量。
- 2
为何算法不需要它
关键一步
带符号的不变量只使用已证明的互反律、补充定律与欧几里得余数,所以从不索取素因子。
- 3
有效与无效的结论
输出 说明 不是模 的平方:与 互素的平方会使每个勒让德因子都等于 。它并不说明 是素数;例如 ,而 是合数。
解答与相关笔记
各题解答已附于上面的练习中。本章给出了完整的奇数分母雅可比互反律及一种已证明的求值方法。克罗内克符号、欧拉(Euler)—雅可比概率素性检验以及高级的比特复杂度算法需要进一步的论证。