本节对应原书 PDF 第 318–321 页。习题题干与答案书原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。原解答属原文层，不进折叠块。

13.1　用下述加密算法把“XINGDONGZAIZIYE”译成密文, 用 0\sim25 分别表示 \mathrm{A}\sim\mathrm{Z}, 密文仍用字母表示.

(1) E(i)=(i+3) \bmod 26.

(2) E(i)=7i \bmod 26.

(3) E(i)=(5i-2) \bmod 26.

解　明文 XINGDONGZAIZIYE

23 8 13 6 3 14 13 6 25 0 8 25 8 24 4

(1) 加密算法 E(i)=(i+3)\bmod 26.

密文 0 11 16 9 6 17 16 9 2 3 11 2 11 1 7

ALQJGRQJCDLCLBH

(2) 加密算法 E(i)=7i\bmod 26

密文 5 4 13 16 21 20 13 16 19 0 4 19 4 12 2

FENQVUNQTAETEMC

(3) 加密算法 E(i)=(5i-2)\bmod 26

密文 9 12 11 2 13 16 11 2 19 24 12 19 12 14 18

JMLCNQLCTYMTMOS

解读：三个算法的第一步完全相同——先把字母串按 A=0、B=1、…、Z=25 换成数字序列。差别只在第二步的数字变换, 所以比较三个密文时, 可以只看同一个明文字母（比如首字母 X=23）在三种算法下分别变成什么。

13.2　用维吉利亚密码将“XINGDONGZAIZIYE”译成密文, 每个字段含 3 个字母, 密钥 k=k_1k_2k_3, k_1=3, k_2=-2, k_3=7.

解　加密算法 E(m_1m_2m_3)=c_1c_2c_3

其中 c_i=(m_i+k_i)\bmod 26,\ i=1,2,3,\ k_1=3,\ k_2=-2,\ k_3=7.

明文 XINGDONGZAIZIYE

23 8 13 6 3 14 13 6 25 0 8 25 8 24 4

密文 0 6 20 9 1 21 16 4 6 3 6 6 11 22 11

AGUJBVQEGDGGLWL

解读：密钥长度为 3, 所以 15 个字母正好分成 5 组, 每组内第 1、2、3 个字母分别加上 3、-2、7。这是「多表替换」——同一个明文字母处在组内不同位置时会得到不同密文, 比 13.1 的单表替换更难破译。

13.3　设整数 a,b,m, 其中 m\geqslant 2. 证明: 线性同余变换

E(i)=(ai+b) \bmod m \qquad i=0,1,\cdots,m-1

是 \{0,1,\cdots,m-1\} 上的双射函数当且仅当 a 与 m 互素.

解　充分性. 设 a 与 m 互素, 则 a 的模 m 逆 a^{-1} 存在. 令

D(j)=a^{-1}(j-b)\bmod m,\quad j=0,1,\cdots,25

则

\begin{aligned} D(E(i)) &= a^{-1}((ai+b)\bmod m-b)\bmod m \\ &= a^{-1}((ai+b)-b)\bmod m \\ &= i,\quad i=0,1,\cdots,25 \end{aligned}
\begin{aligned} E(D(j)) &= (a(a^{-1}(j-b)\bmod m)+b)\bmod m \\ &= (aa^{-1}(j-b)+b)\bmod m \\ &= j,\quad j=0,1,\cdots,25 \end{aligned}

得证 E 是双射, D=E^{-1}.

必要性. 用反证法, 假设 a 与 m 不互素, 则 d=\gcd(a,m)>1. 记 a=da_1, m=dm_1, 于是

\begin{aligned} E(i+m_1) &= (a(i+m_1)+b)\bmod m \\ &= (ai+am_1+b)\bmod m \\ &= (ai+a_1m+b)\bmod m \\ &= (ai+b)\bmod m \\ &= E(i) \end{aligned}

