动机
相邻章节定义了强序列,给出算法并证明素数输入总会通过。本节在具体输入上运行算法,并分析实现代价。
定理/命题
定理 8.2.1
(每轮的正确性)
对奇素数,每个允许的底数均通过;对任意奇数输入,未通过的轮次可证明它为合数。相邻章节证明了这两点。
定理 8.2.2
(计算代价)
采用小学乘法和除法时, 比特输入的一轮强检验使用 比特运算;均匀选底数还需期望 个随机比特。下面的运算计数给出理由。
例题
在下面的追踪中,“阶段值”是 中的剩余 。值 记作 。
追踪表中未填写的后续阶段表示该轮已经停止,并非相应的幂没有定义。若底数在最大公因子检查时已被拒绝,就不会再执行模幂运算;若在某阶段通过,也不会再计算其后的平方。相反,为了比较强检验与费马(Fermat)检验而额外列出的末项,是教学上的补充计算,须与伪代码实际执行的步骤区分开。这一区分也影响代价分析:下文计算的是一轮可能用到的上界,提前停止的轮次可以少做许多运算。
例题 8.2.3
( 的追踪)
我们有 ,故 ,。该轮检查 是否为 ,并检查 、 是否为 。列 并不由该轮计算,列出它是为了解释失败情形。
| 底数 | 判定 | |||||
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 通过(阶段 0) | |||
| 2 | 1 | 2 | 4 | 7 | 4 | 不通过 |
| 3 | 3 | 不通过(gcd) | ||||
| 4 | 1 | 4 | 7 | 4 | 7 | 不通过 |
| 5 | 1 | 5 | 7 | 4 | 7 | 不通过 |
| 6 | 3 | 不通过(gcd) | ||||
| 7 | 1 | 7 | 4 | 7 | 4 | 不通过 |
| 8 | 1 | 8 | 通过(阶段 0) |
例如,对于 :,,。
每个与 互素而失败的底数最终都有 ,因此每个都是费马证据。这并非偶然。模 时 的平方根只有 (相邻章节关于 的平方根的练习),所以类型 2 的失败不会发生。通过的底数是 :八个底数中的两个,远在 之内。配套章节利用子群界研究这一例子。
例题 8.2.4
( 的追踪)
我们有 ,故 ,。循环为空,对互素底数的判定取决于 是否为 。我们还列出该轮不计算的 。
| 底数 | 判定 | 解释 | ||
|---|---|---|---|---|
| 1 | 1 | 1 | 通过 | |
| 2 | 8 | 4 | 不通过 | 费马证据 |
| 4 | 4 | 1 | 不通过 | 是 的非平凡根 |
| 7 | 13 | 4 | 不通过 | 费马证据 |
| 8 | 2 | 4 | 不通过 | 费马证据 |
| 11 | 11 | 1 | 不通过 | 是 的非平凡根 |
| 13 | 7 | 4 | 不通过 | 费马证据 |
| 14 | 14 | 1 | 通过 |
六个底数 在 gcd 步骤失败。
一些示例计算:。由于 ,我们得到 。由于 ,我们得到 。
底数 与 是费马说谎者,因为 ,但它们是强证据。每一个都是 的不同于 的平方根,而相邻章节关于非平凡平方根的引理由它们分解出 : 且 ,或 且 。只有 和 通过,所以 个底数中有 个通过。
例题 8.2.5
( 的追踪)
我们有 ,故 ,。该轮检查 是否为 ,并检查 是否为 。
一个结构上的捷径可以简化计算。我们有 ,且每个单位都满足 。所以 ,即 就是 模 的逆元。然后 。
| 底数 | 判定 | ||
|---|---|---|---|
| 1 | 1 | 通过(阶段 0) | |
| 2 | 11 | 16 | 不通过 |
| 4 | 16 | 4 | 不通过 |
| 5 | 17 | 16 | 不通过 |
| 8 | 8 | 1 | 不通过: 是 的非平凡根 |
| 10 | 19 | 4 | 不通过 |
| 11 | 2 | 4 | 不通过 |
| 13 | 13 | 1 | 不通过: 是 的非平凡根 |
| 16 | 4 | 16 | 不通过 |
| 17 | 5 | 4 | 不通过 |
| 19 | 10 | 16 | 不通过 |
| 20 | 20 | 通过(阶段 0) |
底数 在 gcd 步骤失败。
直接核验几项:,且 。另外 ,所以 。
对于 ,该轮计算出 ,随后 ,第 7 行以证书 返回 FAIL。于是 且 。底数 同样给出 与 。
没有任何单位在阶段 达到 。模 时,单位的每个偶次幂都是 ,而不是 。所以二十个底数中有两个通过。费马说谎者是 ,所以强检验拒绝了两个费马检验所接受的底数。
例题 8.2.6
(一个更大的追踪:,底数 )
我们有 ,故 ,。由于 是卡迈克尔数(Carmichael number)(见相邻章节),费马检验接受每个互素的底数。我们用与 互素的 运行强检验一轮。
分别模 、 和 计算,再用 CRT 合并,这样更高效。
- 模 :,故 ,此后每次平方都得 。
- 模 : 且 ,故 ,此后每次平方都得 。
- 模 : 且 ,故 。平方得 ,再得 ,再得 。
| 阶段 | 模 3 | 模 11 | 模 17 | 模 561 |
|---|---|---|---|---|
| 0 | 2 | 10 | 8 | 263 |
| 1 | 1 | 1 | 13 | 166 |
| 2 | 1 | 1 | 16 | 67 |
| 3 | 1 | 1 | 1 | 1 |
合并后的值可以直接核验:,,。
该轮的进程如下。第 2 行得到 ,它不是 。迭代 得 ,迭代 得 ,迭代 得 。第 7 行以 ( 的一个非平凡平方根)返回 FAIL。相邻章节关于非平凡平方根的引理提取出因子:
确实有 。
CRT 各列显示了这个非平凡根的来源。模 与模 的分量比模 的分量更早到达 。在阶段 ,各剩余的符号不一致:模 为 ,模 为 。配套章节在其证明中使用了这种符号混合的思想。
概念视角代数
通过即同步到达
把各阶段的值模每个恰好整除 的素数幂 约化,一轮就分拆成各分量上的独立序列。由于 是奇数, 恰好当 模每个这样的 都同号地 。所以一个底数通过,恰好当所有分量都从 开始,或所有分量在同一阶段都等于 。各分量在不同阶段到达就必然失败,正如 的追踪中,模 的分量落后了。
快速检查
(对 与 执行强检验的一轮。它在哪里停止?停止时暴露了 的哪些因子?)
此时 ,故 。
解答 · 答案
由于 且 ,第 2 行给出 ,它既不是 也不是 。在迭代 中,,所以第 7 行以 返回 FAIL,而 是 的平方根且不是 。于是 ,。虽然 允许四次迭代,该轮在一次平方后便停止。
代价:算术运算次数与比特运算次数
设 为 的比特数,这就是输入的规模。
算术运算次数。 用从左到右的平方–乘算法计算 ,至多使用 次模 乘法。此后循环至多再执行 次平方。由于 ,一轮中模乘法的总次数至多为
因此一轮使用 次模乘法, 轮使用 次(见关于一轮成本的练习)。
快速检查
(计算上面 、 那一轮所用的模乘法次数,并与上界 比较。)
把 写成二进制。
解答 · 答案
二进制下 。从左到右的平方–乘算法以 对应最高位,之后对其余五位各平方一次,并对最后两个为 的位各乘以 一次:共 次乘法,不超过 。循环在迭代 中各平方一次,再多三次乘法。该轮总共用 次。由于 ,有 ,上界为 。
比特运算次数。 把模乘法当作单位代价的运算,会掩盖被相乘的数的大小。每次乘法是至多 位的剩余之间的乘法,产生至多 位的乘积,随后还必须模 约化。
- 采用小学乘法和长除法时,每次模乘法的代价为 次比特运算。于是一轮的代价为 次比特运算, 轮为 。
- 若用 表示用更快的算法将两个 位整数相乘的代价,且模 约化所用技术的代价与一次乘法相当,则一轮的代价为 。
- gcd 步骤使用欧几里得(Euclid)算法。它对至多 位的数执行 步除法,因此在粗略的小学算法计数下为 次比特运算。更细致的分析给出 。无论哪种,它都不会主导取幂的代价。
- 抽取一个底数的期望代价为 个随机比特。 拒绝采样的循环没有有限的确定性最坏轮数;把采样计入后,上述总运行时间是期望界。
与试除法的比较。 对素数 ,用不超过 的所有整数做试除,需要约 次除法,这关于输入规模 是指数级的。米勒–拉宾(Miller–Rabin)检验关于 是多项式的。
常见错误
(把乘法次数当作运行时间)
诸如“该检验需要 步”的说法,只有当每一步指一次模 乘法时才正确。每一步都要相乘至多 个比特的数,所以用教科书式算术,一轮需要 次比特运算, 轮需要 次。比较运行时间之前,必须先说明采用哪种代价模型。
快速检查
(采用教科书式算术时,若 的比特长度 加倍,一轮比特代价的上界大约增大多少倍?与试除到 比较。)
比较 与 ,以及 与 。
解答 · 答案
上界 变为 ,所以上界增大 倍。试除的次数约为 ,变为约 :它乘以 ,而这个倍数本身随 指数增长。
概率素数不是已证明的素数
这两种判定的逻辑地位截然不同。
- COMPOSITE 是一个证明。 失败的底数连同相邻章节所分类的失败类型,是一个任何人都可以用一次取幂或一次 gcd 计算来验证的证书。
- PROBABLE-PRIME 不是证明。 它表示 个独立选取的底数全部通过。配套章节界定了对合数输入出现这一事件的概率,但并不排除该事件,而且该检验产生的任何东西都不能让第三方验证 是素数。
当必须真正确立素性时,需要另一种素性证明方法。这类方法产生的证书,其验证不依赖于随机性。这些方法超出了本笔记的范围。在实践中,米勒–拉宾检验常被用作它们之前的快速过滤器,以低廉的代价剔除绝大多数合数候选。
例题 8.2.7
(迫使算法提前停止的平方根)
取 、,写 。首项 既不是 也不是 ;下一项 ,所以本轮立即拒绝。实际上 ,,得出两个素因子。之后的值虽然都是 ,算法却已经停止,不能因此把拒绝改成接受。
这个根有具体的 CRT 解释:,而 。平方消去不同的符号,因此在两个因子模下都得到 。混合的符号说明 整体上既不是 ,也不是 ;对于素数模,相应的因式分解论证排除了这一现象。
费马证据不一定立即给出因子。取 、,则 ,。由于 ,该轮算出 ,它既不是 也不是 ,于是在第 9 行失败。未计算的值为 ,所以 是费马证据, 被证明为合数。然而 ,且 :这一轮的值没有一个能通过这些 gcd 暴露真因子。合数性的证书与一个显式因子是不同类型的输出。
练习
快速检查
(一轮的代价:设 为奇数,比特长度为 ,, 为奇数。)
(a) 证明:从左到右的平方–乘算法使用至多 次模乘法计算 。由此推出一轮至多使用 次模乘法。
(b) 假设采用小学乘法和除法,使得一次模 乘法的代价至多为 次比特运算( 为常数),在不计 gcd 与底数生成的情况下,界定 轮的比特代价。
(c) 对于 位的奇数 ,给出每轮模乘法次数的一个显式上界。将其与用试除法(除到 )确认素性所需的试除次数进行比较。
(d) 解释为什么“关于 的多项式”会是错误的效率标准。
解答
(a) 设 有 位。从左到右的平方–乘算法从 开始,这对应最高位。对其余的 位中的每一位,它平方一次,若该位为 ,再乘以 一次。这至多是 次乘法。
由于 ,有 ,又因为 是整数,。循环至多再增加 次平方。总数至多为
(b) 一轮的代价至多为 次比特运算,所以 轮的代价小于 。这是 次比特运算。
(c) 奇数 位的 满足 。所以 ,。由 ,上界至多为 次每轮模乘法。
对素数 ,试除法到 需要检验每个不超过 的候选因子。即使只限于奇数候选,也超过 次除法,这是一个大得多的天文数字。
(d) 输入用 个比特书写,所以效率必须作为 的函数来衡量。关于 呈多项式的算法,例如代价约为 的试除法,关于 是指数级的,对密码学规模的数不可行。米勒–拉宾检验在小学算术下的代价 关于 是多项式的,这正是它具有实用性的原因。