算法杂记

2019-03-26 本文已影响0人 tristan_lee

起源

如今，人们早已习惯了以十进制来书写数字，也早已忘记了古代欧洲将数字1448写成MCDXLVIII的情形。你是否知道应该如何将两个罗马数字相加？你又是否知道MCDXLVIII + DCCCXII会得到什么结果？（还可以试下将他们相乘）。面对罗马数字这种记数法，别说算，我想想都觉得是恶梦。

十进制系统是人类定量推理方面的一项重大变革，发源于约公元600年的印度。它仅仅使用了10个符号，甚至可以很简洁地写出很大的数字，它使得后面演示的算法基本步骤变得非常有效率。对十进制系统的传播产生重大影响的是一本教材，这本书由一个居住于巴格达的阿拉伯人Al Khwarizmi写于19世纪。Al Khwarizmi在书中展示了数字的加、减、乘、除的基本方法，甚至展示了如何求平方根和π。这些方法精准、明确、有法可寻、具有效率、正确而且简单，它们被称作算法algorithms。在很多世纪之后，十进制系统最终被欧州采用，而算法algorithms这个名词同时也表达了对作者Al Khwarizmi的敬意与纪念。

大O表示法

大O表示法的定义：

Let $f(n)$ and $g(n)$ be functions from positive integers to positive reals. We say $f = O(g)$ (which means that “ $f$ grows no faster than $g$ ”) if there is a constant $c > 0$ such that $f(n) ≤ cg(n)$ .

大O表示法的核心是抓大放小，抓住主要矛盾。例如面对函数 $f(n)=3n^2+4n+5$ ，这里的 $O(f(n))$ 我们要做的就是抓住主要增长部分，所以可以写成 $O(n^2)$ ；因为相对于 $3n^2$ ，其它项的增长都是次要的，而且可以去掉常数3。

大O的三种增长模式

指数增长 $O(a^n)$ ，a为常数，如 $O(2^n)$
多项式增长 $O(n^a)$ ，a为常数，如 $O(n^2)$
对数增长 $O(\log(n))$

数论

两个古老的数论问题：

因子分解：给定数字N，将它表示成其素因子的乘积形式
素性测试：给定数字N，判定其是否为素数

这两个问题看上去似乎十分相似，但其中因子分解是非常困难的，直到现在，分解整数N的最快方法所耗费的时间仍然是对N位数的指数级函数。而另一个问题，我们却可以快捷地测试出一个数N是否为素数。这种奇怪的差异：一个十分困难，一个却异常简单；也正是这种差异奠定了安全通信技术的核心，从而保证了当今世界全球范围内通信环境的安全。

著名的数学家G. H. Hardy，也是数论方面的大家，曾这样描述过他自己的工作：“我这辈子所研究的东西都没有任何实用价值”。然而也正是这些人在几个世纪中的这些“没有价值的”工作，奠定了如今整个互联网，手机通信，当然还包括银行金融领域的安全基石。

欧几里德最大公因数算法

欧几里德规则：

gcd(a,b) = gcd(a mod b, b) (不妨设a>b 且r=a mod b ,r不为0)

其中gcd代表greatest common divisor

求最大公因数的欧几里德算法：

function Euclid(a, b)
Input: Two integers a and b with a ≥ b ≥ 0
Output: gcd(a; b)

if b = 0: return a
return Euclid(b, a mod b)

模的除法

基本概念：

乘法逆元：如果 $ax ≡ 1$ (mod N) 成立，我们称x是关于a模N的一个乘法逆元。
互素：如果gcd(a, N) = 1，我们说a和N互素。
模的除法定理：对于任意的a mod N，a有一个模N的乘法逆元，当且仅当a与N互素。
有逆元的好处
- 计算机中的除法操作可以变成乘法操作
- 双向映射(bijection)

素性测试