而 i+m_1\not\equiv i(\bmod m), 与 E 是单射矛盾, 故 a 与 m 互素.

解读：必要性的构造思路是：若 a 与 m 有公因子 d>1, 则 am_1=a_1dm_1=a_1m 是 m 的倍数, 于是把自变量平移 m_1 后 E 的值不变, 单射性立刻被破坏。平移量 m_1=m/d 恰好小于 m, 所以 i 与 i+m_1 确实是两个不同的输入。

13.4　写出 13.1 题中 3 个加密算法的解密算法, 并将你在 13.1 题中得到的密文恢复成明文.

解　(1) 加密算法 E(i)=(i+3)\bmod 26

解密算法 D(i)=(i-3)\bmod 26

密文 ALQJGRQJCDLCLBH

0 11 16 9 6 17 16 9 2 3 11 2 11 1 7

明文 23 8 13 6 3 14 13 6 25 0 8 25 8 24 4

XINGDONGZAIZIYE

(2) 加密算法 E(i)=7i\bmod 26

7 与 26 互素, 7^{-1}\equiv 15(\bmod 26), 解密算法 D(i)=15i\bmod 26

密文 FENQVUNQTAETEMC

5 4 13 16 21 20 13 16 19 0 4 19 4 12 2

明文 23 8 13 6 3 14 13 6 25 0 8 25 8 24 4

XINGDONGZAIZIYE

(3) 加密算法 E(i)=(5i-2)\bmod 26

5 与 26 互素, 5^{-1}\equiv -5(\bmod 26), 解密算法 D(i)=-5(i+2)\bmod 26

密文 9 12 11 2 13 16 11 2 19 24 12 19 12 14 18

JMLCNQLCTYMTMOS

明文 23 8 13 6 3 14 13 6 25 0 8 25 8 24 4

XINGDONGZAIZIYE

解读：解密的全部依据是 13.3 的结论——a 与 26 互素时逆元 a^{-1} 存在, 于是把加密式反解即可。(3) 里 5^{-1}\equiv -5 是因为 5\times(-5)=-25\equiv 1(\bmod 26); 求出 a^{-1} 后先消去系数 5, 再把偏移 -2 移过去。

13.5　RSA 密码取 p=5, q=7, n=35, \phi(n)=24, w=7. 以 00\sim25 表示 \mathrm{A}\sim\mathrm{Z}, 每个字段是 2 位数字.

(1) 把 STOP 译成密文.

(2) 收到密文 32 14 32, 把它译成明文.

解　p=5, q=7, n=pq=35, \phi(n)=4\times 6=24, w=7.

(1) 明文 STOP 表成 18 19 14 15,7 的二进制表示是 111.

18^2\equiv 9(\bmod 35), 9^2\equiv 11(\bmod 35), 18^7\equiv 18\times 9\times 11\equiv 32(\bmod 35)

19^2\equiv 11(\bmod 35), 11^2\equiv 16(\bmod 35), 19^7\equiv 19\times 11\times 16\equiv 19(\bmod 35)

14^2\equiv 21(\bmod 35), 21^2\equiv 21(\bmod 35), 14^7\equiv 14\times 21\times 21\equiv 14(\bmod 35)

15^2\equiv 15(\bmod 35), 15^7\equiv 15\times 15\times 15\equiv 15(\bmod 35)

密文为：32 19 14 15

(2) 密文 32 14 32, 7^{-1}\equiv 7(\bmod 24), 得 d=7.

32^2\equiv(-3)^2\equiv 9(\bmod 35), 9^2\equiv 11(\bmod 35)

32^7\equiv(-3)\times 9\times 11\equiv 18(\bmod 35)

14^2\equiv -14(\bmod 35), (-14)^2\equiv -14(\bmod 35)

14^7\equiv 14\times(-14)\times(-14)\equiv 14(\bmod 35)

明文为：18 14 18, 即 SOS.

