第 17 章：补充：精确概率、统一指数与运行时间

第11章的至少一半已经证明完了。这一章回答三个额外问题：实际概率是多少，指数条件能否再放宽，每轮计算需要多长时间。第一次理解加权上界时可以跳过这一章。

17.1 精确概率公式与最差情形

这里延续第10章的记号： $p-1=2^\alpha u$ ，再写 $q-1=2^\beta v$ ，其中 $u,v$ 为奇数， $\alpha,\beta\ge1$ 。下面算的是均匀选互质底数时的精确概率。

令 $m_0=\min(\alpha,\beta)$ 。两边有正概率的共同取值为 $0,1,\ldots,m_0$ 。代入分布，

$\begin{aligned} P(\text{失败}) &=\frac{1+\sum_{t=1}^{m_0}2^{2t-2}}{2^{\alpha+\beta}}\\ &=\frac{1+\sum_{j=0}^{m_0-1}4^j}{2^{\alpha+\beta}}\\ &=\frac{1+(4^{m_0}-1)/3}{2^{\alpha+\beta}}\\ &=\boxed{\frac{4^{m_0}+2}{3\cdot2^{\alpha+\beta}}}. \end{aligned}$

因此

$\boxed{P(\text{成功})=1-\frac{4^{m_0}+2}{3\cdot2^{\alpha+\beta}}}.$

这些是互质均匀抽样下的精确概率，不依赖 $K$ 中多出的奇因子或因子 $2$ ：前者在指数子群中作排列，后者只延长序列已经为 $1$ 的尾部。

$\alpha$	$\beta$	失败概率	成功概率
1	1	$1/2$	$1/2$
2	1	$1/4$	$3/4$
2	2	$3/8$	$5/8$
3	3	$11/32$	$21/32$
2	4	$3/32$	$29/32$

若 $\alpha=\beta=m_0$ ，失败概率为 $1/3+2/(3\cdot4^{m_0})$ ； $m_0=1$ 时为 $1/2$ ，以后严格减小。若两者不同，分母进一步乘以 $2^{|\alpha-\beta|}$ ，失败概率更小。因此最低成功概率 $1/2$ 确实在 $\alpha=\beta=1$ 达到。取 $p=3,q=7$ 即为一个实例。

17.2 卡迈克尔函数：统一周期与单个元素周期

对 $n\ge2$ ，令 $U_n$ 为互质剩余类。定义 $\lambda(n)$ 为所有 $a\in U_n$ 都满足 $a^L\equiv1$ 的最小正整数 $L$ 。

由第 4.2 节，一个 $L$ 对全部元素可用，当且仅当它被每个元素的阶整除。因此

$\lambda(n)=\operatorname{lcm}\{\operatorname{ord}_n(a):a\in U_n\},\qquad \operatorname{ord}_n(a)\mid\lambda(n)\mid\varphi(n).$

最右边整除来自每个阶均整除 $\varphi(n)$ ，所以其最小公倍数也整除。模 $8$ 时阶分别为 $1,2,2,2$ ，故 $\lambda(8)=2<4=\varphi(8)$ 。

对质数 $p$ ，原根的存在保证 $\lambda(p)=p-1$ 。对两个不同质数 $p,q$ ，中国剩余定理把 $U_{pq}$ 对应到 $U_p\times U_q$ ，并且一个幂等于 $1$ 当且仅当两个坐标都等于 $1$ ，所以

$\lambda(pq)=\operatorname{lcm}(p-1,q-1).$

充分性：该最小公倍数使两个坐标的幂都为 $1$ 。必要性：由标准中国剩余定理可选互质元素，其模 $p$ 坐标为原根、模 $q$ 坐标为 $1$ ，所以任意统一指数必须被 $p-1$ 整除；交换坐标又得 $q-1$ 整除它，因而被两者最小公倍数整除。

三种指数的区别是：阶针对一个底数， $\lambda(n)$ 针对全部互质底数的最小统一指数， $\varphi(n)$ 是互质底数个数，同时提供一个统一指数。一般 $\lambda$ 的质数幂公式及全部结构不在本篇展开。

17.3 我们真正需要的是一个正的统一指数倍数

有效指数满足

$ed\equiv1\pmod{\lambda(n)},\qquad \lambda(n)=\operatorname{lcm}(p-1,q-1).$

这个条件与 RFC 8017 第 3.2 节一致。令 $K=ed-1$ ，则 $\lambda(n)\mid K$ 。原对话使用更强的 $\varphi(n)\mid K$ ；本章的全部证明只需要较弱条件。

要求 $K>0$ 。 正整数 $e>1,d\ge1$ 可以保证这一点； $e=d=1$ 给出 $K=0$ ，无法把它写成后面所需的有限二次幂分解。它虽满足形式同余，却是公开的恒等幂运算，不能纳入这里的分解归约条件。

将 $K$ 中所有因子 $2$ 提取出来，得到唯一分解

$K=2^s r,\qquad r>0\text{ 为奇数}.$

因为 $p,q$ 为奇质数， $p-1,q-1$ 都为偶数，故 $s\ge1$ 。对任何 $a\in U_n$ ，费马小定理分别给出 $a^K\equiv1$ 模 $p$ 与模 $q$ ，再由 CRT 合并得

$a^K\equiv1\pmod n.$

算法知道的是 $K$ ，无需知道 $\lambda(n)$ 或 $\varphi(n)$ 的实际数值。

17.4 有限次失败与期望多项式时间

第 11 章已经证明互质底数的一次成功概率至少为 $1/2$ 。在全部 $1,\ldots,n-1$ 中抽样时，非互质分支直接成功；条件于互质时仍然均匀。因此全部候选的一次成功概率也至少为 $1/2$ 。

独立重复 $k$ 次仍失败的概率至多为 $2^{-k}$ 。例如 $k=20$ ，上界为 $1/1048576\approx9.54\times10^{-7}$ 。这不保证每个随机序列都成功。

无限重试的算法一旦输出就必正确，期望尝试次数至多为 $2$ ，称为 Las Vegas 型随机算法；限次版本可以在未找到因子时明确报告失败。不能把“报告失败”写成输出一个未经验证的因子。

复杂度按输入位数计算。反复除以 $2$ 最多进行 $O(\log K)$ 次，快速幂需要 $O(\log r)$ 次模乘，连续平方最多 $s\le\lfloor\log_2K\rfloor$ 次；gcd 和整数运算均可在输入位数的多项式时间完成。期望总时间因此是 $\log n+\log e+\log d$ 的多项式，而不是与巨大整数 $K$ 的数值成正比。通常 RSA 指数代表小于 $n$ ，此时也可按 $\log n$ 控制。

第 17 章：补充：精确概率、统一指数与运行时间 ​

17.1 精确概率公式与最差情形 ​

17.2 卡迈克尔函数：统一周期与单个元素周期 ​

17.3 我们真正需要的是一个正的统一指数倍数 ​

17.4 有限次失败与期望多项式时间 ​

第 17 章：补充：精确概率、统一指数与运行时间

17.1 精确概率公式与最差情形

17.2 卡迈克尔函数：统一周期与单个元素周期

17.3 我们真正需要的是一个正的统一指数倍数

17.4 有限次失败与期望多项式时间