改变未来的九大算法(Nine Algorithms that Changed the Future)

九大算法

第二章搜索引擎索引——在世界上最大的草垛中寻针
第三章 Page Rank——让谷歌腾飞的技术
第四章公钥加密——用明信片传输秘密
第五章纠错码——自纠正的错误
第六章图形识别——从经验中学习
第七章数据压缩——有益无害
第八章数据库——追求一致性的征程
第九章数字签名——这个软件究竟由谁编写？
第十章什么可以计算？(可计算性和停机问题)

直到斯坦福大学再也不能承受这一日益受欢迎的服务所需要的带宽，拉里·佩奇和谢尔盖·布林才把公司转移到了如今著名的门洛帕克车库。他们肯定做了些正确的事，因为在他们正式成立公司3个月后，美国《个人计算机杂志》（PC Magazine）就宣布谷歌是1998年美国排名前一百的网站之一。

香农的工作将汉明代码放到了一个更大的理论环境中，并为许多深入发展打下了基础。自此以后，汉明代码被用于一些最早期的计算机中，并仍广泛用于一些特定种类的内存系统中。里德—所罗门（Reed–Solomon）代码是另一类重要的代码。这些代码能被用来纠正每个代码字中的众多错误。[与这里的（7, 4）汉明代码截然不同，汉明代码只能纠正7位数代码字中的一个错误。]里德—所罗门代码基于一个名为有限域代数（finite field algebra）的数学分支，但你可以非常粗略地想象，它结合了阶梯校验和及二维定点把戏的特色。CD、DVD和计算机硬盘中都用到了里德—所罗门代码。

从第一台数字计算机的创造开始，人脑令人印象深刻的能力就吸引并启发了计算机科学家。最早使用计算机模拟人脑的讨论之一，是由英国科学家阿兰·图灵（Alan Turing）发起的，图灵还是一名顶级的数学家、工程师和译电码专家。图灵于1950年发表的经典论文《计算机器与智能》（Computing Machinery and Intelligence），以其对计算机是否能伪装成人类的哲学探讨而闻名于世。

公钥加密中, 用户会生成一对公钥(public key)和私钥(private key). 公钥和私钥之间满足某种数学关系, 但是如果仅仅知道公钥却很难推断出私钥. 整个消息传输过程是这样的, 如果A要向B发送消息M的话

A发送f(private-key-A, M)给B
B收到之后使用f'(public-key-A, f(private-key-A, M))解密出M

当然上面过程可以工作的假设是, B要知道这条消息是从A传输过来的. 但是有时候B并不知道某条消息是谁发送的, 那么这个时候就要求发送者首先发送公钥, 然后才能加密消息. 可是一旦如此, 如果其他人C可以截获AB之间交换的数据的话, 那么C也就可以知道A的公钥, 那么整个过程对C就完全暴露了. 这种应用场景比如https. 所以在这种场景下, 需要AB可以通过某种"加密"方式先产生共享密钥, 然后使用这个共享密钥来做加密传输. 产生共享密钥的方式可以是这样的:

A 选择一个private number(PA'), 然后选择一个public number(PA)
然后A将PA以及f(PA', PA)告诉B. 其中f是一个函数, 从f(PA',PA)以及P很难推断出PA'. 另外还需要一个特性后面说.
B 收到消息之后, 选择一个private number(PB'), 然后计算f(PB', PA)告诉A, 并且使用f(PB', f(PA', PA))作为key
A 收到消息之后, 使用f(PA', f(PB', PA))作为key
为了使得两个key是一致的, 就要求f(PB', f(PA', PA)) = f(PA', f(PB', PA)). 所以也就要求f满足associative.

数字签名使用到了公钥加密. 数字签名是要帮助接收者确定, 所收到的消息确实是来自于某个人X. 对于接收者来说最大的问题是, X的public-key到底是什么. 举个简单的例子,

用户A想上X.com上阅读某条消息M. 这条消息被加密成为f(private-key-X, M)
但是用户A被DNS劫持, 转到了Y.com上. Y.com和X.com看上去一样, 但是消息M替换成为了M'. 同样这条消息被加密成为f(private-key-Y, M')
用户为了阅读消息需要public-key. 于是用户从Y.com拿到了public-key-Y, 解密阅读到了M'.

数字签名实现就是将这些public-key由一些可信机构进行托管. 一些特定组织被正式指认为所谓的根认证机构。VeriSign、GlobalSign和GeoTrust等都是较为知名的根认证机构。在你有要求时，众多根认证机构的联系细节（包括互联网地址和公钥）会预装到浏览器软件中.