【随机化算法】
随机化算法（Randomized Algorithms）在密码学中具有核心作用。因此，在密码学中讨论“高效计算”时，不能只考虑确定性多项式时间模型，还需要考虑概率多项式时间（Probabilistic Polynomial Time）模型
引入：随机化算法实例
考虑一个简单的随机化算法问题：判断一个无向图是否连通
判断图是否连通，可以规约为判定图中任意一对结点之间是否存在路径。因此，只需考虑如下任务：给定图 $G=(V,E)$ 以及两个顶点 $s,t\in V$，判断 $s$ 与 $t$ 是否连通
一个随机化算法可以这样设计：从顶点 $s$ 出发，进行长度为 $O(|V||E|)$ 的随机游走，并在每一步检查是否遇到顶点 $t$，若在某一步遇到 $t$，算法就接受，否则算法就拒绝
该算法的分析可分为两种情况：
- 若 $s$ 与 $t$ 不连通，则算法接受的概率为 $0$
- 若 $s$ 与 $t$ 连通，则算法至少以 $\frac{2}{3}$ 的概率接受
注意，这里的 $\frac{2}{3}$ 并非一个精确计算出来的概率，而是通过马尔可夫不等式对算法运行时间进行约束后得到的标准概率下界。事实上，只要随机算法的成功率大于 $\frac{1}{2}$，就可以通过重复独立运行将其提升至任意接近 $1$ 的程度，不过在计算理论中，使用 $\frac{2}{3}$ 作为标准下界是一个通用的惯例，其足以证明算法具有常数级的成功概率保证
对于无向图的随机游走，从 $s$ 到 $t$ 所需的步数 $H_{st}$ 是一个随机变量，称为击中时间（Hitting Time），从任意起点 $s$ 到任意终点 $t$ 的期望击中时间 $\mathbb{E}[H_{st}]$ 存在确定上界：
由于 $|V|-1<|V|$，因此有：
也就是说，虽然随机游走不一定很快到达 $t$，但它的期望到达时间至多是 $O(|V||E|)$
记游走步数为 $L=O(|V||E|)$，如果算法在 $L$ 步内没有遇到 $t$，则说明 $H_{st}>L$，那么根据马尔可夫不等式，有：
记期望击中时间的上界为 $T=2|E||V|$，假设游走步数满足 $L=3T$，那么有：
因此，只要 $s$ 和 $t$ 连通，那么随机游走在 $L=3T=6|V||E|$ 步遇到 $t$ 的概率至少为：
这里的 $\frac{2}{3}$ 并非一个精确计算出来的概率，而是通过把随机游走的长度 $L$ 取成足够大的 $6|V||E|$ 而得到的概率保证。如果取 $L=100T$，则错误概率可以进一步降至 $\frac{1}{100}$
概率多项式时间图灵机
形式化来说，可以把随机化算法看作一种概率多项式时间图灵机（Probabilistic Polynomial Time Turing Machine），其是一种允许使用随机性的图灵机模型，在运行过程中能够真实地进行随机选择
图灵机 $M$ 的转移函数在每一步可能给出两个可能的转移结果，然后随机选择其中一个继续执行，且无论随机选择的结果是什么，机器必须在输入长度 $|x|$ 的某个多项式步数 $T_M(|x|)$ 内停机
此时，可以从两个等价角度理解随机性：
- 内部随机选择（Internal Random Choice）：算法在运行过程中可以进行随机选择，也就是“抛硬币”
- 辅助随机输入（Auxiliary Random Input）：算法本身是确定的，但把随机选择的结果作为一个额外输入
内部随机选择
在内部随机选择视角下，图灵机 $M$ 在输入 $x$ 上的输出不是一个固定字符串，而是一个随机变量 $M(x)$，这个随机变量由图灵机由计算过程中的内部随机选择决定。因此，图灵机 $M$ 在输入 $x$ 上输出 $y$ 的概率可写为：
由于主要考虑多项式时间图灵机，为不失一般性，可以假设图灵机 $M$ 在输入 $x$ 上进行随机选择的次数与随机结果无关，记为 $t_{M}(x)$。用 $M_r(x)$ 表示图灵机 $M$ 在输入 $x$、内部随机选择结果为 $r$ 时的输出，则图灵机 $M$ 在输入 $x$ 上输出 $y$ 的概率，等于所有可能随机串中使图灵机输出 $y$ 的随机串所占的比例，即：
辅助随机输入
辅助随机输入视角下，图灵机本身是确定性的，但它有两个输入，第一个输入是真正的问题输入 $x$，第二个输入是表示内部随机选择结果的随机串 $r$
此时，图灵机 $M$ 在输入 $x$ 与 $r$ 的输出可写为：
当固定输入 $x$ 后，让 $r$ 在 $\{0,1\}^{t_M(x)}$ 上均匀随机选择，就可以得到 $M(x,r)$ 的概率分布，这个概率分布与内部随机选择观点下的 $M(x)$ 是等价的
【高效计算与 BPP】
随机化算法采用的基本观点是：高效计算（Efficient Computations），不仅包括确定性多项式时间算法能够完成的计算，也包括概率多项式时间算法能够完成的计算。也就是说，只要一个随机化算法的运行时间被输入长度的某个多项式限制，它就可以被视为一种高效算法
在判定问题中，如果某个语言可以由概率多项式时间图灵机以有界错误概率识别，那么这个语言属于复杂性类 BPP（Bounded Probabilistic Polynomial Time）。需要注意的是，BPP 不是一个具体算法，也不是一台图灵机，而是一个语言类，其包含所有能够由概率多项式时间图灵机以高概率正确判定的语言
若语言 $L\in\mathcal{BPP}$，那么存在一个概率多项式时间图灵机 $M$，使得：
- 对于每个 $x\in L$，有：$P[M(x)=1]\geq \frac{2}{3}$
- 对于每个 $x\notin L$，有：$P[M(x)=0]\geq \frac{2}{3}$
其中，$M(x)=1$ 表示图灵机接受输入 $x$，即判断 $x\in L$；$M(x)=0$ 表示图灵机拒绝输入 $x$，即判断 $x\notin L$
形式化地，定义：
若 $M$ 是一个识别语言 $L\in \mathcal{BPP}$ 的概率多项式时间图灵机，则对于 $\forall x\in\{0,1\}^{*}$，都有：
这里的有界错误概率表示算法的成功概率要与 $\frac{1}{2}$ 保持一个固定距离，即算法不仅要比随机猜测好一点，而是至少具有一个常数级优势
上述定义中的 $\frac{2}{3}$ 只是一个通用惯例，可以替换为任何大于 $\frac{1}{2}$ 的常数，只要随机算法的成功率大于 $\frac{1}{2}$，就可以通过重复独立运行并取多数结果，将成功概率提升至任意接近 $1$ 的程度
【可忽略函数】
若对于任意多项式 $\mathrm{poly}(\cdot)$，均 $\exists N\in \mathbb{N}$，使得 $\forall n>N$，都有：
则称 $\mu$ 为可忽略函数（Negligible Functions）。直观来说，其是一类比任意多项式倒数下降得都要快的函数
可忽略函数具有一个重要性质：如果一个可忽略函数乘以任意多项式，那么结果仍是可忽略函数。也就是说，对于任意可忽略函数 $\mu(\cdot)$ 和任意多项式 $\mathrm{poly}(\cdot)$，函数 $\mu’(n)=\mu(n)\cdot \mathrm{poly}(n)$ 仍是可忽略函数
因此，如果某个事件发生的概率是可忽略的，那么即使将实验重复多项式次，该事件仍然既不可能发生
证明：可忽略函数乘以多项式仍可忽略
按照定义，需要证明：对于任意多项式 $\mathrm{poly}’(\cdot)$，$\exists N$，使得 $\forall n>N$ 时，有 $\mu(n)\mathrm{poly}(n)<\frac{1}{\mathrm{poly}’(n)}$
注意到，$\mathrm{poly}(n)\mathrm{poly}’(n)$ 仍是一个多项式，那么根据可忽略函数的定义，对于这个多项式，存在一个 $N$，使得当 $n>N$ 时，有：
两边同时乘以多项式 $\mathrm{poly}(n)$ 可得：
原式得证