解读：求 x^7\bmod 35 用的是「反复平方」：x^7=x\cdot x^2\cdot x^4, 而 x^2、x^4 逐次平方即得, 不必真算七次乘法。注意本题 w=d=7, 因为 7^{-1}\equiv 7(\bmod 24), 所以加密和解密用的是同一个指数。

13.6　对下述参数给出用线性同余法产生的伪随机数序列, 并指出序列的周期.

(1) m=16, a=7, c=1, x_0=0.

(2) m=9, a=7, c=4, x_0=3.

(3) m=15, a=3, c=0, x_0=1.

(4) m=17, a=2, c=0, x_0=4.

(5) m=17, a=5, c=0, x_0=1.

解　线性同余法 x_n=(ax_{n-1}+c)\bmod m, n=1,2,\cdots

(1) m=16, a=7, c=1, x_0=0

伪随机数序列: 1,8,9,0,1,8,9,0,\cdots 周期: 4

(2) m=9, a=7, c=4, x_0=3

伪随机数序列: 7,8,6,1,2,0,4,5,3,7,8,\cdots 周期: 9

(3) m=15, a=3, c=0, x_0=1

伪随机数序列: 3,9,12,6,3,9,12,6,\cdots 周期: 4

(4) m=17, a=2, c=0, x_0=4

伪随机数序列: 8,16,15,13,9,1,2,4,8,16,\cdots 周期: 8

(5) m=17, a=5, c=0, x_0=1

伪随机数序列: 5,8,6,13,14,2,10,16,12,9,11,4,3,15,7,1,5,\cdots 周期: 16

解读：周期就是序列重新回到某个已出现过的值所经历的步数。(2) 的周期 9 恰好等于模数 m, 称为满周期, 此时序列遍历 0\sim m-1 全部取值; (1)(3)(4) 都只是 m 的一部分, 说明参数选得不好时伪随机数会有明显的短循环。

13.7　(1) 设计用 (0,1) 均匀分布伪随机数产生服从下述分布律的伪随机数的算法.

X0123
p0.100.350.050.50

(2) 分析算法的平均运行时间.

(3) 改进算法使得平均运行时间最少.

解　(1)

算法1：

  1. 产生 (0,1) 均匀分布伪随机数 u
  1. if u\leqslant 0.1 then x\leftarrow 0, 计算结束
  1. else if u\leqslant 0.45 then x\leftarrow 1, 计算结束
  1. else if u\leqslant 0.5 then x\leftarrow 2, 计算结束
  1. else x\leftarrow 3
  1. return x

(2) 设产生伪随机数 u 所需的时间为 a, 算法1 执行步骤 2\sim5 中的步数为 N, 算法1 的运行时间为 T=N+a+1.

N 与 u 的关系如下：

u(0,0.1](0.1,0.45](0.45,0.5](0.5,1]
N1234

故 N 的分布律为

N1234
p0.10.350.050.5

于是, 算法1 的平均运行时间为

E(T)=a+1+E(N)=a+1+1\times 0.1+2\times 0.35+3\times 0.05+4\times 0.5=a+3.95

(3) 按概率从大到小重新排列 X 的取值

X3102
p0.50.350.10.05

算法2：

  1. 产生 (0,1) 均匀分布伪随机数 u
  1. if u\leqslant 0.5 then x\leftarrow 3, 计算结束
  1. else if u\leqslant 0.85 then x\leftarrow 1, 计算结束
  1. else if u\leqslant 0.95 then x\leftarrow 0, 计算结束
  1. else x\leftarrow 2
  1. return x

类似地, 算法2 的平均运行时间为

