第 9 章：成功条件与两个首次到达时间

先只研究与 $n$ 互质的底数，即从 $U_n$ 中均匀选取 $a$ 。均匀表示其中每个剩余类被选到的概率都为 $1/\varphi(n)$ 。一旦 $a$ 选定，后续取幂、平方和取最大公约数都由它确定，没有新的随机选择。

第8章从全部 $1,\ldots,n-1$ 抽样的算法也适用：不互质的底数直接给出因子；条件于“选到的 $a$ 互质”，各个互质底数仍然等可能。因此先证明互质分支的成功率，再把直接成功的分支加回来即可。

连续平方的第 $j$ 项是 $x_j\equiv a^{2^jr}\pmod n$ 。用CRT拆开，模 $p$ 和模 $q$ 各自形成一条平方序列。两边都最终到1，但到达的时刻可能不同。

令

$T_p=\min\{j\ge0:a^{2^jr}\equiv1\pmod p\}, \qquad T_q=\min\{j\ge0:a^{2^jr}\equiv1\pmod q\}.$

$T_p$ 表示模 $p$ 第一次到1时，已经做了多少次平方； $T_q$ 含义相同。初始 $a^r$ 已经为1时，次数记为0。这两个量都由随机底数 $a$ 决定，因此称为随机变量。它们存在且不大于 $s$ ，因为第 $s$ 项已经为1；到1以后再平方，仍为1。

引入它们的目的，是把“前一项属于哪种平方根”转化为“两个坐标是否同时第一次到1”。后者更容易计数。

设 $T_p<T_q$ 。整体序列第一次到1的时刻是 $T_q$ ：此时两边都为1，而此前模 $q$ 还未到1。考察前一项 $j=T_q-1$ 。

模 $p$ 已经到1，所以前一项的 $p$ 坐标为1。模 $q$ 尚未到1，但下一次平方将为1，所以前一项的 $q$ 坐标是 $-1$ 。这里用的是质数下方程 $x^2=1$ 只有 $\pm1$ 两个根，排除1后就只剩 $-1$ 。

因此前一项的坐标为 $(1,-1)$ ，是非平凡平方根，算法成功。若 $T_q<T_p$ ，同理得到 $(-1,1)$ ，也成功。

若 $T_p=T_q=t>0$ ，前一项的两边都尚未到1，下一次却都为1，所以前一项为 $(-1,-1)$ ，即整体的 $-1$ ，算法失败。若 $t=0$ ，初始整体已为1，也失败。所有可能都已覆盖，因此对于互质底数，

$\boxed{\text{成功}\Longleftrightarrow T_p\ne T_q,\qquad \text{失败}\Longleftrightarrow T_p=T_q.}$

这一步只解释成功与失败的条件，还没有给出概率。下一步要问两个到达时间分别怎样分布，以及它们是否独立。

第6章给出双射 $U_n\longleftrightarrow U_p\times U_q$ 。右边共有 $(p-1)(q-1)$ 对坐标；每一对恰好对应一个底数。均匀选择 $U_n$ 中的底数，就等价于等可能地选择这些坐标对。

记 $A_p=a\bmod p$ 、 $A_q=a\bmod q$ 。固定一个非零余数 $b$ 和一个非零余数 $c$ ，有

$P(A_p=b,A_q=c)=\frac1{(p-1)(q-1)}.$

固定 $b$ 而让 $c$ 任意，一共有 $q-1$ 对，所以 $P(A_p=b)=1/(p-1)$ ；同理 $P(A_q=c)=1/(q-1)$ 。联合概率等于两个边缘概率的乘积，这正是独立性。

也可以把坐标对看成一个完整的行列表：模 $p$ 余数决定行，模 $q$ 余数决定列。知道选中了哪一行，仍不会偏向这行中的某一列，因为每行都有相同的全部列。这个理解对应的仍是上面的精确计数，而不是另外的假设。

$T_p$ 只需要 $a$ 的 $p$ 坐标就能计算， $T_q$ 只需要 $q$ 坐标；固定的 $r$ 没有额外随机性。因此分别对两个独立坐标做确定的运算，不会让它们相关。

把这一点写成计数更清楚。令 $B_t$ 为模 $p$ 到达时间等于 $t$ 的余数集合， $C_u$ 为模 $q$ 到达时间等于 $u$ 的余数集合。事件 $T_p=t,T_q=u$ 对应 $B_t\times C_u$ ，所以

$P(T_p=t,T_q=u) =\frac{|B_t||C_u|}{(p-1)(q-1)} =P(T_p=t)P(T_q=u).$

这里 $|B_t|$ 表示集合中的元素个数。对任意 $t,u$ 都成立，所以 $T_p,T_q$ 独立。关键不是“它们来自同一个底数”或“它们来自两个质数”，而是CRT保证均匀底数对应完整、均匀的坐标对。

我们已把失败转化为 $T_p=T_q$ ，也证明了两者独立。还需要知道：每个到达时间出现的概率是否有统一上界。

接下来的目标是证明，对于任意 $t$ ， $P(T_p=t)\le1/2$ ，模 $q$ 也一样。路线是：先证明取幂后的初始余数在一个较小循环群上均匀，再根据元素的阶统计首次到达时间。这里“元素均匀”与“到达时间均匀”是不同结论；后一种均匀实际上通常不成立。

第 9 章：成功条件与两个首次到达时间 ​