动机
数论与密码学中的许多算法都需要大素数。例如,它们可能需要一个有数百甚至数千个二进制位的素数。最直接的素性检验是试除法:逐一尝试所有不超过 n \sqrt{n} n 的可能因子。其代价大致与 n \sqrt{n} n 成正比,而输入的规模是 n n n 的比特数,约为 log 2 n \log_2 n log 2 n 。因此试除法的运行时间关于输入长度是指数级的。对于一个 1024 位的数,n \sqrt{n} n 约为 2 512 2^{512} 2 512 ,如此规模的计算是不可行的。
费马(Fermat)小定理给出了一个快速的必要条件:若 n n n 为素数且 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 ,则 a n − 1 ≡ 1 ( m o d n ) a^{n-1}\equiv 1 \pmod n a n − 1 ≡ 1 ( mod n ) 。这个条件可以用模幂运算在关于 log n \log n log n 的多项式时间内验证。但该条件并不充分,而且有些合数对与其互素的每一个底数都满足它。本篇笔记研究费马条件的一个加强形式,即强概率素数条件 ,以及建立在其上的随机化检验,即米勒–拉宾检验 (Miller–Rabin test)。
这一加强利用了素数的一个事实,而费马检验忽略了这一事实:在素数模下,1 1 1 的平方根只有 1 1 1 和 − 1 -1 − 1 。米勒–拉宾检验并不止步于 a n − 1 a^{n-1} a n − 1 ,而是考察通向 a n − 1 a^{n-1} a n − 1 的反复开平方所得的链条,并检验该链条的行为是否符合素数模下必须具有的行为。
本章证明素数输入总能通过检验。配套章节证明合数情形的误差界:
若 n n n 为素数,则 { 1 , … , n − 1 } \{1,\dots,n-1\} { 1 , … , n − 1 } 中每个底数都通过。
若 n n n 为奇合数,则 { 1 , 2 , … , n − 1 } \{1,2,\dots,n-1\} { 1 , 2 , … , n − 1 } 中至多有一半的底数通过。
结合独立随机选取底数,这些结果给出一个保证清晰的检验:判定为合数的结论总是正确的;对任意固定的合数输入,经过 k k k 轮后得出概率素数结论的概率小于 2 − k 2^{-k} 2 − k 。我们还将仔细说明这一保证没有断言什么。
全篇假定你熟悉中国剩余定理(CRT)、费马小定理、平方–乘取幂算法、群同态与拉格朗日(Lagrange)定理,以及关于素数幂的初等整除性。
从费马检验到 1 的平方根
费马说谎者
设 n ≥ 3 n \ge 3 n ≥ 3 为奇数。若 n n n 为合数,而整数 a a a 满足 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 且仍有 a n − 1 ≡ 1 ( m o d n ) a^{n-1}\equiv 1 \pmod n a n − 1 ≡ 1 ( mod n ) ,则称 a a a 为 n n n 的费马说谎者 。费马说谎者正是使费马检验给出错误印象的底数。
例题 8.1.2
(为何 n = 561 n=561 n = 561 的每个单位都能欺骗费马检验)
有些合数的单位中只有 费马说谎者。一个标准的例子是 n = 561 = 3 ⋅ 11 ⋅ 17 n = 561 = 3\cdot 11\cdot 17 n = 561 = 3 ⋅ 11 ⋅ 17 。我们可以直接验证。设 gcd ( a , 561 ) = 1 \gcd(a,561)=1 g cd( a , 561 ) = 1 ,则:
模 3 3 3 :a 2 ≡ 1 a^2\equiv 1 a 2 ≡ 1 ,且 2 ∣ 560 2 \mid 560 2 ∣ 560 ,故 a 560 ≡ 1 ( m o d 3 ) a^{560}\equiv 1 \pmod 3 a 560 ≡ 1 ( mod 3 ) ;
模 11 11 11 :a 10 ≡ 1 a^{10}\equiv 1 a 10 ≡ 1 ,且 10 ∣ 560 10\mid 560 10 ∣ 560 ,故 a 560 ≡ 1 ( m o d 11 ) a^{560}\equiv 1 \pmod{11} a 560 ≡ 1 ( mod 11 ) ;
模 17 17 17 :a 16 ≡ 1 a^{16}\equiv 1 a 16 ≡ 1 ,且 16 ∣ 560 16 \mid 560 16 ∣ 560 (因为 560 = 16 ⋅ 35 560 = 16\cdot 35 560 = 16 ⋅ 35 ),故 a 560 ≡ 1 ( m o d 17 ) a^{560}\equiv 1\pmod{17} a 560 ≡ 1 ( mod 17 ) 。
由 CRT,对每个单位 a a a 都有 a 560 ≡ 1 ( m o d 561 ) a^{560}\equiv 1 \pmod{561} a 560 ≡ 1 ( mod 561 ) 。具有这种性质的合数称为卡迈克尔数 (Carmichael number)。对于这样的 n n n ,费马检验只有在碰到与 n n n 有公因子的底数时才能检测出合数性。抽到非单位的概率至多为不同素因子上的和 ∑ p ∣ n 1 / p \sum\limits_{p\mid n}1/p p ∣ n ∑ 1/ p ;素因子的个数也有影响。
因此,我们需要从底数 a a a 获得比单个值 a n − 1 a^{n-1} a n − 1 更多的信息。
1 的平方根
额外的信息来自下面的引理。
设 p p p 为奇素数,x x x 为整数且 x 2 ≡ 1 ( m o d p ) x^2\equiv 1 \pmod p x 2 ≡ 1 ( mod p ) 。则 x ≡ 1 x\equiv 1 x ≡ 1 或 x ≡ − 1 ( m o d p ) x \equiv -1 \pmod p x ≡ − 1 ( mod p ) 。
我们有 p ∣ x 2 − 1 = ( x − 1 ) ( x + 1 ) p \mid x^2-1 = (x-1)(x+1) p ∣ x 2 − 1 = ( x − 1 ) ( x + 1 ) 。由于 p p p 是素数,故 p ∣ x − 1 p\mid x-1 p ∣ x − 1 或 p ∣ x + 1 p \mid x+1 p ∣ x + 1 。
该证明恰好只用到了 p p p 的一条性质:若素数整除一个乘积,则它整除其中某个因子。对于合数模,这条性质不成立。引理的失效随即暴露出 n n n 的一个因子。
引理 8.1.4
(1 1 1 的非平凡平方根暴露因子)
设 n ≥ 3 n\ge 3 n ≥ 3 ,且 x 2 ≡ 1 ( m o d n ) x^2\equiv 1 \pmod n x 2 ≡ 1 ( mod n ) 但 x ≢ ± 1 ( m o d n ) x\not\equiv \pm 1 \pmod n x ≡ ± 1 ( mod n ) 。则 gcd ( x − 1 , n ) \gcd(x-1,n) g cd( x − 1 , n ) 与 gcd ( x + 1 , n ) \gcd(x+1,n) g cd( x + 1 , n ) 都是 n n n 的真因子,即都严格介于 1 1 1 与 n n n 之间。
由于 n ∣ ( x − 1 ) ( x + 1 ) n \mid (x-1)(x+1) n ∣ ( x − 1 ) ( x + 1 ) 且 n ∤ x − 1 n\nmid x-1 n ∤ x − 1 ,故 gcd ( x − 1 , n ) ≠ n \gcd(x-1,n)\neq n g cd( x − 1 , n ) = n 。若 gcd ( x − 1 , n ) = 1 \gcd(x-1,n)=1 g cd( x − 1 , n ) = 1 ,则由 n ∣ ( x − 1 ) ( x + 1 ) n \mid (x-1)(x+1) n ∣ ( x − 1 ) ( x + 1 ) 可得 n ∣ x + 1 n\mid x+1 n ∣ x + 1 ,这与 x ≢ − 1 x\not\equiv -1 x ≡ − 1 矛盾。因此 1 < gcd ( x − 1 , n ) < n 1 < \gcd(x-1,n) < n 1 < g cd( x − 1 , n ) < n 。交换 x − 1 x-1 x − 1 与 x + 1 x+1 x + 1 的角色,同样的论证给出 1 < gcd ( x + 1 , n ) < n 1<\gcd(x+1,n)<n 1 < g cd( x + 1 , n ) < n 。
我们把这样的 x x x 称为模 n n n 的 1 1 1 的非平凡平方根 。由素数模下 1 1 1 的平方根的引理,素数模下不存在这样的根。对于至少有两个不同素因子的奇合数模,则总存在非平凡平方根,下面关于 1 1 1 的平方根的练习将说明这一点。
定义
设 n ≥ 3 n\ge 3 n ≥ 3 为奇数。此时 n − 1 n-1 n − 1 为偶数,故可唯一地写成
n − 1 = 2 s d , s ≥ 1 , d 为奇数 . n - 1 = 2^s d, \qquad s \ge 1,\quad d \text{ 为奇数}. n − 1 = 2 s d , s ≥ 1 , d 为奇数 .
对于整数 a a a ,a a a 模 n n n 的强序列 为
x r ≡ a 2 r d ( m o d n ) , r = 0 , 1 , … , s . x_r \equiv a^{2^r d} \pmod n, \qquad r = 0,1,\dots,s. x r ≡ a 2 r d ( mod n ) , r = 0 , 1 , … , s . 每一项都是前一项的平方:x r + 1 ≡ x r 2 x_{r+1}\equiv x_r^2 x r + 1 ≡ x r 2 。最后一项是费马值,x s ≡ a n − 1 x_s \equiv a^{n-1} x s ≡ a n − 1 。我们把下标 r r r 称为阶段 。
若 n n n 为素数且 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 ,则序列终止于 x s ≡ 1 x_s \equiv 1 x s ≡ 1 。考察值 1 1 1 首次出现的阶段。要么它出现在阶段 0 0 0 ,要么前一项的平方为 1 1 1 而前一项本身不是 1 1 1 ,于是由素数模下 1 1 1 的平方根的引理,前一项为 − 1 -1 − 1 。这启发了如下定义。
设 n ≥ 3 n\ge 3 n ≥ 3 为奇数,n − 1 = 2 s d n-1=2^s d n − 1 = 2 s d ,d d d 为奇数,底数 a ∈ { 1 , … , n − 1 } a\in\{1,\dots,n-1\} a ∈ { 1 , … , n − 1 } 。若 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 且
a d ≡ 1 ( m o d n ) 或 a 2 r d ≡ − 1 ( m o d n ) 对某个满足 0 ≤ r ≤ s − 1 的 r , a^{d}\equiv 1 \pmod n \qquad\text{或}\qquad a^{2^r d}\equiv -1 \pmod n \ \text{ 对某个满足 } 0\le r\le s-1 \text{ 的 } r, a d ≡ 1 ( mod n ) 或 a 2 r d ≡ − 1 ( mod n ) 对某个满足 0 ≤ r ≤ s − 1 的 r , 则称整数 a a a 使 n n n 成为以 a a a 为底的强概率素数 。此时我们也说 a a a 通过 。若 n n n 为合数且 a a a 通过,则 a a a 是 n n n 的强说谎者 。若 a a a 不通过,则 a a a 是 n n n 合数性的强证据 。
这个定义有三点值得说明。
检查哪些阶段。 在阶段 0 0 0 ,我们接受值 1 1 1 或 − 1 -1 − 1 。在阶段 1 , … , s − 1 1,\dots,s-1 1 , … , s − 1 ,我们只接受值 − 1 -1 − 1 。在阶段 r ≥ 1 r\ge 1 r ≥ 1 出现值 1 1 1 本身并不足以接受,因为关键在于值 1 1 1 是如何得到的。若 1 1 1 在阶段 r r r 首次出现且本轮尚未停止,则前一项既不是 1 1 1 也不是 − 1 -1 − 1 ,所以它是 1 1 1 的非平凡平方根,n n n 为合数。若 1 1 1 已在更早阶段出现,本轮则早已接受或拒绝。
阶段 s s s 从不是接受阶段。 阶段 s s s 的值 − 1 -1 − 1 意味着 a n − 1 ≡ − 1 a^{n-1}\equiv -1 a n − 1 ≡ − 1 。对素数 n n n 而言,这与费马定理不相容,因为当 n ≥ 3 n\ge 3 n ≥ 3 时 − 1 ≢ 1 -1\not\equiv 1 − 1 ≡ 1 。所以定义只取到 r ≤ s − 1 r\le s-1 r ≤ s − 1 。
条件只依赖于 a a a 模 n n n 的值。 因此我们把底数视为剩余类,并从 { 1 , 2 , … , n − 1 } \{1,2,\dots,n-1\} { 1 , 2 , … , n − 1 } 中选取。剩余类 0 0 0 被排除,因为它永远不与 n n n 互素。
底数 1 1 1 与 n − 1 n-1 n − 1 总是通过:1 d = 1 1^d = 1 1 d = 1 ,且因 d d d 为奇数,( n − 1 ) d ≡ ( − 1 ) d = − 1 (n-1)^d\equiv(-1)^d = -1 ( n − 1 ) d ≡ ( − 1 ) d = − 1 。它们是不携带任何信息的通过底数。配套章节证明的误差界是在存在这些底数的情况下得到的。
快速检查
(证明:对 n = 2047 = 23 ⋅ 89 n=2047=23\cdot89 n = 2047 = 23 ⋅ 89 ,底数 2 2 2 通过,所以 2 2 2 是 2047 2047 2047 的强说谎者。)
注意 2 11 = 2048 2^{11}=2048 2 11 = 2048 。
解答 · 答案 此时 n − 1 = 2046 = 2 ⋅ 1023 n-1=2046=2\cdot1023 n − 1 = 2046 = 2 ⋅ 1023 ,故 s = 1 s=1 s = 1 ,d = 1023 = 11 ⋅ 93 d=1023=11\cdot93 d = 1023 = 11 ⋅ 93 。由于 2 11 = 2048 ≡ 1 ( m o d 2047 ) 2^{11}=2048\equiv1\pmod{2047} 2 11 = 2048 ≡ 1 ( mod 2047 ) ,得 2 1023 = ( 2 11 ) 93 ≡ 1 2^{1023}=(2^{11})^{93}\equiv1 2 1023 = ( 2 11 ) 93 ≡ 1 。因此 a d ≡ 1 a^d\equiv1 a d ≡ 1 ,尽管 2047 2047 2047 是合数,2 2 2 仍在阶段 0 0 0 通过。
算法
伪代码
该检验以整数 n ≥ 2 n\ge 2 n ≥ 2 和轮数 k ≥ 1 k\ge 1 k ≥ 1 为输入,返回三种判定之一。
PRIME 仅对 n = 2 n=2 n = 2 返回,且是确定的。
COMPOSITE 总是正确的。
PROBABLE-PRIME 是我们必须分析其可靠性的判定。
MILLER-RABIN(n, k): # n ≥ 2, k ≥ 1
1 if n = 2: return PRIME
2 if n is even: return COMPOSITE # n ≥ 4 为偶数,故 2 是真因子
3 d ← n − 1; s ← 0
4 while d is even:
5 d ← d / 2; s ← s + 1
# 现在 n − 1 = 2^s · d,其中 d 为奇数且 s ≥ 1
6 repeat k times:
7 draw a uniformly at random from 1, 2, ..., n − 1,
independently of all previous draws
8 if STRONG-ROUND(n, s, d, a) = FAIL: return COMPOSITE
9 return PROBABLE-PRIME
STRONG-ROUND(n, s, d, a):
1 if gcd(a, n) > 1: return FAIL # gcd(a, n) 是 n 的真因子
2 x ← a^d mod n # 平方–乘算法;这是 x_0
3 if x = 1 or x = n − 1: return PASS # 阶段 0
4 for r ← 1 to s − 1:
5 y ← x^2 mod n # y = x_r
6 if y = n − 1: return PASS # 阶段 r
7 if y = 1: return FAIL # x 是 1 的平方根,且不是 ±1
8 x ← y
9 return FAIL
有几个细节值得详细说明。
n = 2 n=2 n = 2 与偶数 n n n 的情形。 分解 n − 1 = 2 s d n-1=2^s d n − 1 = 2 s d (s ≥ 1 s\ge 1 s ≥ 1 )要求 n n n 为奇数。对于偶数 n n n ,数 n − 1 n-1 n − 1 是奇数,故 s = 0 s=0 s = 0 ,强条件中没有可以接受 − 1 -1 − 1 的阶段。这个定义并非为这种情形设计,我们直接处理:2 2 2 是素数,而每个偶数 n ≥ 4 n\ge 4 n ≥ 4 都是合数,因为 2 2 2 是其真因子。
n = 3 n=3 n = 3 的情形。 此时 n − 1 = 2 n-1=2 n − 1 = 2 ,故 s = 1 s=1 s = 1 ,d = 1 d=1 d = 1 。该轮中第 4–8 行的循环让 r r r 从 1 1 1 取到 0 0 0 ,因此根本不执行。底数为 1 1 1 和 2 2 2 ,二者都在阶段 0 0 0 通过。这是正确的,因为 3 3 3 是素数。
抽取底数。 从 { 1 , … , n − 1 } \{1,\dots,n-1\} { 1 , … , n − 1 } 中均匀抽取 a a a 的一种方法是拒绝采样。抽取 β \beta β 个新的随机比特,其中 β \beta β 为 n n n 的比特长度。将它们解释为整数 t t t ,0 ≤ t ≤ 2 β − 1 0\le t\le 2^\beta-1 0 ≤ t ≤ 2 β − 1 。若 1 ≤ t ≤ n − 1 1\le t\le n-1 1 ≤ t ≤ n − 1 ,则接受 a = t a=t a = t ,否则重新抽取。由于奇数 n ≥ 3 n\ge3 n ≥ 3 满足 n − 1 ≥ 2 β − 1 n-1\ge2^{\beta-1} n − 1 ≥ 2 β − 1 ,每次尝试成功的概率至少为 1 / 2 1/2 1/2 ,期望尝试次数至多为 2 2 2 。对分析而言,重要的是底数在 { 1 , … , n − 1 } \{1,\dots,n-1\} { 1 , … , n − 1 } 上恰好是均匀的,并且每一轮使用新的随机比特。
gcd 步骤。 该轮的第 1 行对正确性并非必需,因为与 n n n 不互素的底数,其任何幂都不可能模 n n n 同余于 1 1 1 或 − 1 -1 − 1 。加入它是因为一旦触发,它能廉价地给出 n n n 的一个显式因子。但这并不是检验之所以“强”的原因。抽到非单位的概率至多为不同素因子上的和 ∑ p ∣ n 1 / p \sum\limits_{p\mid n}1/p p ∣ n ∑ 1/ p 。当此和很小时,检测合数性主要依靠强条件。
该轮恰好计算强条件
该轮的第 7 行会提前终止,因此我们应当检查这一轮判定的恰好是强条件。
设 n ≥ 3 n\ge 3 n ≥ 3 为奇数,n − 1 = 2 s d n-1=2^sd n − 1 = 2 s d (d d d 为奇数),a ∈ { 1 , … , n − 1 } a\in\{1,\dots,n-1\} a ∈ { 1 , … , n − 1 } 。则 STRONG-ROUND( n , s , d , a ) (n,s,d,a) ( n , s , d , a ) 返回 PASS 当且仅当 a a a 使 n n n 成为以 a a a 为底的强概率素数。
若 gcd ( a , n ) > 1 \gcd(a,n)>1 g cd( a , n ) > 1 ,则该轮返回 FAIL,而定义也不成立。因此假设 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 。
第 2 行令 x = x 0 x = x_0 x = x 0 。若 x 0 ∈ { 1 , n − 1 } x_0\in\{1,n-1\} x 0 ∈ { 1 , n − 1 } ,则该轮与定义都接受。
否则,我们证明如下循环不变量:在第 r r r 次迭代开始时,变量 x x x 保存 x r − 1 x_{r-1} x r − 1 ,且 x 0 , … , x r − 1 x_0,\dots,x_{r-1} x 0 , … , x r − 1 中没有一个同余于 1 1 1 或 − 1 -1 − 1 。 由上一段,这在 r = 1 r=1 r = 1 时成立。在第 r r r 次迭代中,变量 y y y 变为 x r x_r x r ,分三种情形。
若 x r ≡ − 1 x_r\equiv -1 x r ≡ − 1 ,则该轮返回 PASS,而定义在阶段 r ≤ s − 1 r\le s-1 r ≤ s − 1 接受。
若 x r ≡ 1 x_r\equiv 1 x r ≡ 1 ,则该轮返回 FAIL。我们验证定义同样拒绝。我们知道 x 0 ≢ 1 x_0\not\equiv 1 x 0 ≡ 1 且 x 0 , … , x r − 1 ≢ − 1 x_0,\dots,x_{r-1}\not\equiv -1 x 0 , … , x r − 1 ≡ − 1 。由于 x r ≡ 1 x_r\equiv 1 x r ≡ 1 ,对所有 t ≥ r t\ge r t ≥ r 都有 x t ≡ 1 x_t\equiv 1 x t ≡ 1 ,而因 n ≥ 3 n\ge 3 n ≥ 3 ,1 ≢ − 1 1\not\equiv -1 1 ≡ − 1 。所以阶段 0 , … , s − 1 0,\dots,s-1 0 , … , s − 1 中没有一项等于 − 1 -1 − 1 ,定义拒绝。
否则 x r ≢ ± 1 x_r\not\equiv\pm1 x r ≡ ± 1 。该轮令 x ← x r x\leftarrow x_r x ← x r ,不变量对 r + 1 r+1 r + 1 成立。
若循环结束,则由不变量知 x 0 , … , x s − 1 x_0,\dots,x_{s-1} x 0 , … , x s − 1 都不同于 ± 1 \pm1 ± 1 ,所以定义拒绝。该轮在第 9 行同样拒绝。
解读失败的一轮
FAIL 不仅仅是一个否定的判定。它总是伴随着 n n n 为合数的证据,共有三类。
公因子。 gcd 步骤触发,且 g = gcd ( a , n ) g=\gcd(a,n) g = g cd( a , n ) 满足 1 < g ≤ a < n 1<g\le a<n 1 < g ≤ a < n 。所以 g g g 是 n n n 的真因子。
1 的非平凡平方根。 第 7 行触发。此时 x ≡ x r − 1 x\equiv x_{r-1} x ≡ x r − 1 满足 x 2 ≡ 1 x^2\equiv 1 x 2 ≡ 1 且 x ≢ ± 1 x\not\equiv\pm 1 x ≡ ± 1 。由非平凡平方根的引理,gcd ( x − 1 , n ) \gcd(x-1,n) g cd( x − 1 , n ) 是真因子。
在第 9 行耗尽。 我们知道 x s − 1 ≢ ± 1 x_{s-1}\not\equiv \pm 1 x s − 1 ≡ ± 1 。考虑该轮从未计算的那一项,x s ≡ x s − 1 2 ≡ a n − 1 x_s\equiv x_{s-1}^2\equiv a^{n-1} x s ≡ x s − 1 2 ≡ a n − 1 。要么 x s ≢ 1 x_s\not\equiv 1 x s ≡ 1 ,此时 a a a 是费马证据,由费马定理知 n n n 为合数;要么 x s ≡ 1 x_s\equiv 1 x s ≡ 1 ,此时 x s − 1 x_{s-1} x s − 1 是 1 1 1 的非平凡平方根。
在情形 1、情形 2,以及情形 3 中 x s ≡ 1 x_s\equiv 1 x s ≡ 1 的子情形,我们甚至能得到 n n n 的一个真因子。当 s = 1 s=1 s = 1 时,循环为空,每个与 n n n 互素的底数所对应的 FAIL 都属于类型 3,完全由值 x 0 x_0 x 0 决定。
任何人都可以用一次模幂运算或一次 gcd 运算来重新核验这些证书中的任何一个。因此 COMPOSITE 判定不仅仅是概率性的,而是被证明了的,其证明就是那个失败的底数。
快速检查
(对 n = 21 n=21 n = 21 与 a = 8 a=8 a = 8 执行强检验的一轮。出现哪一种失败?它暴露了 21 21 21 的哪些因子?)
写出 20 = 2 2 ⋅ 5 20=2^2\cdot5 20 = 2 2 ⋅ 5 ,并先计算 8 2 8^2 8 2 。
解答 · 答案 此时 s = 2 s=2 s = 2 ,d = 5 d=5 d = 5 ,且 gcd ( 8 , 21 ) = 1 \gcd(8,21)=1 g cd( 8 , 21 ) = 1 。由于 8 2 = 64 = 3 ⋅ 21 + 1 ≡ 1 8^2=64=3\cdot21+1\equiv1 8 2 = 64 = 3 ⋅ 21 + 1 ≡ 1 ,得 x 0 = 8 5 = 8 ( 8 2 ) 2 ≡ 8 x_0=8^5=8\,(8^2)^2\equiv8 x 0 = 8 5 = 8 ( 8 2 ) 2 ≡ 8 ,它既不是 1 1 1 也不是 20 20 20 。在迭代 r = 1 r=1 r = 1 中 y = 8 2 ≡ 1 y=8^2\equiv1 y = 8 2 ≡ 1 ,所以第 7 行返回 FAIL。这是类型 2 的失败:x = 8 x=8 x = 8 是 1 1 1 的平方根且不是 ± 1 \pm1 ± 1 ,而 gcd ( 8 − 1 , 21 ) = 7 \gcd(8-1,21)=7 g cd( 8 − 1 , 21 ) = 7 ,gcd ( 8 + 1 , 21 ) = 3 \gcd(8+1,21)=3 g cd( 8 + 1 , 21 ) = 3 。
用尽检查阶段后的两种解释
跟踪两个简短轮次中的变量,就能看清上述失败类型 3 的两种可能。两例中的最大公因子都是 1 1 1 ,因此拒绝来自强条件,而非开头找到了公因子。
例题 8.1.8
(用尽检查阶段:n = 9 n=9 n = 9 ,底数为 2 2 2 )
写 9 − 1 = 8 = 2 3 ⋅ 1 9-1=8=2^3\cdot1 9 − 1 = 8 = 2 3 ⋅ 1 ,所以 s = 3 s=3 s = 3 ,d = 1 d=1 d = 1 。由于 gcd ( 2 , 9 ) = 1 \gcd(2,9)=1 g cd( 2 , 9 ) = 1 ,第 2 行给出 x 0 = 2 x_0=2 x 0 = 2 。它既不是 1 1 1 也不是 8 8 8 ,第 3 行不接受。在 r = 1 r=1 r = 1 时,计算 x 1 = 2 2 m o d 9 = 4 x_1=2^2\bmod9=4 x 1 = 2 2 mod 9 = 4 ;它既不是 8 8 8 也不是 1 1 1 ,所以循环以 x = 4 x=4 x = 4 继续。在 r = 2 r=2 r = 2 时得到 x 2 = 4 2 m o d 9 = 7 x_2=4^2\bmod9=7 x 2 = 4 2 mod 9 = 7 ,仍既不是 8 8 8 也不是 1 1 1 。已无更多待检查的阶段,第 9 行返回 FAIL。
为了解释失败,再计算额外的值 x 3 = 7 2 m o d 9 = 4 x_3=7^2\bmod9=4 x 3 = 7 2 mod 9 = 4 。该轮本身并不执行这最后一次平方。它说明 2 8 ≢ 1 ( m o d 9 ) 2^8\not\equiv1\pmod9 2 8 ≡ 1 ( mod 9 ) ,所以底数 2 2 2 已经是费马证据。这条轨迹中没有出现 1 1 1 的非平凡平方根:该轮因用尽允许检查的阶段而拒绝,并非第 7 行检测到了这样的根。
例题 8.1.9
(空循环仍能检测费马说谎者:n = 15 n=15 n = 15 ,底数为 4 4 4 )
此时 15 − 1 = 14 = 2 ⋅ 7 15-1=14=2\cdot7 15 − 1 = 14 = 2 ⋅ 7 ,所以 s = 1 s=1 s = 1 ,d = 7 d=7 d = 7 。由于 gcd ( 4 , 15 ) = 1 \gcd(4,15)=1 g cd( 4 , 15 ) = 1 ,底数是一个单位。又因 4 2 = 16 ≡ 1 ( m o d 15 ) 4^2=16\equiv1\pmod{15} 4 2 = 16 ≡ 1 ( mod 15 ) ,
x 0 = 4 7 = 4 ( 4 2 ) 3 ≡ 4 ( m o d 15 ) . x_0=4^7=4(4^2)^3\equiv4\pmod{15}. x 0 = 4 7 = 4 ( 4 2 ) 3 ≡ 4 ( mod 15 ) . 初始值既不是 1 1 1 也不是 14 14 14 。循环的范围从 r = 1 r=1 r = 1 到 s − 1 = 0 s-1=0 s − 1 = 0 ,因此不执行任何迭代,第 9 行返回 FAIL。然而,费马值为 4 14 = ( 4 2 ) 7 ≡ 1 ( m o d 15 ) 4^{14}=(4^2)^7\equiv1\pmod{15} 4 14 = ( 4 2 ) 7 ≡ 1 ( mod 15 ) 。因此,末项为 1 1 1 并不足以满足强条件:它的前一项 4 4 4 是 1 1 1 的非平凡平方根。非平凡平方根的引理把证书具体化为
gcd ( 4 − 1 , 15 ) = 3 , gcd ( 4 + 1 , 15 ) = 5. \gcd(4-1,15)=3,\qquad \gcd(4+1,15)=5. g cd( 4 − 1 , 15 ) = 3 , g cd( 4 + 1 , 15 ) = 5. 这是失败类型 3 中的第二种可能。尽管第 7 行根本未执行,变量 x x x 已保存的值仍给出了平方根,进而给出因数分解。相比之下,底数 14 14 14 因 14 7 ≡ − 1 ( m o d 15 ) 14^7\equiv-1\pmod{15} 1 4 7 ≡ − 1 ( mod 15 ) 而立即通过;这一个通过的底数并不能证明 15 15 15 为素数。
定理/命题
设 n n n 为奇素数,a ∈ { 1 , … , n − 1 } a\in\{1,\dots,n-1\} a ∈ { 1 , … , n − 1 } 。则 a a a 通过。因此,对每个奇素数 n n n 和随机抽取的每一种结果,MILLER-RABIN( n , k ) (n,k) ( n , k ) 都返回 PROBABLE-PRIME。对 n = 2 n=2 n = 2 它返回 PRIME。
由于 1 ≤ a ≤ n − 1 1\le a\le n-1 1 ≤ a ≤ n − 1 且 n n n 为素数,故 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 。由费马小定理,x s ≡ a n − 1 ≡ 1 ( m o d n ) x_s\equiv a^{n-1}\equiv 1 \pmod n x s ≡ a n − 1 ≡ 1 ( mod n ) 。所以使 x r ≡ 1 x_r\equiv 1 x r ≡ 1 的阶段 r r r 构成的集合非空。设 r 0 r_0 r 0 为其最小元。
若 r 0 = 0 r_0 = 0 r 0 = 0 ,则 a d ≡ 1 a^d\equiv 1 a d ≡ 1 ,a a a 通过。
若 r 0 ≥ 1 r_0\ge 1 r 0 ≥ 1 ,则 x r 0 − 1 2 ≡ x r 0 ≡ 1 x_{r_0-1}^2\equiv x_{r_0}\equiv 1 x r 0 − 1 2 ≡ x r 0 ≡ 1 ,且由最小性 x r 0 − 1 ≢ 1 x_{r_0-1}\not\equiv 1 x r 0 − 1 ≡ 1 。由素数模下 1 1 1 的平方根的引理,x r 0 − 1 ≡ − 1 x_{r_0-1}\equiv -1 x r 0 − 1 ≡ − 1 。阶段 r 0 − 1 r_0-1 r 0 − 1 介于 0 0 0 与 s − 1 s-1 s − 1 之间,所以 a a a 通过。
由于该轮判定的正是强条件,每一轮都返回 PASS,因此算法到达第 9 行并返回 PROBABLE-PRIME。n = 2 n=2 n = 2 的情形在第 1 行处理。
证明透视
素数总是通过的证明中各要素的作用 证明用到三个事实,每个恰好用一次。费马小定理保证值 1 1 1 出现在强序列中,最迟在阶段 s s s ;它需要 gcd ( a , n ) = 1 \gcd(a,n)=1 g cd( a , n ) = 1 ,而对素数 n n n ,这由 1 ≤ a ≤ n − 1 1\le a\le n-1 1 ≤ a ≤ n − 1 得出。若没有这次出现,最小阶段 r 0 r_0 r 0 便不存在。
关键一步是取 r 0 r_0 r 0 为最小。最小性提供前一项 x r 0 − 1 x_{r_0-1} x r 0 − 1 ,它的平方为 1 1 1 而它本身不是 1 1 1 。素性只在这里介入:素数模下 1 1 1 的平方根的引理迫使这个前一项等于 − 1 -1 − 1 。由于 r 0 ≤ s r_0\le s r 0 ≤ s ,接受阶段 r 0 − 1 r_0-1 r 0 − 1 落在 { 0 , … , s − 1 } \{0,\dots,s-1\} { 0 , … , s − 1 } 之内,这正是阶段 s s s 从不需要检查的原因。
对合数模,论证恰好在该引理处失效。对 n = 15 n=15 n = 15 与 a = 4 a=4 a = 4 ,第一个 1 1 1 出现在 r 0 = 1 r_0=1 r 0 = 1 ,但它的前一项 x 0 = 4 x_0=4 x 0 = 4 是 1 1 1 的平方根而不是 ± 1 \pm1 ± 1 ;尽管 4 14 ≡ 1 4^{14}\equiv1 4 14 ≡ 1 ,这个底数仍不通过。证明既没有用到 gcd 步骤,也没有用到随机抽取:结论对每个底数都成立。
因此该检验具有单侧误差 。它从不把素数判为合数。每一种可能的错误都是把合数报告为概率素数。配套章节证明了这种情况可能发生的频率。
常见错误
反例模式
卡迈克尔数的费马说谎者不一定是强说谎者 一个看似合理的说法是:强检验只是重新安排 a n − 1 a^{n-1} a n − 1 的计算,所以对卡迈克尔数,每个单位既然都是费马说谎者,也就都是强说谎者。取 n = 561 n=561 n = 561 ,于是 s = 4 s=4 s = 4 ,d = 35 d=35 d = 35 ,并取底数 a = 5 a=5 a = 5 。反复平方得
x 0 ≡ 23 , x 1 ≡ 529 , x 2 ≡ 463 , x 3 ≡ 67 , x 4 ≡ 1 ( m o d 561 ) . x_0\equiv23,\quad x_1\equiv529,\quad x_2\equiv463,\quad x_3\equiv67,\quad x_4\equiv1 \pmod{561}. x 0 ≡ 23 , x 1 ≡ 529 , x 2 ≡ 463 , x 3 ≡ 67 , x 4 ≡ 1 ( mod 561 ) . 确实 67 2 = 4489 = 8 ⋅ 561 + 1 67^2=4489=8\cdot561+1 6 7 2 = 4489 = 8 ⋅ 561 + 1 。所以 5 5 5 是费马说谎者,但被检查的值 x 0 , … , x 3 x_0,\dots,x_3 x 0 , … , x 3 中没有一个是 1 1 1 或 560 560 560 ,该轮在第 9 行失败。这是 x s ≡ 1 x_s\equiv1 x s ≡ 1 的失败类型 3:67 67 67 是 1 1 1 的非平凡平方根,且 gcd ( 66 , 561 ) = 33 \gcd(66,561)=33 g cd( 66 , 561 ) = 33 ,gcd ( 68 , 561 ) = 17 \gcd(68,561)=17 g cd( 68 , 561 ) = 17 。正确的说法是:强条件严格强于费马条件,它考察通向 a n − 1 a^{n-1} a n − 1 的路径,而不仅仅是终点。
低于 2 − k 2^{-k} 2 − k 的界要求底数针对给定输入独立且均匀地抽取。固定的一组底数对某个特定合数并没有这样的保证。对 n = 2047 = 23 ⋅ 89 n=2047=23\cdot89 n = 2047 = 23 ⋅ 89 ,如上面的快速检查所示,底数 2 2 2 通过,所以无论重复底数 2 2 2 多少次,每次都返回 PROBABLE-PRIME。换一个底数仍可揭穿 2047 2047 2047 :3 1023 ≡ 1565 ( m o d 2047 ) 3^{1023}\equiv1565\pmod{2047} 3 1023 ≡ 1565 ( mod 2047 ) ,既不是 1 1 1 也不是 2046 2046 2046 ,而 s = 1 s=1 s = 1 ,所以以 3 3 3 为底的一轮失败。
练习
快速检查
(1 的平方根与两种失败:设 n n n 为奇数,n ≥ 3 n\ge3 n ≥ 3 。)
(a) 证明:若 n = p e n=p^e n = p e ,其中 p p p 为奇素数且 e ≥ 1 e\ge 1 e ≥ 1 ,则 x 2 ≡ 1 ( m o d p e ) x^2\equiv1\pmod{p^e} x 2 ≡ 1 ( mod p e ) 的解只有 x ≡ ± 1 x\equiv\pm1 x ≡ ± 1 。
(b) 证明:若 n n n 恰有 ω \omega ω 个不同的素因子,则 x 2 ≡ 1 ( m o d n ) x^2\equiv1\pmod n x 2 ≡ 1 ( mod n ) 模 n n n 恰有 2 ω 2^\omega 2 ω 个解。由此推出:1 1 1 的非平凡平方根存在当且仅当 ω ≥ 2 \omega\ge2 ω ≥ 2 。
(c) 证明:若 n n n 为奇素数幂,且互素底数 a a a 使强检验这一轮失败,则 a a a 是费马证据:a n − 1 ≢ 1 a^{n-1}\not\equiv1 a n − 1 ≡ 1 。对 n = 9 n=9 n = 9 ,a = 2 a=2 a = 2 验证这一点。
(d) 证明:若 x x x 是奇合数 n n n 模下 1 1 1 的非平凡平方根,则 x x x 是费马说谎者但是强证据。指出它属于“解读失败的一轮”中的哪一种失败类型。
解答 (a) 设 p e ∣ ( x − 1 ) ( x + 1 ) p^e\mid(x-1)(x+1) p e ∣ ( x − 1 ) ( x + 1 ) 。若 p p p 同时整除两个因子,则它整除两者之差 2 2 2 ,这对奇数 p p p 是不可能的。所以 p p p 只整除其中一个因子,于是整个幂 p e p^e p e 必须整除该因子。因此 x ≡ 1 x\equiv1 x ≡ 1 或 x ≡ − 1 ( m o d p e ) x\equiv-1\pmod{p^e} x ≡ − 1 ( mod p e ) ,且由于 p e ≥ 3 p^e\ge3 p e ≥ 3 ,这两个解是不同的。
(b) 记 n = ∏ i = 1 ω p i e i n=\prod\limits_{i=1}^{\omega}p_i^{e_i} n = i = 1 ∏ ω p i e i 。由 CRT,x 2 ≡ 1 ( m o d n ) x^2\equiv1\pmod n x 2 ≡ 1 ( mod n ) 当且仅当对每个 i i i 都有 x 2 ≡ 1 ( m o d p i e i ) x^2\equiv1\pmod{p_i^{e_i}} x 2 ≡ 1 ( mod p i e i ) 。由 (a),每个分量恰有 2 2 2 个解,而 CRT 给出解的元组与模 n n n 的解之间的一一对应。所以共有 2 ω 2^\omega 2 ω 个解。因为 ± 1 \pm1 ± 1 是其中两个,所以非平凡解存在当且仅当 2 ω > 2 2^\omega>2 2 ω > 2 ,即 ω ≥ 2 \omega\ge2 ω ≥ 2 。
(c) 由失败轮次的分类,失败的互素底数要么有 a n − 1 ≢ 1 a^{n-1}\not\equiv1 a n − 1 ≡ 1 ,要么产生模 n n n 的 1 1 1 的非平凡平方根。对 n = p e n=p^e n = p e ,(a) 排除了第二种可能。对 n = 9 n=9 n = 9 与 a = 2 a=2 a = 2 ,强序列为 2 , 4 , 7 2,4,7 2 , 4 , 7 ,随后 a 8 ≡ 7 2 = 49 ≡ 4 ≠ 1 a^8\equiv7^2=49\equiv4\ne1 a 8 ≡ 7 2 = 49 ≡ 4 = 1 ,所以 2 2 2 是费马证据。
(d) 由于 x 2 ≡ 1 x^2\equiv1 x 2 ≡ 1 且 n − 1 n-1 n − 1 为偶数,x n − 1 = ( x 2 ) ( n − 1 ) / 2 ≡ 1 x^{n-1}=(x^2)^{(n-1)/2}\equiv1 x n − 1 = ( x 2 ) ( n − 1 ) /2 ≡ 1 ,所以 x x x 是费马说谎者。由于 d d d 为奇数,x d = x ⋅ ( x 2 ) ( d − 1 ) / 2 ≡ x x^d=x\cdot(x^2)^{(d-1)/2}\equiv x x d = x ⋅ ( x 2 ) ( d − 1 ) /2 ≡ x ,它不是 ± 1 \pm1 ± 1 。所以 x x x 在阶段 0 0 0 不通过。随后 x 1 ≡ x 2 ≡ 1 x_1\equiv x^2\equiv1 x 1 ≡ x 2 ≡ 1 ,故对所有 r ≥ 1 r\ge1 r ≥ 1 都有 x r ≡ 1 x_r\equiv 1 x r ≡ 1 ,− 1 -1 − 1 从不出现。
若 s ≥ 2 s\ge2 s ≥ 2 ,该轮在迭代 r = 1 r=1 r = 1 的第 7 行失败。这是类型 2,证书就是 x x x 本身。
若 s = 1 s=1 s = 1 ,该轮在第 9 行失败。这是 x s ≡ 1 x_s\equiv1 x s ≡ 1 的类型 3,所以 x s − 1 = x x_{s-1}=x x s − 1 = x 仍是那个非平凡根。
n = 15 n=15 n = 15 的底数 4 4 4 和 11 11 11 ,以及 n = 21 n=21 n = 21 的底数 8 8 8 和 13 13 13 ,都是实例。