E(T')=a+1+1\times 0.5+2\times 0.35+3\times 0.1+4\times 0.05=a+2.7

解读：改进的全部依据是「把概率大的取值放在判断链的最前面」。算法 1 里概率 0.5 的 X=3 要走到第 4 次判断才被选中, 而算法 2 让它第一次就命中, 平均步数从 2.95 降到 1.7, 期望时间因此减少 1.25。

13.8　设计用 (0,1) 均匀分布伪随机数产生服从几何分布的伪随机数的算法.

解　几何分布 p_k=P\{X=k\}=q^{k-1}p, k=1,2,\cdots

递推公式：

p_1=p
p_{k+1}=qp_k, k=1,2,\cdots

算法

  1. 产生 (0,1) 均匀分布伪随机数 u
  1. t\leftarrow p, F\leftarrow t, q\leftarrow 1-p, x\leftarrow 1
  1. while u>F
  1. \quad t\leftarrow t*q, F\leftarrow F+t, x\leftarrow x+1
  1. return x

解读：几何分布的取值无上界, 不可能像 13.7 那样列出有限个分支, 所以改用累加的方式：变量 F 逐步累加 p_1,p_2,\dots, 一旦 F 追上均匀随机数 u 就停下, 此时累计的项数就是 X。这也解释了为什么循环条件是 u>F 而非 u\geqslant F。

13.9　线性搜索算法如下:

Linear Search(A,x)　　　　　　// 数组 A[1..n], 待查找对象 x

1. for i\leftarrow 1 to n do

2. 　if A[i]=x then return i　　　　// 查找成功

3. return “no”　　　　　　// 查找失败

设 A 的 n 个元素都不相同, x 已在 A 中的概率为 p(0\leqslant p\leqslant 1), 并且当 x 在 A 中时, x 等于 A 的每一个元素的可能性相等. 试分析算法的平均时间复杂度.

解　若 x=A[i], 则循环执行 i 次; 若 x 不在 A 中, 则执行完循环(n 次)后再加 1 步. 根据题设, P(x=A[i])=\frac{p}{n}, i=1,2,\cdots,n; x 不在 A 中的概率等于 q=1-p. 算法的平均运行时间为

E(T_n)=\sum_{i=1}^{n}i\cdot\frac{p}{n}+q(n+1)=\left(\frac{1}{2}p+q\right)(n+1)=\left(1-\frac{1}{2}p\right)(n+1)

解读：注意「查找失败」这条路径的代价比成功路径更重——它要跑满 n 次循环, 再加最后返回 “no” 的那 1 步, 所以是 n+1。这也说明平均时间复杂度随失败概率 q 增大而升高。

13.10　设 A 的 n 个元素都不相同, 试证明下述算法产生的排列 A[1],A[2],\cdots,A[n] 服从均匀分布.

Random Permute Array(A)　　　　// 数组 A[1..n]

  1. for i\leftarrow 1 to n do
  1. 产生 \{i,i+1,\cdots,n\} 上的均匀随机数 k
  1. 交换 A[i] 与 A[k]

这段程序能起到随机化输入, 使其服从均匀分布的作用. 比如, 在快速排序算法的前面加上这段程序, 就得到随机快速排序算法.

解　记 S=\{A[i]\mid 1\leqslant i\leqslant n\}, 要证对每一个 i(1\leqslant i\leqslant n), 经过 i 次循环后 A[1..i] 为 S 中任意一个 i 个元素的子排列的概率等于 \frac{(n-i)!}{n!}.

当 i=1 时, 步骤2 产生的随机数 k 等可能地为 \{1,2,\cdots,n\} 中的任意一个, 故经过一次循环后, A[1] 为 S 中的任意一个的概率等于 \frac{1}{n}=\frac{(n-1)!}{n!}, 即结论成立.

假设对 i-1(2\leqslant i\leqslant n) 结论成立, 考虑经过 i 次循环. 设 x_1,x_2,\cdots,x_i 是 S 中的任意一个 i 个元素的子排列, 记

B: 经过 i-1 次循环后 A[1..i-1] 为 x_1,x_2,\cdots,x_{i-1}

C: 第 i 次循环中产生的随机数 k 使得 A[k]=x_i

于是, BC: i 次循环后 A[1..i] 为 x_1,x_2,\cdots,x_i. 而由归纳假设, 得

P(B)=\frac{(n-i+1)!}{n!}

从而

P(BC)=P(B)P(C|B)=\frac{(n-i+1)!}{n!}\cdot\frac{1}{n-i+1}=\frac{(n-i)!}{n!}

得证对 i 结论也成立.

因此, 经过 n 次循环后, A[1..n] 为 S 的任何排列的概率等于 \frac{1}{n!}, 即 A[1..n] 服从均匀分布.

解读：证明的关键在于条件概率 P(C|B)=\frac{1}{n-i+1}——前 i-1 个位置已经排定后, x_i 必定还留在 A[i..n] 这 n-i+1 个位置中, 而第 i 次循环的 k 在这段区间上均匀取值, 所以正好选中 x_i 所在位置的概率就是 \frac{1}{n-i+1}。

13.11　随机线性搜索算法是在执行线性搜索算法(题 13.9)之前先对输入进行随机重排(题 13.10), 描述如下:

Random Linear Search(A,x)　　　　// 数组 A[1..n], 待查找对象 x

  1. Random Permute Array(A)
  1. Linear Search(A,x)

假设 A 中有 k(1\leqslant k\leqslant n) 个元素等于 x, 试分析算法在调用 Linear Search(A,x) 时, 执行循环的次数的期望值.

解　执行 i 次循环 \Leftrightarrow A[1..i-1] 中不含 x 且 A[i]=x. 这样的 A[1..n] 有 P(n-k,i-1)\cdot k\cdot(n-i)! 个. 于是, 循环执行次数 T_n 的分布律为

\begin{aligned} P\{T_n=i\} &= \frac{P(n-k,i-1)\cdot k\cdot(n-i)!}{n!} \\ &= \frac{(n-k)!(n-i)!k}{(n-k-i+1)!n!}\quad i=1,2,\cdots,n-k+1 \end{aligned}
E(T_n)=\sum_{i=1}^{n-k+1}i\cdot\frac{(n-k)!(n-i)!k}{(n-k-i+1)!n!}
\begin{aligned} &= \frac{1}{\binom{n}{k}}\sum_{i=1}^{n-k+1}\binom{n-i}{k-1}\qquad \text{令}\ j=n-k+1-i \\ &= \frac{1}{\binom{n}{k}}\sum_{j=0}^{n-k}\binom{k-1+j}{k-1} \\ &= \frac{1}{\binom{n}{k}}\left[(n-k+1)\sum_{j=0}^{n-k}\binom{k-1+j}{k-1}-\sum_{j=0}^{n-k}j\binom{k-1+j}{k-1}\right] \\ &= \frac{1}{\binom{n}{k}}\left[(n-k+1)\sum_{j=0}^{n-k}\binom{k-1+j}{k-1}-k\sum_{j=1}^{n-k}\binom{k-1+j}{k}\right] \\ &= \frac{1}{\binom{n}{k}}\left[(n-k+1)\sum_{l=k-1}^{n-1}\binom{l}{k-1}-k\sum_{l=k}^{n}\binom{l}{k}\right] \\ &= \frac{1}{\binom{n}{k}}\left[(n-k+1)\binom{n}{k}-k\binom{n+1}{k+1}\right]\qquad (\text{主教材 8.3.2 节(8)}) \\ &= n-k+1-\frac{k(n-k)}{k+1} \end{aligned}

解读：计数式 P(n-k,i-1)\cdot k\cdot(n-i)! 可以逐段读：前 i-1 个位置要从 n-k 个不等于 x 的元素里有序地选, 有 P(n-k,i-1) 种; 第 i 位放 x, 有 k 种选法; 剩下 n-i 个位置任意排, 有 (n-i)! 种。化简中反复使用主教材 8.3.2 节的组合恒等式, 最后一步消去二项式系数。

13.12　某公司要招聘一名技术主管, 有 n 位应聘者. 招聘人员与他们一位一位地面谈, 并当场告诉对方是否录用. 具体做法是, 首先确定一个正整数 k(1\leqslant k\leqslant n-1), 然后对每位应聘者通过面谈打一个分数, 打的分数都不相同. 前 k 位都不录用, 设前 k 位的最高得分为 m. 从第 k+1 位起, 只要得分超过 m 就录用, 不再考虑后面的人. 如果 n-k-1 位的得分都不超过 m, 此时只剩下最后一位, 不管他得多少分都录用. 算法描述如下, 其中 score(i) 是第 i 位应聘者的得分.

On-Line Max(n,k)

  1. m\leftarrow -\infty
  1. for i\leftarrow 1 to k do
  1. if score(i)>m then m\leftarrow score(i)
  1. for i\leftarrow k+1 to n-1 do
  1. if score(i)>m then return i
  1. return n

假设 n 位应聘者的排列服从均匀分布,

(1) 求恰好选中分数最高者的概率 p, 并分析 k 应如何取值.

(2) 求需要面谈的人数的期望值.

解　(1) 设 A_i: 选中第 i 人且第 i 人是最高分, 即第 i 人是最高分且前 i-1 个人中的最高分在前 k 个人中, i=k+1,k+2,\cdots,n. 则

P(A_i)=\frac{1}{n}\cdot\frac{k}{i-1}

故恰好选中最高分的概率为

p_k=\sum_{i=k+1}^{n}p(A_i)=\frac{1}{n}\sum_{i=k+1}^{n}\frac{k}{i-1}=\frac{k}{n}\sum_{j=k}^{n-1}\frac{1}{j}

考虑 p_k\leqslant p_{k+1}, 即

\frac{k}{n}\sum_{j=k}^{n-1}\frac{1}{j}\leqslant\frac{k+1}{n}\sum_{j=k+1}^{n}\frac{1}{j}

化简得

\sum_{j=k+1}^{n-1}\frac{1}{j}\geqslant 1

因此 k_0=\min\left\{k\left|\sum_{j=k+1}^{n-1}\frac{1}{j}<1\right.\right\} 使 p_k 取到最大值.

注意到 \sum_{j=k+1}^{n-1}\frac{1}{j}\approx\int_{k}^{n-1}\frac{\mathrm{d}x}{x}=\ln\frac{n-1}{k}, 由 \ln\frac{n-1}{k}=1, 解得 k_0\approx(n-1)\mathrm{e}^{-1}.

例如, 当 n=20 时, \sum_{j=7}^{19}\frac{1}{j}=1.10, \sum_{j=8}^{19}\frac{1}{j}=0.95, k_0=7. 而 (20-1)\mathrm{e}^{-1}=6.99.

(2) 记 X: 被选中人的序号.

X=i\Leftrightarrow 第 i 人的分数是前 i 个人中最高的且前 i-1 个人中的最高分在前 k 个人中, i=k+1,k+2,\cdots,n-1.

X=n\Leftrightarrow 前 n-1 个人中的最高分在前 k 个人中.

X 的分布律为

P\{X=i\}=\frac{k}{i(i-1)}\qquad i=k+1,k+2,\cdots,n-1
P\{X=n\}=\frac{k}{n-1}

面谈人数的平均值为

EX=\sum_{i=k+1}^{n-1}i\cdot\frac{k}{i(i-1)}+n\cdot\frac{k}{n-1}=k\left(1+\sum_{j=k}^{n-1}\frac{1}{j}\right)

解读：(1) 的概率 \frac{1}{n}\cdot\frac{k}{i-1} 是两件事同时发生的概率：第 i 人恰为全局最高分（概率 \frac{1}{n}）, 且前 i-1 人中的最高分落在前 k 人中（概率 \frac{k}{i-1}）。(2) 里 X=n 单列一项, 因为最后一位是「兜底录用」, 触发条件与前 n-1 位不同。

13.13　用散列函数 h 把 n 个不同的关键字散列到长度为 m 的表 T 中, 假设 h 为简单均匀散列函数, 求平均的冲突数.

解　令 X_{ij}=\begin{cases}1 & h(K_i)=h(K_j) \\ 0 & \text{否则}\end{cases} 1\leqslant i<j\leqslant n

P\{X_{ij}=1\}=\frac{1}{m}

冲突数 M=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}X_{ij}, 平均冲突数为

