第 10 章：取幂的均匀性与到达时间分布

返回目录

10.1 均匀输入怎样才能产生均匀输出

先说明一个将反复使用的计数原则。若 $X$ 在一个有限集合 $S$ 上均匀，令 $Y=f(X)$ 。对于一个输出 $y$ ，

$P(Y=y)=\frac{|\{x\in S:f(x)=y\}|}{|S|}.$

分子是产生 $y$ 的输入个数，也称 $y$ 的原像个数。因为每个输入概率相同，输出概率就由有多少个输入合到这里决定。若每个可能输出的原像一样多，输出才均匀；若 $f$ 是双射，每个输出只有一个原像，当然也均匀。

所以“底数均匀”本身不足以推出“取幂后均匀”。下面必须实际检查这个取幂映射的原像数量，以及哪些映射是双射。

10.2 把模数的乘法周期拆成奇部和2的幂

只分析模 $p$ ，模 $q$ 同理。把 $p-1$ 中的因子2全部提出，写成

$p-1=2^\alpha u,\qquad u\text{为奇数}.$

$\alpha$ 表示 $p-1$ 含有多少个因子2；因为 $p$ 为奇质数， $\alpha\ge1$ 。另一方面，算法的指数是 $K=2^sr$ ， $r$ 为奇数。由于 $p-1\mid K$ ，有 $s\ge\alpha$ 和 $u\mid r$ 。

后一个整除关系为什么成立？ $u\mid2^sr$ ，但 $u$ 是奇数，与 $2^s$ 互质，所以可以消去 $2^s$ ，推出 $u\mid r$ 。于是写 $r=uw$ ， $w$ 也为奇数。

取模 $p$ 的原根 $g$ ，令 $h=g^u$ 。因为 $g$ 的阶为 $p-1=2^\alpha u$ ，第4.4节给出

$\operatorname{ord}_p(h) =\frac{2^\alpha u}{\gcd(2^\alpha u,u)}=2^\alpha.$

因此 $h$ 生成一个恰有 $2^\alpha$ 个元素的循环群

$H_p=\{1,h,h^2,\ldots,h^{2^\alpha-1}\}\quad(\bmod p).$

提出奇部 $u$ 的作用，就是从长度 $2^\alpha u$ 的原根循环中，得到长度纯为2的幂的循环。算法先算 $a^r$ ，也会消去这个奇部；下一节把两件事连接起来。

10.3 为什么指数开始对2的幂取模

原根给出唯一编号 $a\equiv g^k\pmod p$ ，其中 $0\le k<2^\alpha u$ 。取 $r=uw$ 次幂后，

$a^r\equiv(g^k)^{uw}=(g^u)^{kw}=h^{kw}\pmod p.$

现在底数变为 $h$ ，它的阶是 $2^\alpha$ 。所以 $h^{kw}$ 的值由指数 $kw\bmod2^\alpha$ 决定。这就是为什么指数的模数变为 $2^\alpha$ 。

幂值仍在模 $p$ 下计算，指数则按 $h$ 的周期取模 $2^\alpha$ 。 没有把 $a^r\bmod p$ 改成 $a^r\bmod2^\alpha$ 。第4.3节的指数与幂值区分在这里再次出现。

10.4 为什么取幂后在这个循环群上均匀

由第9章， $a\bmod p$ 在全部非零类上均匀。原根编号是双射，所以 $k$ 也在 $0,\ldots,2^\alpha u-1$ 上均匀。接着沿上一节的等式分三步看分布。

首先将 $k$ 对 $2^\alpha$ 取余。固定余数 $j$ ，恰有

$j,\ j+2^\alpha,\ \ldots,\ j+(u-1)2^\alpha$

这 $u$ 个编号产生它。每个余数的原像数相同，所以 $k\bmod2^\alpha$ 均匀，每个概率为 $u/(2^\alpha u)=2^{-\alpha}$ 。

其次把这个余数乘 $w$ 。因为 $w$ 为奇数， $\gcd(w,2^\alpha)=1$ ，乘法可消去：若 $wj_1\equiv wj_2\pmod{2^\alpha}$ ，必有 $j_1\equiv j_2$ 。因此乘 $w$ 是一个排列， $kw\bmod2^\alpha$ 仍均匀。此处只需要 $w$ 与 $2^\alpha$ 互质，不需要它与整个 $p-1$ 互质。

