动机
配套小节定义了强序列,给出了精确的算法,并证明了素数输入总能通过检验。本节固定一个奇合数,证明被它欺骗的底数个数有一个上界。关键在于把每个通过检验的底数都装进同一个真子群;通过检验的底数本身未必构成子群。对于含有不同素因子的模数,用中国剩余定理(CRT)处理;对于素数幂,则用一个小的主单位处理。与配套小节一样,记 ,其中 , 为奇数;第 阶段指剩余 。
定理/命题
与 不互素的底数
引理 8.3.1
(不互素的底数总不通过)
设 为奇数,且 。则对每个 都有 。特别地,即使省略 gcd 这一步, 也不会通过检验。
证明
(模公因数约化)
假设 ,其中 。由于 ,同一同余式在模 下也成立。但 ,所以左边 ,于是 迫使 ,矛盾。
因此,每个通过检验的底数都是模 的单位。记 ,它是阶为 的交换群,并记
一半界
定理 8.3.2
(一半界)
设 为奇合数。则 中通过检验的底数个数满足
因此,从 中均匀随机抽取的底数通过检验的概率至多为 ,严格小于 。
快速检查
(对 ,直接求出通过检验的底数集合 ,并把 与 比较。)
此时 ,所以 ,;先列出各单位的平方。
解答 · 答案
单位为 ,它们的平方只有 。阶段 恰好让 通过,即 。阶段 需要 ,但 不是平方数。阶段 需要 ,但 的平方分别是 。因此 ,。通过概率为 ,正如定理所要求,低于一半。
证明思路或证明
证明
(包含每个通过底数的真子群)
固定奇合数 ,, 为奇数,。由于 ,剩余 与 模 不同,且 是 的一个二阶子群。
第 1 步:选取阶段 。 令
集合 含有 ,因为取 时,由 为奇数得 。所以 非空且有限,令 ,并令
按构造,存在单位 使得 。此外,对任何满足 的被检验阶段 ,都没有单位在该阶段取值为 。
我们不需要单独讨论“ 为空”的情形。集合 总是包含 和 ,而且下面的论证从未用到 非空这一点。阶段 是通过单位 来定义的,无论是否还有其他单位到达 。
第 2 步: 是子群。 定义 为 。由于 是交换群,,所以 是群同态。于是
是子群在同态下的原像,因而是 的子群。
第 3 步:每个通过检验的底数都属于 。 设 。 通过检验有两种方式。
- 情形 。 此时 ,所以 。
- 情形 对某个阶段 成立。 此时 (以 为见证),由最大性得 。写出 。若 ,该值为 。若 ,指数 为偶数,该值为 。无论哪种情形都有 。
这正是把 选为最后一个阶段起作用的地方。通过检验的底数在阶段 或更早到达 ,绝不会更晚。一旦底数到达 ,此后每次平方都得到 。因此在阶段 ,所有在更早阶段通过的底数都位于 ,恰在阶段 通过的底数位于 。满足 的底数则一直位于 。单个子群 就容纳了所有这些底数。
第 4 步: 是真子群。 我们必须构造一个单位 ,使得 。由于 是合数,下面两种情形恰有一种成立。
情形 A: 至少有两个不同的素因子。 取素数 ,并设 为整除 的 的精确幂。令 ,。则 ,且 与 都是大于 的奇数,所以都至少为 。设 为第 1 步中满足 的单位。由 CRT,存在整数 使得
于是 与 互素(因为 与 互素),也与 互素,所以 。它的 次幂满足
若 ,则模 约化得 ,即 。由于 ,这不可能。若 ,则模 约化得 ,同样不可能。因此 ,即 。
像 具有混合符号:在一个互素分量上为 ,在另一个分量上为 。这样的元素是模 的 的非 平方根,而这恰是素数模数不可能拥有的对象。
情形 B:,其中 为奇素数且 。 令 。由于 , 是单位。对每个整数 ,二项式定理给出
因为 的每一项都能被 整除,而 恰当 时成立。因此 当且仅当 ,即当且仅当 。所以 的阶恰为 。
现在 。事实上, 为奇数,所以 。又 且 ,若 则 。因此 。此外,,而由于 为奇数,。所以 也成立。于是 。
在情形 B 中,我们没有用到 的具体取值,只用到 与 互素。就这一点而言,素数幂的情形更容易。
第 5 步:计数。 是有限群 的真子群。由拉格朗日(Lagrange)定理, 整除 ,且 ,所以 。由第 3 步,。
其次,对合数 有 。在 中, 的每个素因子 都满足 且 ,所以 中至少有一个元素不是单位。由上述不互素底数的引理,非单位不贡献任何通过检验的底数。因此
除以 个等可能的底数,得到通过概率至多为 ,严格小于 。
证明透视
各个假设在一半界中的位置
每个假设都只在一个可以指明的地方使用。 为奇数给出 ,使 非空;它也使情形 A 中两个 CRT 分量都至少为 ,所以具有混合符号的元素不可能是 。 为合数只在第 4 步用到。若 是素数,两种情形都不存在,而结论也确实不成立:此时 ,,由欧拉(Euler)判别法,每个单位都属于 ,所以 。 的交换性只用来保证 是同态。
唯一不显然的一步是选取 ,它要同时满足两个方向相反的要求。第 3 步需要 不小于任何通过底数到达 的阶段;第 4 步的情形 A 则需要在阶段 本身有单位 使 。较小的下标违反第一个要求: 的见证 是通过检验的,而若 且 ,平方后会得到 ,所以 不在较小下标所定的子群内。较大的被检验下标不属于 ,因此情形 A 没有见证可用。
论证以计数收尾,而不是刻画 。第 3 步只给出 ,再由拉格朗日定理控制 。情形 B 完全不看 :它的障碍是一个阶为 的元素,而 ,因为 而 。
检验边界情形
带有情形分拆和精心选取下标的证明,应当用小例子来检验。下面说明各个成分在若干奇合数上的表现。
例题 8.3.3
( 时的素数幂障碍)
。 此时 ,所以 ,。模 的单位的平方为 。由于 不是平方数,没有单位在阶段 或 到达 。所以 ,,。适用情形 B,取 ,则 。
例题 8.3.4
( 时 CRT 的混合符号)
。 此时 ,所以被检验的阶段只有 ,必有 ,。适用情形 A,,,。CRT 给出 ,因为 且 。于是 ,所以 ,它不是 。
。 此时 ,,且某些单位在阶段 到达 。所以 ,并且用到了第 3 步中“更早阶段映到 ”的部分。见关于 的素数幂的练习。
例题 8.3.5
(包含通过底数但比它更大的子群)
。 此时 ,所以 ,。一个单位要在阶段 到达 ,必须同时在模 和模 下都如此。 与 的 -部分都是 ,所以 可以出现在阶段 ,但不会出现在阶段 或更晚。确实 ,所以 ,。
- 模 下 的平方根为 。例如 。所以 。
- 的平方根为 ,其中 。所以 ,。
- 取 ,, 的第 4 步 CRT 构造给出 ,因为 且 。于是 ,所以 。它具有混合符号,模 为 ,模 为 ,且不是 。
- 注意 。底数 和 属于 但不通过检验:对 ,,,所以 是 的非平凡平方根。子群 是 的容器,而不是对 的刻画。
。 这是配套小节中的卡迈克尔数(Carmichael number)。模 下,单位的任何偶次幂都是 ,所以没有单位在阶段 时模 到达 。因此 ,。适用情形 A,例如取 ,。见关于卡迈克尔数的强说谎者的练习。
另有两点说明。
- 若 ,则 ,且 的每个元素都在阶段 通过检验。所以恰有 。严格包含只可能在 时发生,例如 。
- 情形 A 并不要求 无平方因子。例如 属于情形 A,取 ,。只有当 是单个素数的幂时才使用情形 B。
定理控制的是一轮检验。完整的检验会用新的底数重复这一轮,界也随之相乘。
快速检查
(用 个从 中独立、均匀抽取的底数检验奇合数 。求全部 轮都通过的概率的上界。)
一轮用定理,乘积用独立性。
解答 · 答案
由定理,每一轮通过的概率至多为 ,而这个数小于 。各轮相互独立,所以全部 轮都通过的概率是乘积,至多为 。独立性不可缺少:把同一个底数重复使用 次,并不比只做一轮更好。
常见错误
常见错误
(取最后一个被检验的阶段,而不是最后一个到达 的阶段)
直接取 似乎很自然。集合 仍然包含每个通过检验的底数,但不一定是真子群。对 ,有 ,所以 。由于 是 、 和 的倍数,每个单位在模 、、 下都满足 ,因此模 也如此。这个子群就是整个群,什么也控制不了。证明用的是某个单位真正到达 的最后阶段;情形 A 需要的正是这个见证。
反例模式
强说谎者不一定构成子群
一个看似合理的说法是:合数 的通过底数构成 的子群,就像费马(Fermat)说谎者那样(它们是 的核)。对 ,上面的例题已求得 。 和 都通过,但 ,乘积为 。对 ,有 和 ,所以这一轮从未遇到 , 不通过。因此 对乘法不封闭。正确的说法正是证明所用的: 包含于子群 ,而拉格朗日定理计数的只是 。
常见错误
(把界读成“通过的数是合数”的概率)
定理控制的是一个固定合数通过检验的概率:经过 轮独立检验后,。它并没有说通过了 轮的数是合数的概率低于 。这个反向概率取决于输入是如何选出的,例如候选数中素数所占的比例,须用贝叶斯(Bayes)公式计算。
练习
快速检查
( 的素数幂:设 。你可以使用如下事实: 是 阶循环群,由 生成。)
(a) 求 和 。然后利用生成元的指数,求解配套小节中强条件定义的各个条件,精确确定通过检验的底数集合 。
(b) 追踪底数 的一轮检验。
(c) 按一半界的证明确定 、 和 。验证 在 之外,既要直接计算,也要利用二项式公式 。
(d) 说明在阶段 通过的两个底数在阶段 时的表现。
解答
(a) 有 ,所以 ,。该轮检验考察 是否为 ,以及 、 是否为 。写 ,其中 取模 。由于 ,有 。又因为 ,所以 。
- 意味着 ,所以 。这给出 。
- 意味着 ,所以 。这给出 。
- 意味着 ,即 。所以 ,给出 以及 。确实 ,且 。
- 意味着 。模 约化得 ,所以无解。
因此 。底数 在 gcd 这一步就失败。所以 个底数中有 个通过检验,不超过 。
(b) 对 :,所以 ,它不是 。在循环中, 时 。所以 ,该轮在阶段 通过。
(c) 某个单位,例如 ,在阶段 到达 ,而在阶段 没有单位到达 。所以 ,。计算 。
- 意味着 ,即 ,所以 ,。
- 已在 (a) 中解出,得 。
所以 ,,是指数为 的子群。对 :,,。二项式公式给出 ,与之一致。由于 ,有 。这里用到 ,而这成立是因为 且 为奇数。
(d) 底数 始终保持在 。底数 在阶段 位于 ,在阶段 变为 。所以在阶段 ,阶段 通过的底数位于 ,阶段 通过的底数 和 位于 。这四个都属于 ,正如证明的第 3 步所预言的那样。
快速检查
(卡迈克尔数的强说谎者:设 ,所以 ,。)
(a) 证明对 ,不存在模 的单位 满足 。由此得出 且 。
(b) 利用 CRT 以及 是 阶循环群这一事实,精确计算 。
(c) 将 与界 以及费马说谎者的个数作比较。
(d) 仿照证明中的情形 A,取 ,,构造一个明确的单位 ,并计算 。
解答
(a) 模 的单位 也是模 的单位,所以 。对 ,指数 为偶数,所以 。若某值 ,则它模 约化为 ,这不可能,因为 。所以 ,,。通过检验要求 ,而每个这样的 都在阶段 通过。因此 。
(b) 当且仅当该同余式模 、、 都成立。对每个分量计数,利用在 阶循环群中方程 恰有 个解。
- 模 :,因为 为奇数且 。每个符号各有 个解。
- 模 :,因为 。方程 有 个解。对 ,取生成元 并写 。则 ,而 恰当 为奇数时成立,给出 个解。
- 模 :,因为 。由于 ,立方映射是该群上的双射,所以 各恰有 个原像。
由 CRT, 有 个解, 也有 个。这两个集合不相交,所以 。
(c) ,所以界为 ,而 。通过概率为 。由配套小节的卡迈克尔数例子,全部 个单位都是费马说谎者。因此强检验把说谎者的个数从 减少到了 。
(d) 取 ,它满足 。我们需要 且 。写 ,并利用 ,需要 。所以 ,。
于是 且 。整数 满足同样的两个同余式,所以 。这既不是 也不是 ,所以 。此外 :它模 和模 都是 。所以 是 的非平凡平方根,且 。