\begin{aligned} E(M) &= \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}E(X_{ij})=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac{1}{m} \\ &= \frac{1}{m}\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2m} \end{aligned}

解读：把「冲突数」拆成 \binom{n}{2} 个 0-1 指示变量之和, 是这类计数期望的标准手法——每个 X_{ij} 的期望就是这一对关键字撞车的概率 \frac{1}{m}, 由期望的线性性直接相加即可, 不需要考虑各对之间是否独立。

13.14　设 p 是一个素数, m\geqslant 2, 记 Z_p=\{0,1,\cdots,p-1\}, Z_p^*=\{1,2,\cdots,p-1\}. 对每一对 \langle a,b \rangle\in Z_p^*\times Z_p, 定义

\bar{h}_{a,b}(K)=(aK+b)\bmod p
h_{a,b}(K)=\bar{h}_{a,b}(K)\bmod m \qquad K\in Z_p

试证明:

(1) 对每一对 \langle a,b \rangle\in Z_p^*\times Z_p, \bar{h}_{a,b} 是 Z_p 上的双射函数.

(2) 设 \langle a,b \rangle 服从 Z_p^*\times Z_p 上的均匀分布, 则对 Z_p 中任意的 K\neq L,

P(h_{a,b}(K)=h_{a,b}(L))\leqslant \frac{1}{m}