最后由编号 $j$ 转为 $h^j\bmod p$ 。由于 $h$ 的阶恰好为 $2^\alpha$ ，这又是双射。所以

$\boxed{a^r\bmod p\text{在 }H_p\text{上均匀，每个元素的概率为 }2^{-\alpha}.}$

完整的依据依次是：原根给出双射编号，取余有等大小原像，乘奇数是排列，最后的幂编号又是双射。 取幂通常没有在全部 $p-1$ 个非零类上保持均匀，而是在这个较小的 $H_p$ 上均匀。

如果希望核对各步，可以取 $p=13$ ： $p-1=4\cdot3$ ，选原根 $g=2$ ，则 $h=8$ 的阶为4。取 $r=9$ ，有 $w=3$ ；12个编号对4取余时每个余数有3个原像，乘3再把四个余数重排，因此输出 $1,8,12,5$ 各占 $1/4$ 。这个例子对应上面的原像数与排列，不承担一般证明。

10.5 到达时间为什么由元素阶决定

令 $z=a^r\bmod p$ ，它已在 $H_p$ 中。假设 $z$ 的阶为 $d$ 。连续平方 $j$ 次就是计算 $z^{2^j}$ ，所以第4.2节告诉我们

$z^{2^j}\equiv1\pmod p\quad\Longleftrightarrow\quad d\mid2^j.$

因为 $H_p$ 是 $2^\alpha$ 阶循环群， $z$ 的阶必为 $2^t$ ，其中 $0\le t\le\alpha$ 。这可以直接从 $z=h^k$ 与幂阶公式 $d=2^\alpha/\gcd(2^\alpha,k)$ 看出，也符合“元素阶整除群阶”的一般定理。

当 $d=2^t$ 时， $d\mid2^j$ 等价于 $j\ge t$ ，所以最早到1的时刻恰为 $T_p=t$ 。 $t=0$ 意味着 $d=1$ ，即初始 $z$ 已经是1。现在问题变成： $H_p$ 中有多少个元素的阶恰为 $2^t$ ？

10.6 怎样从阶的个数得到概率

先做一般计数。设 $h$ 的阶为 $N$ ，全部元素是 $h^k$ ， $0\le k<N$ 。若 $d\mid N$ ，由幂阶公式， $h^k$ 的阶恰好为 $d$ 等价于

$\gcd(N,k)=\frac Nd.$

满足条件的编号必能写成 $k=(N/d)j$ ，其中 $0\le j<d$ 。代入最大公约数，条件进一步等价于 $\gcd(d,j)=1$ 。这样的 $j$ 恰有 $\varphi(d)$ 个，所以循环群中阶恰为 $d$ 的元素有 $\varphi(d)$ 个。 $d=1$ 时只有单位元；第16章保留完整的群论证明。

回到 $N=2^\alpha$ 。阶为1的元素有1个；阶为 $2^t$ 、 $1\le t\le\alpha$ 的元素有 $\varphi(2^t)=2^{t-1}$ 个。这是因为 $0$ 至 $2^t-1$ 中与 $2^t$ 互质的编号正是奇数，恰占一半。

每个元素的概率已知为 $2^{-\alpha}$ ，因此

$\boxed{ P(T_p=t)= \begin{cases} 2^{-\alpha},&t=0,\\ 2^{t-1-\alpha},&1\le t\le\alpha,\\ 0,&\text{其他整数 }t. \end{cases}}$

这是“符合条件的元素个数除以全部元素个数”，不是把各个到达时间直接设成等可能。比如 $\alpha=2$ 时，阶1、2、4分别有1、1、2个元素，所以 $T_p$ 取0、1、2的概率为 $1/4,1/4,1/2$ 。这个小例子显示：元素均匀，到达时间却不均匀，因为不同阶的元素数量不同。

一般情况下，所有概率的总和为 $(1+1+2+\cdots+2^{\alpha-1})/2^\alpha=1$ 。而每个概率都不超过 $1/2$ ： $t=0$ 用 $\alpha\ge1$ ； $1\le t\le\alpha$ 时最大值在 $t=\alpha$ 取得，恰为 $2^{\alpha-1}/2^\alpha=1/2$ 。模 $q$ 完全同理，只需把 $\alpha$ 换成 $q-1$ 中因子2的次数 $\beta$ 。