算法杂记

作者: tristan_lee | 来源:发表于2019-03-26 16:36 被阅读0次

起源

如今，人们早已习惯了以十进制来书写数字，也早已忘记了古代欧洲将数字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%。对所有可能的输入，错误概率的上限同样存在，它只依赖于算法自身做出的随机性选择，我们做不到完美，只能将出错限定在某种级别，但这些算法在实际使用中已经绰绰有余了。

RSA算法

RSA机制基本完全依赖于数论的知识，RSA算法可以是一个定义在集合{0,1,...N-1}上的双向映射函数(bijection)，加密操作是从一端映射到另一端，而解密操作就是反向映射；如RSA有以下两个重要性质：

图片.png

第一个性质保证了加密操作的合理性，通过加密秘钥e从一端唯一地映射到另一端（明文到密文）
第二个性质保证了解密操作的合理性，通过解密秘钥d实现反向映射（密文到明文）
加密与解密操作都是计算量有限的模的指数运算， $(x^e)^d ≡ x$ mod N （证明略）

RSA安全通信过程

Bob选择他的公钥和私钥

首先随机选取两个不同的大素数p和q
他的公钥是(N, e)，其中N=p·q, e是一个2n位长的数，且与(p-1)(q-1)互素。通常情况下选择e=3，以便能够快速地进行加密操作。
他的密钥是d，d是e模(p-1)(q-1)操作的逆元，由扩展欧几里得算法求得。

Alice想要向Bob发送消息x

她抓获到Bob的公钥(N, e)，将加密消息 $y=x^e$ (mod N)发送给Bob，加密过程可以使用模的指数算法高效地进行
Bob对接收到的消息进行解密，解密过程需要计算 $y^d$ mod N

破解RSA算法的两种可能途径

尝试x的所有可能取值，针对每个可能取值都需要判断 $x^e ≡ y$ mod N是否成立，这个判断过程所需时间是指数级的
另一种选择是尝试分解大整数N，得到N的因子p和q，然后求出e模(p-1)(q-1)操作的逆元d，而我们确信大整数的因子分解是困难的，这恰恰是RSA机制安全性的基石

散列函数族

散列函数的最大特点是散射，并且是均匀的散射；这意味着即便输入数据在某个概率分布上是相当集中的，散列函数也可以将这些输入映射成随机的并且彼此唯一的输出。这主要还是依赖于以素数为模后得到的双向映射(bijection)特性。

算法杂记

起源

大O表示法

数论

欧几里德最大公因数算法

模的除法

素性测试

素数的随机生成

RSA算法

RSA安全通信过程

破解RSA算法的两种可能途径

散列函数族

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读