\{h_{a,b}\mid \langle a,b \rangle\in Z_p\times Z_p^*\} 称作通用散列函数类.

解　(1) 因为 p 是素数, 1\leqslant a<p, 所以 a 的模 p 逆 a^{-1} 存在. 令

\bar{h}_{a,b}^{-1}(K)=a^{-1}(K-b)\bmod p\qquad \forall K\in Z_p

不难验证: \forall K\in Z_p, \bar{h}_{a,b}^{-1}(h_{a,b}(K))=K, \bar{h}_{a,b}(\bar{h}_{a,b}^{-1}(K))=K, 从而得证 \bar{h}_{a,b} 是 Z_p 上的双射函数.

(2) 设 K,L\in Z_p 且 K\not=L, 不妨设 (aK+b)\bmod p\geqslant(aL+b)\bmod p. 又因为 K\not=L, 故 K-L 的模 p 逆 (K-L)^{-1} 存在. 于是

\begin{aligned} h_{a,b}(K)=h_{a,b}(L) &\Leftrightarrow \bar{h}_{a,b}(K)\equiv\bar{h}_{a,b}(L)(\bmod m) \\ &\Leftrightarrow (aK+b)\bmod p-(aL+b)\bmod p\equiv 0(\bmod m) \\ &\Leftrightarrow a(K-L)\bmod p\equiv 0(\bmod m)\qquad \text{两边同乘}(K-L)^{-1} \\ &\Leftrightarrow a\bmod p\equiv 0(\bmod m) \end{aligned}

而 a 服从 Z_p^* 上的均匀分布, 得到

P\{h_{a,b}(K)=h_{a,b}(L)\}=\frac{\lfloor(p-1)/m\rfloor}{p-1}\leqslant\frac{1}{m}

待核：答案书 p230 中 13.14(2) 推导的 \bmod m 与 \bmod p 混用系原书如此, 已逐字照抄未改。