OMSCS-GA课程笔记05-Randomized Algorithms

这个系列是Gatech OMSCS 高级算法课程(CS 6515: Intro to Grad Algorithms)的同步课程笔记。课程内容涉及动态规划、随机算法、分治、图算法、最大流、线性规划以及NP完备等高级算法的设计思想和相关应用，本节主要介绍随机算法。

随机算法在密码学中有着非常重要的应用。

Modular Arithmetic

在介绍随机算法与密码学的关系前我们需要先来引入模算数(modular arithmetic)的相关概念。对于整数$x$我们定义取模运算mod来获得它关于$N$的余数，如果两个整数$x$和$y$具有相同的余数则称它们关于$N$同余(congruence)：

以除数3为例，通过取模运算可以定义3个同余等价类。

Basic Fact

同余的一个基本性质是如果$x$和$y$以及$a$和$b$分别关于$N$同余等价，则$x+a$和$y+b$同余等价且$xa$和$yb$同余等价。

Modular Exp

模算数的一个重要应用是计算指数的余数。对于n-bit整数$x$和$y$，我们可以通过递推的方法来计算$x^y$的余数：

上述算法的复杂度依赖于$y$的大小。更高效的算法是利用平方运算来减少迭代步骤：

Multiplicative Inverse

我们定义mod运算的逆为满足$x z \equiv 1 \ \text{mod} \ N$的整数，记为$x \equiv z^{-1} \ \text{mod} \ N$。

需要注意的是并不是所有的整数都存在逆。

实际上当且仅当$x$和$N$的最大公约数(greatest common divisor, GCD)为1时才存在逆。

GCD

因此计算mod的逆就归结于计算$x$和$N$的最大公约数。关于最大公约数的研究可以追溯到古希腊的欧几里得，他指出$x$和$y$的最大公约数等于$(x \ \text{mod} \ y)$和$y$的最大公约数：

基于欧几里得定理可以得到计算最大公约数的算法，其复杂度为$O(n^3)$：

Euclid(x, y):
  if y == 0:
    return x

  else:
    return Euclid(y, x mod y)

这样就可以计算mod的逆，其复杂度为$O(n^3)$：