素数 - 一个大于1的自然数，除了1和它本身以外不再有其他因数
合数 - 是相对于素数而言的，自然数中除了能被1和本身整除外，还能被其他数（0除外）整除的数
- Carmichael数 - 非常特殊罕见的一种合数

费马小定理(Fermat's little theorem)：

如果p是素数，那么对每个a (1 ≤ a < p)，有 $a^{p-1} ≡ 1$ (mod p)成立
If p is prime, then for every 1 ≤ a < p, $a^{p-1} ≡ 1$ (mod p)

图片.png

无处不在的概率：

如上图所示费马小定理为我们提供了一种对N的素性测试。但这里还存在问题，就是费马小定理并不是判断N是否为素数的充分必要条件；它并没有规定当N不是素数时会怎样。而事实上对a的某些取值，一些合数N可能能够通过费马小定理的测试（即 $a^{N-1} ≡ 1$ mod N），例如对于341=11*31并不是一个素数，然而却有 $2^{340} ≡ 1$ mod 341成立。但我们还是有希望的，又是概率来拯救。事实上对于合数N，大多数选取的a值都是不能通过费马小定理的测试，这就为我们提供了在实际应用中可行的算法。

以费马小定理作为测试我们可以得到一个素性测试算法：

function primality(N)
Input: Positive integer N
Output: yes/no

Pick a positive integer a < N at random
if a^(N-1) ≡ 1 (mod N):
    return yes
else:
    return no

引理：如果对于某些与N互素的a，有 $a^{N-1} ≡ 1$ mod N不成立，那么对于a<N的至少一半的可能取值，N将无法通过费马测试。（证明略）

由引理我们可以得到以上素性测试算法返回正确值的概率：

P(当N为素数，算法返回yes) = 1
P(当N不为素数，算法返回yes) ≤ 1/2

这样我们就可以得到一个改进版本算法，通过多次重复原先的过程来减少出错概率；可见出错概率将以指数级别快速降低，通过选择足够大的k值，能够使出错概率降低至任意小的水平。当k=100时，测试结果出错的概率最多只有 $2^{-100}$ ，这是一个极小的数：

P(当N不为素数，算法返回yes) ≤ $(1/2)^k$

改进版素性测试算法：

function primality2(N)
Input: Positive integer N
Output: yes/no

Pick positive integers a as a1, a2, ..., ak < N at random
if a^(N-1) ≡ 1 (mod N) for all a1, a2, ..., ak:
    return yes
else:
    return no

素数的随机生成

我们离密码学应用所需要的所有工具就差最后一步了，一个快速生成随机素数的算法。该素数可能有几百位长，因为素数足够多，所以随机生成一个这样的素数就变得相对简单——一个随机的n位长的数字为素数的概率大约是 $1/n$ 。

随机生成一个n位长的素数:

随机选定一个n位长的数N
对N进行素性测试
如果通过测试，输出N；否则重复以上过程

该算法有多快？当随机选定一个N，N是素数的概率最少有 $1/n$ ，所以在每次迭代中，该过程最少有 $1/n$ 的概率停止。从而平均起来，该过程将在 $O(n)$ 次迭代后终止。

图片.png

实际的素数生成算法测试，如上图所示，我们选取 $N ≤ 25 × 10^9$ ，在这个范围内，我们得到大约 $10^9$ 个素数，大约有 $20000$ 个合数通过了素性测试，出错概率大约在 $20000/10^9 = 2 × 10^{-5}$ 。而且随着参与计算的数的位数增加（达到几百位长），出错概率还将更迅速的降低。

我们慢慢会发现很多高效和精妙的实用算法背后都依赖于类似抛硬币般的随机性(chance)，它们输出的正确概率可以相当高，但永远不可能100%。对所有可能的输入，错误概率的上限同样存在，它只依赖于算法自身做出的随机性选择，我们做不到完美，只能将出错限定在某种级别，但这些算法在实际使用中已经绰绰有余了。