动机
一个模运算,在若干个较小的模下进行,可能比在一个大模下进行更容易。只有当各局部答案恰好确定唯一一个整体剩余类时,重构才有意义。中国剩余定理提供了这一保证,并把贝祖(Bézout)系数转化为合并部分信息的算法。
素性检验提出的是另一个问题:一个模是否具备许多模论证所需要的域性质?模恒等式不成立可以证明合数性;恒等式成立则可能只是说明这个特定的底没有暴露问题。我们将精确地证明两种检验究竟确立了什么,而不是把一个必要条件倒转成没有依据的素性证书。
前一章的算术内容提供了欧几里得(Euclid)算法、模逆元与重复平方。
定义
定义 9.1.1
(同余数据与合数见证)
对于整数 , 表示 。剩余重构问题是对同一个未知整数给出若干个这样的条件。素数是恰有两个正因数的整数 。合数见证是这样的数据:在某个已陈述的定理之下,其被验证的性质证明了某个大于一的整数不是素数。某个底通过检验,仅仅意味着没有得到该指定形式的见证。
定义 9.1.2
(强概率素数条件)
对于奇数 ,唯一地写成 ,其中 为奇数,。对选定的整数底 ,若 与 有非平凡的最大公因数,则立即得到一个因子。否则令
重复平方可以计算这条链。该底的强概率素数条件是:,或者对某个 有 。这里的等号使用从零到 的标准代表元; 代表负一。通过检验被有意地不称为素性证明。
定理/命题
定理 9.1.3
(构造性中国剩余定理)
设 两两互素, 为整数剩余。则模 恰有一个解类。从 出发,对每个新条件 ,计算
并把 同时替换为 。该状态始终满足 ,并且恰好表示已处理条件的全部解。
定理 9.1.4
(试除法是确定性的素性检验)
整数 是合数,当且仅当它有一个不超过 的素因数。因此,从整数除数 开始,在 时继续检验,就得到一个正确的确定性检验。如果检验的是所有整数而不只是素数,则至多需要 次试除。
定理 9.1.5
(强条件不成立即证明合数性)
每个奇素数 对每个允许的底都满足强概率素数条件。因此,若某个底与 的最大公因数为一,且不满足该条件,则 是合数。若某个中间值 满足 ,则 是 的非平凡真因子。
证明思路或证明
证明
(合并一个条件)
对于一次 CRT 合并,当前条件恰好给出 ,其中 为整数。新条件变为 。互素性使 在模 下可逆,所以存在唯一的类 。因此合并后的解类是模 的 。由 的界得 。这同时证明了初始化、保持性与唯一性。两两互素保证之后的每个乘积都与下一个模互素。
证明透视
合并在哪里用到互素
这个证明靠参数化把方程组化为一条同余式:已处理的条件恰好描述 ,于是新条件变成线性同余式 。互素只用了一次,就是使 在模 下可逆,从而恰好得到一个类 。由于 是先前各模数的乘积,两两互素给出 。范围的界完成论证:。若没有互素,关于 的同余式可能无解,也可能有多个类。
证明
(不超过平方根的最小因子)
对于试除法,若 是合数,写 ,其中 。则 。 的一个素因数也是 的因数,并且不大于 。反之,不大于 的素因数是真因数,从而证明了合数性。整数比较 避免了依赖平方根的浮点近似。
证明
(终于一的平方根链)
对于强条件,先回顾素数模下的费马(Fermat)恒等式。乘以一个非零剩余会置换非零类,所以把整组非零类相乘,再约去可逆的乘积,便得到 。因此 。若 ,令 为使 的第一个下标。它的前一项平方为一,且不是一。在素数域中, 迫使 或 ,所以那个前一项必为负一。它的下标小于 ,这就确立了强条件。
证明
(由非平凡平方根取出因子)
对于因子的断言,该同余式说明 。若 ,则由贝祖约去会迫使 ,与 矛盾。若该最大公因数为 ,则 ,这同样被排除。因此该最大公因数严格介于一与 之间。这一论证不需要假设合数模是无平方因子的。
证明透视
必要条件有一个有用的逆否命题
素数模满足强条件,因为它们仅有的一的平方根是正一与负一。因此条件不成立就证明该模是合数。反过来则不成立:合数模可能对某个特定的底模仿所要求的链。这个证明解释的是拒绝,而不是接受之后自动得到证书。
例题详解
例题 9.1.6
(一次合并保留全部解,而不只是一个猜测)
解 与 。第一次合并之后状态为 。由于 ,下一个修正量为 。新状态为 。检验得 且 。全部解为 ,其中 ,而不只是所显示的这个代表元。
例题 9.1.7
(局部计算再重构一个幂)
求 。模七时,六就是负一,得剩余六。模十一时,费马定理把指数化为三,得 。从 出发,解 ,得 ,。因此 。这种指数约化在素数坐标中是有效的,因为六与两者都互素;而重构本身保持精确的剩余,不引入任何数值近似。
例题 9.1.8
(费马检验通过而更强的链将其拒绝)
合数 满足 ,所以 。因此以二为底的费马检验通过并不能证明素性。对于更强的检验,,且 ,而 。所检验的链中项都不是 ,初始项也不是一,所以强条件不成立。这个非平凡平方根还给出 ,即一个显式因子。
重构不变量是一个精确的规格
在每次合并时,乘积描述的是已处理的所有条件的完整周期。代表元被保持在标准范围内,以限制其大小并简化之后的计算。不需要搜索最终乘积以下的所有整数,也不需要枚举局部剩余的所有组合。每一步所需的那个逆元由欧几里得算法提供。
以乘积一作为初始化,是空条件列表的内部状态。每个整数都满足零个条件,所以其解类是全体整数。第一个真正的模仍然至少为二,而一在该模下的逆元是显然的。把这一初始化与公开的模的定义分开,就避免了第一次合并时不必要的例外失败。
该方法可以独立检验:把最终代表元代入每个输入同余式。这验证了构造,而乘积模下的唯一性论证则确立了完备性。仅靠代入并不能证明已描述了全部解。程序可以同时给出其代表元与乘积,使数学规格的这两部分保持可见。
互素性与表示代价
如果两个模有公因子,它们施加的信息会重叠,并且可能互相矛盾。此时乘积一般不是正确的唯一性模。更一般的合并可以使用线性同余的可解性定理与最小公倍数,但那是另一种约定。上面证明的算法必须检查其互素性假设,而不是试图对非单位求逆。
乘积的二进制长度以输入各模的二进制长度之和为界。这并不使该乘积上的算术成为常数代价。之后的逆元、乘积与约化都作用于不断增长的整数。重构做线性次数的合并,但比特复杂度的陈述还必须计入算术子程序的代价。每次合并之后保持剩余有界,可以控制存储,但并不消除这些算术代价。
一个完全确定的强检验
小于二的整数视为非素数,二与三视为素数,更大的偶数以因子二拒绝。对于剩下的奇数,把它减一分解为一个奇因子乘以二的幂。选取一个允许的底,并计算它与该模的最大公因数。介于一与模数之间的最大公因数已给出因子证书;否则用重复平方求出奇数次幂的值以及随后的平方链。
若初始值为一,或者在最终指数之前所检验的任一链项为负一,则报告该底通过。若两者都不出现,则报告合数。当出现一的非平凡平方根时,可以提前停止,并按上述方法提取因子。这些出口意义不同:一个证明合数性,另一个只记录通过了某个条件。实现应返回不同的状态,而不应把两种结果都标成同一个是非定理的答案。
初始的模幂以及至多对数次的平方,利用先前证明的重复平方算法,需要 次模乘法。模乘法与最大公因数的计算仍有各自的比特代价。这里不声称任何概率误差界。这样的界需要另一个定理,说明对一个合数模最多有多少个底能通过,而不是仅仅重复执行必要条件的证明。
为什么试除法仍值得理解
试除法有简单而完整的正确性论证,并且在拒绝时给出一个除数。它的局限在于其代价取决于数值的平方根,而不是输入的二进制长度。素数输入会使循环检验直到该阈值的每个候选者,相对于位数而言这可能极其巨大。但这个方法对于小的输入,以及在应用其他方法之前去除小因子,仍然有用。
更快的拒绝检验与完整的确定性素性证明是不同的目标。强条件对许多输入给出高效且在严格意义上有依据的拒绝,但一个底通过并不能解决所有输入。试除法在精确算术之下最终能解决每个整数,但所需工作量可能大得多。学生应当先弄清一个算法证明了什么,再比较它的速度。
概念视角算法
证书、检验与重构回答的是不同的问题
CRT 证明局部的值描述了唯一一个整体剩余类。非平凡的最大公因数证明了一个因子。强链不成立证明素数域中的某个蕴含已被破坏。链通过则是较弱的结果,在成为素性保证之前还需要额外的数学。把这些输出区分清楚,可避免把算法未曾证明的结论当成它的保证。
常见错误
强检验“通过”是最常被误读的结果。
反例模式
即使强检验通过也不是素性证书
取 ,底为九。由于 且 ,初始链值为 。这个底通过了强条件,尽管该模是合数。修正后的结论是:拒绝证明合数性;对某个特定底的接受并不是素数定理的逆命题。
常见错误
(试除循环停在平方根边界之前)
试除循环必须包含相等情形 。对 ,唯一的素因数是 ,而 。若用严格的 ,循环在 就停止,并错把 判为素数。排除边界会漏掉素数的平方。
常见错误
(把指数按模数约化)
不要把指数按值所在的模来约化。指数周期需要经过论证的定理及单位假设,而重复平方不需要这样的约化。模 时 ,但把指数 模 约化为 之后,,结果是错的。
反例模式
两个同余式未必有公共解
声称:任何两个同余式都有解,而且解在模数乘积之下唯一。取 与 。第一式迫使 为奇数,第二式迫使 为偶数,所以没有整数同时满足两式。这里 不整除 。修正:设 ,解存在当且仅当 整除两个余数之差,而且此时解在模 下唯一;若模数互素则 ,便得到所述的定理。
总结
CRT 利用一个逆元和一个维持的周期来合并精确的局部信息。试除法给出完整的确定性判别准则,其数值代价为平方根量级。强合数见证利用素数域的平方根性质,给出严格的拒绝;对其接受状态,必须按照定理实际的量词来解读。
练习
快速检查
(对 取底 3 应用强条件,若出现非平凡平方根,则求出一个因子。)
利用 。
解答 · 答案
此处 ,所以 。由于 ,,既不是一也不是九十。在 之前没有其他需要检验的下标,所以这个底拒绝。而且 , 给出一个因子。与底为九时的结果不同,这与依赖于底的必要条件是一致的。
快速检查
(解 与 。说明为什么模乘积的唯一性不成立。)
使用线性同余定理,而不是使用不存在的逆元。
解答 · 答案
写 。另一个条件给出 ,即 ,从而 。因此 。模六十的两个不同的类十三与四十三都是原方程组的解。这些模并不互素;它们的 lcm 是三十,所以乘积模的唯一性断言是错误的。
快速检查
(说明为什么对 ,试除循环必须检验 11。然后利用素因数定理证明 127 是素数。)
列出不超过相关平方根的每个素数。
解答 · 答案
合数 没有小于十一的素因数,所以严格不等号会漏掉它唯一的素因数。对于 ,不超过其平方根的素数候选者是 。它们各自的余数为 ,全都非零。不存在不超过平方根的素因数,所以该定理证明了素性。