Ext-Euclid(x, y):
  if y == 0:
    return (x, 1, 0)

  else:
    d, alpha', beta' = Ext-Euclid(y, x mod y)
    return (d, beta', alpha' - x//y * beta')

RSA

Fermat’s Little Theorem

在模算数的基础上就可以介绍密码学中重要的RSA算法了，不过在此之前我们还需要引入费马小定理(Fermat’s little theorem)。它指出对于任意质数$p$和小于$p$的整数$z$，$z^{p-1}$与1关于$p$同余：

Euler’s Theorem

欧拉定理(Euler’s theorem)是对费马小定理的推广，它指出互质的整数$N$和$z$，$z^{\phi(N)}$与1关于$N$同余，其中$\phi(N)$为小于$N$且与$N$互质的整数数量。

如果我们进一步令$N$为两个质数$p$和$q$的积$N=pq$，可以证明$\phi(N)=(p-1)(q-1)$。这样有$z^{(p-1)(q-1)}$与1关于$N$同余。

RSA Idea

RSA算法的基本思想是利用欧拉定理来对$z$进行加密。我们取两个质数$p$和$q$并计算它们的积$N=pq$，接下来取关于$(p-1)(q-1)$互逆的一对整数$d$和$e$。进行加密时加密方已知$e$和$N$，这样可以计算$z^e$；而在解密时解密方知道$e$，利用$z^{de}$就可以恢复$z$。

Cryptography Setting

在密码学中最常见的一类场景是公开密钥加密(public-key cryptography)。此时数据发送方通过加密函数e()对信息进行加密，而接收方通过解密函数d()进行解密，它们之间的直接通信都是加密后的消息e(m)。同时接收方会公开公钥(public key)，这样任何拥有公钥的人都可以加密，但只有数据接收方能够利用私钥(private key)进行解密。

RSA Protocols

因此数据接收方的任务在于计算公钥和私钥，然后公开公钥并保留私钥用来解密。为此它需要首先选择两个质数$p$和$q$，然后计算与$(p-1)(q-1)$互质的$e$用来加密，这样就得到了公钥$N=pq$和$e$，最后计算并保存私钥$d$即可。

对于数据发送方来说，它只需要先获取公钥$N$和$e$，然后对消息$m$进行加密$y \equiv m^e \ \text{mod} \ N$，最后发送加密后的消息$y$即可。

而当接收方需要进行解密时只需要利用私钥计算$y^d \ \text{mod} \ N = m$。

RSA Pitfalls

使用RSA进行加密时需要注意的是保证原始数据$m$和$N=pq$是互质的，而如果它们存在公约数则容易导致一些问题。假设$m$和$N$存在公约数$p$，对于数据接收方仍然可以正确地进行解密，但是任何截获加密数据$m^e$的人都可以利用gcd(y, N)来破解$p$进而获得私钥。因此在进行加密时需要注意验证$m$和$N$是否是互质。

另一方面我们还希望原始数据$m$既不是特别大也不是特别小的数字，当$m$特别大或者特别小时都容易导致加密失效。

RSA Recap

总结一下目前为止的内容，整个RSA算法的流程如下：

Random Prime Numbers

整个RSA算法依赖于选取质数$p$和$q$，因此我们需要设计随机质数的生成算法。要生成随机质数我们首先需要生成随机n-bit整数，这个过程比较简单只需要对n-bit随机赋予0或者1即可。然后我们验证这个随机整数是否是一个质数，如果它是质数就得到了一个随机质数，否则重新生成一个新的随机整数再进行判断即可。可以证明n-bit随机整数恰为质数的概率约为$\frac{1}{n}$，因此理论上我们只需要重复生成n次随机整数就可以得到一个随机质数。

要验证一个整数是否是质数则需要费马素性检验(Fermat primality test)。根据费马小定理，任意小于质数$r$的整数$z$一定有$z^{r-1} \equiv 1 \ \text{mod} \ r$。因此如果我们能够找到一个小于$r$的整数$z$使得$z^{r-1} \not\equiv 1 \ \text{mod} \ r$，那么$r$一定是一个合数，这样的$z$称为Fermat witness。

可以证明任意合数都至少存在一个Fermat witness。

因此合数的因数一定是Fermat witness，称为trivial Fermat witness。而实际上Fermat witness不一定都是因数，此时则称其为non-trivial Fermat witness。只有trivial Fermat witness的合数称为Carmichael数(Carmichael number)，在使用费马素性检验时它们的性质非常接近于质数，因此也被称为伪质数(pseudo primes)。不过Carmichael数非常少见，在简单情况下我们可以忽略它们的存在。

如果我们忽略Carmichael数的存在可以得到质数的检验算法：

Bloom Filters

Ball into Bins

假设我们有$n$个完全相同的小球与$n$个盒子，每次随机将一个小球置入其中一个盒子中，此时第$i$个盒子中的小球数量是一个随机变量$\text{load}(i)$。记盒子中数目最多的小球数为$\max \ \text{load}$，它同样是一个随机变量且最大值为$n$，即所有小球同时落入一个盒子中。不过这种情况的概率很低，为$(\frac{1}{n})^n$。

要分析$\max \ \text{load}$的分布并不容易。首先，前$\log (n)$个小球都落在第$i$个盒子的概率为$(\frac{1}{n})^{\log n}$。

在此基础上可以证明第$i$个盒子中小球数量至少为$\log (n)$的概率小于等于${n \choose \log n} (\frac{1}{n})^{\log n}$。

当$n$比较大时组合数具有上界：

\[{n \choose k} \approx \bigg( \frac{n}{k} \bigg)^k \leq \bigg( \frac{n \ e}{k} \bigg)^k\]

带入概率上界可以得到：

\[P \leq \bigg( \frac{n \ e}{\log n} \bigg)^{\log n} \bigg( \frac{1}{n} \bigg)^{\log n} = \bigg( \frac{e}{\log n} \bigg)^{\log n}\]

由于$\frac{e}{\log n}$随$n$的增加而减小，我们可以进一步使用常数$\frac{1}{4}$进行放缩。进一步假设$n > 2^{11}$可以得到最终的概率上界$\frac{1}{n^2}$。

利用上面的结论可以推导出$\max \ \text{load}$至少为$\log n$的概率上界为$\frac{1}{n}$，而它的下界有大概率为$\frac{\log n}{\log \log n}$。

除了随机放置小球外，另一种放置小球的方式是每次随机选择两个盒子然后把小球放到$\text{load}$较小的那个盒子中。

可以证明按照这种方式进行放置时$\max \ \text{load}$的上界有大概率为$\log \log n$。

Chain Hashing

Hashing在现实生活中有着非常多的应用，比如说可以使用hashing作为容器来保存数据，此时我们需要回答的问题是容器中是否存在某个给定的元素$x$。最常见的实现方法是构造一个数组，其中每个位置对应一个链表。然后设计一个函数$h(x)$将可能的元素$x$映射到链表的编号。这样的实现方式称为chain hashing。假设$h(x)$是一个随机函数，我们可以把链表想象成小球问题中的盒子，而元素$x$则为小球，这样就可以使用上一节的结论来进行分析。