算法导论11.5 Exercises 答案

\(\star\) 11.5-1

令\(g_a(k)=(2k^2+ak)\bmod 2^w\)。使用反证法证明函数\(g_a(w)\)是双射的。

假设\(\exists x,y\in\mathbb{Z}_{2^w},x\neq y,g_a(x)=g_a(y)\)，那么可以列出如下同余等式：

\[2x^2+ax\equiv 2y^2+ay\pmod{2^w}\]

经过化简后，得到\((x-y)(2(x+y)+a)\equiv 0\pmod{2^w}\)。这说明\(2^w\mid (x-y)(2(x+y)+a)\)。然而，\(a\)是奇数，因此其中一个因子\(2(x+y)+a\)必定是奇数，\(2^w\)不可能整除这个因子，由此引出矛盾。因此\(g_a(k)\)是一个单射函数。由于\(g_a(k)\)是从\(\mathbb{Z}_{2^w}\)映射到\(\mathbb{Z}_{2^w}\)的，那么可以说明函数\(g_a(k)\)是双射的。

不难说明\(f_a(k)=\text{swap}(g_a(k))\)是双射的。假设\(y\in\mathbb{Z}_{2^w},y'=\text{swap}(y)\)，令\(x,x'\)是满足\(g_a(x)=y,g_a(x')=y'\)的两个值，那么有\(f_a(x)=y',f_a(x')=y\)。\(g\)到\(f\)对操作无非是将\(x,x'\)的函数值进行交换，因此\(f_a(k)=\text{swap}(g_a(k))\)仍然是双射的。

接下来使用归纳法说明\(f_a^{(r)}=f(f_a^{(r-1)})\)是双射的。当\(r=1\)时，\(f_a^{(1)}=f_a\)是双射函数；当\(r>1\)时，假设\(f_a^{(r-1)}\)是双射函数，由于外层的嵌套\(f_a(\cdot)\)是双射函数，因此这个操作也仅仅是对原来的输出重新进行了一次置换。最终\(f_a^{(r)}\)是双射函数。

\(\star\) 11.5-2

根据随机预言机的定义，对于每个询问的\(x\in U\)，如果之前从未询问过，那么从\(\mathbb{Z}_m\)中均匀随机选择一个特定值存储下来并返回；否则直接返回之前存储下来随机选过的值。

由于第一次询问时是从\(\mathbb{Z}_m\)中均匀随机选择的，因此对于\(\forall x\in U,y\in \mathbb{Z}_m,\Pr\{h(x)=y\}=\dfrac{1}{m}\)。

随机预言机中，为\(x\)选择一个\(y\)的操作与其它的\(x'\in U\)选择值没有关系，因此对于所有\(x\in U\)，它们都是相互独立的，即\(\displaystyle{\Pr\left\{\bigwedge_{x\in U} h(x)=y_x\right\}}=\dfrac{1}{m^{|D|}}\)。因此随机预言机是\(|U|\)-独立的。在高层次上的\(|U|\)-独立性都成立，那么在低层次上，随机预言机是\(5\)-独立的。

\(\star\) 11.5-3

本题考察的是函数\(f_a^{(r)}\)的雪崩效应。

如图所示，当选择的比特\(k_i\)满足\(i>\dfrac{w}{2}\)时，至少需要进行\(3\)轮的迭代才会使所有比特可能都产生反转；否则只需要\(2\)轮就可以使所有比特可能都产生反转。

图中\(3\)种情况分别对应\(i>\dfrac{w}{2},i=\dfrac{w}{2},i<\dfrac{w}{2}\)时的一般情况。