第 12 章：重试、运行时间与RSA结论的范围

返回目录

12.1 失败以后重试为什么有效

每次失败后重新独立、均匀选择底数，就得到新的一次尝试。若每次失败概率至多 $1/2$ ，独立重复 $k$ 次都失败的概率至多

$\left(\frac12\right)^k=2^{-k}.$

“独立重复”不能省略。若一直重复同一个失败底数，后续计算完全一样，重复次数增加不会改善成功率。重新抽样让前一次的失败不改变下一次的分布。

算法输出的因子始终可以验证，因此随机性影响的是需要尝试多少次，不影响成功输出是否正确。有限次全失败时，可以继续尝试；它不构成错误的分解结果。

12.2 为什么平均至多两次，不等于两次必成功

设单次成功率为 $\rho\ge1/2$ ，令 $N$ 为第一次成功时的尝试总次数。第 $k$ 次恰好第一次成功，需要前 $k-1$ 次失败、第 $k$ 次成功，所以 $P(N=k)=(1-\rho)^{k-1}\rho$ 。

期望 $E[N]$ 表示大量独立运行中尝试次数的平均值。其值为 $1/\rho\le2$ 。这个求和也可以从“第 $j+1$ 轮是否需要做”理解：第1轮一定需要做，第2轮只有第一次失败才需要做，第3轮只有前两次都失败才需要做。因此

$E[N]=\sum_{j=0}^{\infty}P(N>j) =\sum_{j=0}^{\infty}(1-\rho)^j =\frac1\rho\le2.$

第一等式的依据是：一个恰做 $k$ 轮的运行，会在 $N>0,N>1,\ldots,N>k-1$ 这 $k$ 个条件中各被计一次。对这些轮次指标取平均，再相加，就是平均总轮数。这解释了为什么能用尾概率计算期望。

期望至多2是平均表现，不是每次最多2轮；做很多轮仍有可能，只是尾概率按几何速度减小。

12.3 为什么是期望多项式时间

每次尝试需要求最大公约数、计算 $a^r\bmod n$ 以及最多 $s$ 次平方。快速幂按照 $r$ 的二进制展开进行，使用 $O(\log r)$ 次模乘法； $s\le\log_2K$ ，所以一次尝试的运算次数是 $O(\log K)$ 量级。

再考虑每个整数运算的位复杂度：中间余数小于 $n$ ，有 $O(\log n)$ 位；模乘法与欧几里得算法都有关于这些位长的多项式时间实现。因此单轮耗时是关于 $\log n,\log K$ 的多项式。期望轮数至多2，所以期望总耗时仍为多项式。

“多项式时间”是按输入的位数衡量，不是按 $n$ 本身衡量。完整位复杂度说明保留在第17章；本节说明成功概率怎样与运行时间接起来。标准结论的依据见《Handbook of Applied Cryptography》第3章Fact 3.30及第8章Fact 8.6。

12.4 恢复私钥与从密文恢复消息为什么要区分

我们证明了两个方向：分解 $n$ 可以恢复 $d$ ；已知满足条件的私钥指数 $d$ ，可以随机分解 $n$ 。因此“恢复私钥指数”与“分解模数”具有这里证明的计算联系。

但给定 $(n,e,c)$ ，直接求出满足 $m^e\equiv c\pmod n$ 的消息，是另一种已知信息和计算任务，称为RSA反演。能还原一个密文，并不意味着已经得到一个对所有消息适用的私钥指数 $d$ 。上面的随机分解算法必须从 $d$ 构造已知的 $K=ed-1$ ，不能从“某条消息已还原”自动得到这个输入。