小站会根据您的关注,为您发现更多,

看到喜欢的小站就马上关注吧!

下一站,你会遇见谁的梦想?

小站头像

数学与谜题研究室

RSS 归档

站长

18973人关注
2013 / . 04 / . 18

调查的艺术:把个人隐私变成可以说的秘密

调查的艺术:把个人隐私变成可以说的秘密

如果你在学生会工作,想要了解同学们在考试中舞弊行为的严重程度,你会怎么做呢?一个很简单的办法就是,和每一个同学单独进行谈话:“诚实地告诉我你作弊了吗,我保证不会告诉任何人”。不过,这个“保证”似乎太不给力,几乎不会有人敢诚实作答吧,谁知道这个秘密最终会传到哪儿去呢。有没有什么绝对没有漏洞的保密措施,让每一位同学都能放心地诚实回答问题呢?这次,威武的数学又派上用场了。

一种对敏感信息的调查方法

假定要在 100 位同学中做调查。事先当着所有同学的面制作 100 张小纸条,其中 40 张纸条上写“你作弊了吗”,剩下 60 张纸条上写“你没作弊吗”。然后,和每一位同学进行单独谈话,让他像抓阄那样随机抽取一张小纸条。这位同学将会根据纸条上的问题回答“是”或者“不是”,之后立即把小纸条销毁掉,不让其他任何人知道纸条上的内容。这样一来,每个同学都可以放心地回答“是”或者“不是”了,因为其他人根本不知道他答的是哪个问题。

 

你的工作就是记录有多少人回答“是”,有多少人回答“不是”,不必(也不可能)知道他们各自是针对哪个问题回答的。根据最后统计出来的 100 个回答结果,你就能推算出舞弊学生所占的大致比例了。


如何计算出舞弊学生的比例?

假定有 45 人回答“是”,剩下 55 个人回答“不是”,你如何算出舞弊学生所占的比例呢?不妨把这个比例记作 p,根据全概率公式,下面的等式成立:

 

45/100 = p × (40/100) + (1 - p) × (60/100)

 

这个公式上直观上可以这么理解:记“你作弊了吗”的问卷为问卷 A,“你没作弊吗”的问卷为问卷 B。那么一个人回答“是”的概率等于收到 A 卷的概率乘以作弊的概率,加上收到 B 卷的概率乘以没作弊的概率。一个人回答“是”的概率宏观上就表现为这 100 个人中回答“是”的人数,一个人作弊的概率宏观上也就表现为 100 个人中作弊的人数。

 

我们可以依据上面的式子,解出 p 的值来。当然,这样一次计算出来的 p 是不准确的,因为调查所得到的结果 45 并不一定是理论值。也就是说,固定一个 p,我们可以算出回答“是”的人数的理论值,那么多次调查中回答“是”的人数将在理论值附近波动。换个角度来说,我们可以通过多次调查,取 p 的平均值作为结果就比较准确了。


为什么要取 40 和 60 ?

考虑一个极端情况,我们把 (40, 60) 换为 (50, 50),你会发现,上述等式右边的 p 正好被消掉了,不管 p 是多少,回答“是”的人数的理论值总是 50。这是因为,此时一个人收到 A、B 卷是等可能的,所以他回答“是”或“不是”也是等可能的,所以整体上回答“是”的人数会接近一半。也就是说,我们无法通过实验来测得 p 的值,这是一套毫无意义的问卷。

 

事实上,A、B 卷的数量差越大,结果的误差就会越小。另一个极端情况就是有 100 个 A 卷 0 个 B 卷(或者 100 个 B 卷 0 个 A 卷),假设所有人仍然都说真话,测量结果的准确程度将会达到最大——它就等于实际结果了。

 

但同时,A、B 卷的数量相差太大,又会失去保密的作用,因为大家都会知道你手中的问题多半是哪一个。综合两方面的因素来看,(40, 60) 的确是一个不错的选择。



本文版权属于果壳网(guokr.com),转载请注明出处。商业使用请联系果壳


转自:http://www.guokr.com/article/5500/

2013 / . 02 / . 04

IBM Ponder This 2013年2月谜题

链接:http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/February2013.html

原文:James Tanton tweeted (https://twitter.com/jamestanton/status/293127359291330561) that "16 and 9 are each square numbers, and putting them together, 169, gives another square" and he then asked for other examples.

Our challenge this month is to find integers x, y, and z such that concatenating x^2 and y^2 gives z^2, and that z has at least four consecutive nines.

 

大意就是要找到三个数x, y, z,x^2与y^2的数字拼接起来得到z^2(比如4^2和3^2分别等于16和9,连接得到169等于13^2),同时要求z中包含至少4个连续的9

 

如果做出答案请把答案发邮件提交至 webmaster,也就是ibm ponder this的官方邮箱,不要在这里剧透哦

2013 / . 01 / . 16

泊松分布与美国枪击案

转自阮一峰的网络日志:http://www.ruanyifeng.com/blog/2013/01/poisson_distribution.html

作者: 阮一峰

日期: 2013年1月 8日

去年12月,美国康涅狄格州发生校园枪击案,造成28人死亡。

泊松分布与美国枪击案

资料显示,1982年至2012年,美国共发生62起(大规模)枪击案。其中,2012年发生了7起,是次数最多的一年。

泊松分布与美国枪击案

去年有这么多枪击案,这是巧合,还是表明美国治安恶化了?

前几天,我看到一篇很有趣的文章,使用"泊松分布"(Poisson distribution),判断同一年发生7起枪击案是否巧合。

让我们先通过一个例子,了解什么是"泊松分布"。

泊松分布与美国枪击案

已知某家小杂货店,平均每周售出2个水果罐头。请问该店水果罐头的最佳库存量是多少?

假定不存在季节因素,可以近似认为,这个问题满足以下三个条件:

(1)顾客购买水果罐头是小概率事件。

(2)购买水果罐头的顾客是独立的,不会互相影响。

(3)顾客购买水果罐头的概率是稳定的。

在统计学上,只要某类事件满足上面三个条件,它就服从"泊松分布"。

泊松分布的公式如下:

泊松分布与美国枪击案

各个参数的含义:

  P:每周销售k个罐头的概率。

  X:水果罐头的销售变量。

  k:X的取值(0,1,2,3...)。

  λ:每周水果罐头的平均销售量,是一个常数,本题为2。

根据公式,计算得到每周销量的分布:

泊松分布与美国枪击案

从上表可见,如果存货4个罐头,95%的概率不会缺货(平均每19周发生一次);如果存货5个罐头,98%的概率不会缺货(平均59周发生一次)。

泊松分布与美国枪击案

现在,我们再回过头,来看美国枪击案。

假定它们满足"泊松分布"的三个条件:

  (1)枪击案是小概率事件。

  (2)枪击案是独立的,不会互相影响。

  (3)枪击案的发生概率是稳定的。

显然,第三个条件是关键。如果成立,就说明美国的治安没有恶化;如果不成立,就说明枪击案的发生概率不稳定,正在提高,美国治安恶化。

根据资料,1982--2012年枪击案的分布情况如下:

泊松分布与美国枪击案

计算得到,平均每年发生2起枪击案,所以 λ = 2 。

泊松分布与美国枪击案

上图中,蓝色的条形柱是实际的观察值,红色的虚线是理论的预期值。可以看到,观察值与期望值还是相当接近的。

泊松分布与美国枪击案

我们用"卡方检验"(chi-square test),检验观察值与期望值之间是否存在显著差异。

  卡方统计量 = Σ [ ( 观察值 - 期望值 ) ^ 2 / 期望值 ]

计算得到,卡方统计量等于9.82。查表后得到,置信水平0.90、自由度7的卡方分布临界值为12.017。因此,卡方统计量小于临界值,这表明枪击案的观察值与期望值之间没有显著差异。所以,可以接受"发生枪击案的概率是稳定的"假设,也就是说,从统计学上无法得到美国治安正在恶化的结论。

但是,也必须看到,卡方统计量9.82离临界值很接近,p-value只有0.18。也就是说,对于"美国治安没有恶化"的结论,我们只有82%的把握,还有18%的可能是我们错了,美国治安实际上正在恶化。因此,这就需要看今后两年中,是否还有大量枪击案发生。如果确实发生了,泊松分布就不成立了。

[参考阅读]

  * 泊松分布,by 曹亮吉

  * 卡方分布(PDF文件)

(完)

2013 / . 01 / . 09

【九点半关注】阿瑟·本杰明表演‘数学魔术’

在一场现场表演中,数学魔术师阿瑟本杰明与一组计算者比赛算3位数数字的平方,更演算了一系列高难度的方程式并且猜出观众的生日。他是怎么做到的呢?让他来告诉你吧。
  转自 TEDxSYSU
2012 / . 12 / . 31

跨越千年的RSA算法

数论,数学中的皇冠,最纯粹的数学。早在古希腊时代,人们就开始痴迷地研究数字,沉浸于这个几乎没有任何实用价值的思维游戏中。直到计算机诞生之后,几千年来的数论研究成果突然有了实际的应用,这个过程可以说是最为激动人心的数学话题之一。最近我在《程序员》杂志上连载了《跨越千年的 RSA 算法》,但受篇幅限制,只有一万字左右的内容。其实,从数论到 RSA 算法,里面的数学之美哪里是一万字能扯完的?在写作的过程中,我查了很多资料,找到了很多漂亮的例子,也积累了很多个人的思考,但最终都因为篇幅原因没有加进《程序员》的文章中。今天,我想重新梳理一下线索,把所有值得分享的内容一次性地呈现在这篇长文中,希望大家会有所收获。需要注意的是,本文有意为了照顾可读性而牺牲了严谨性。很多具体内容都仅作了直观解释,一些“显然如此”的细节实际上是需要证明的。如果你希望看到有关定理及其证明的严格表述,可以参见任意一本初等数论的书。把本文作为初等数论的学习读物是非常危险的。最后,希望大家能够积极指出文章中的缺陷,我会不断地做出修改。

======= 更新记录 =======

2012 年 12 月 15 日:发布全文。
2012 年 12 月 18 日:修改了几处表达。

======== 目录 ========

(一)可公度线段
(二)中国剩余定理
(三)扩展的辗转相除
(四)Fermat 小定理
(五)公钥加密的可能性
(六)RSA 算法




(一)可公度线段

Euclid ,中文译作“欧几里得”,古希腊数学家。他用公理化系统的方法归纳整理了当时的几何理论,并写成了伟大的数学著作《几何原本》,因而被后人称作“几何学之父”。有趣的是,《几何原本》一书里并不全讲的几何。全书共有十三卷,第七卷到第十卷所讨论的实际上是数论问题——只不过是以几何的方式来描述的。在《几何原本》中,数的大小用线段的长度来表示,越长的线段就表示越大的数。很多数字与数字之间的简单关系,在《几何原本》中都有对应的几何语言。例如,若数字 a 是数字 b 的整倍数,在《几何原本》中就表达为,长度为 a 的线段可以用长度为 b 的线段来度量。比方说,黑板的长度是 2.7 米,一支铅笔的长度是 18 厘米,你会发现黑板的长度正好等于 15 个铅笔的长度。我们就说,铅笔的长度可以用来度量黑板的长度。如果一张课桌的长度是 117 厘米,那么 6 个铅笔的长度不够课桌长, 7 个铅笔的长度又超过了课桌长,因而我们就无法用铅笔来度量课桌的长度了。哦,当然,实际上课桌长相当于 6.5 个铅笔长,但是铅笔上又没有刻度,我们用铅笔来度量课桌时,怎么知道最终结果是 6.5 个铅笔长呢?因而,只有 a 恰好是 b 的整数倍时,我们才说 b 可以度量 a 。

给定两条长度不同的线段 a 和 b ,如果能够找到第三条线段 c ,它既可以度量 a ,又可以度量 b ,我们就说 a 和 b 是可公度的( commensurable ,也叫做可通约的), c 就是 a 和 b 的一个公度单位。举个例子: 1 英寸和 1 厘米是可公度的吗?历史上,英寸和厘米的换算关系不断在变,但现在,英寸已经有了一个明确的定义: 1 英寸精确地等于 2.54 厘米。因此,我们可以把 0.2 毫米当作单位长度,它就可以同时用于度量 1 英寸和 1 厘米: 1 英寸将正好等于 127 个单位长度, 1 厘米将正好等于 50 个单位长度。实际上, 0.1 毫米、 0.04 毫米 、 (0.2 / 3) 毫米也都可以用作 1 英寸和 1 厘米的公度单位,不过 0.2 毫米是最大的公度单位。

等等,我们怎么知道 0.2 毫米是最大的公度单位?更一般地,任意给定两条线段后,我们怎么求出这两条线段的最大公度单位呢?在《几何原本》第七卷的命题 2 当中, Euclid 给出了一种求最大公度单位的通用算法,这就是后来所说的 Euclid 算法。这种方法其实非常直观。假如我们要求线段 a 和线段 b 的最大公度单位,不妨假设 a 比 b 更长。如果 b 正好能度量 a ,那么考虑到 b 当然也能度量它自身,因而 b 就是 a 和 b 的一个公度单位;如果 b 不能度量 a ,这说明 a 的长度等于 b 的某个整倍数,再加上一个零头。我们不妨把这个零头的长度记作 c 。如果有某条线段能够同时度量 b 和 c ,那么它显然也就能度量 a 。也就是说,为了找到 a 和 b 的公度单位,我们只需要去寻找 b 和 c 的公度单位即可。怎样找呢?我们故技重施,看看 c 是否能正好度量 b 。如果 c 正好能度量 b ,c 就是 b 和 c 的公度单位,从而也就是 a 和 b 的公度单位;如果 c 不能度量 b ,那看一看 b 被 c 度量之后剩余的零头,把它记作 d ,然后继续用 d 度量 c ,并不断这样继续下去,直到某一步没有零头了为止。

跨越千年的RSA算法

我们还是来看一个实际的例子吧。让我们试着找出 690 和 2202 的公度单位。显然, 1 是它们的一个公度单位, 2 也是它们的一个公度单位。我们希望用 Euclid 的算法求出它们的最大公度单位。首先,用 690 去度量 2202 ,结果发现 3 个 690 等于 2070 ,度量 2202 时会有一个大小为 132 的零头。接下来,我们用 132 去度量 690 ,这将会产生一个 690 - 132 × 5 = 30 的零头。用 30 去度量 132 ,仍然会有一个大小为 132 - 30 × 4 = 12 零头。再用 12 去度量 30 ,零头为 30 - 12 × 2 = 6 。最后,我们用 6 去度量 12 ,你会发现这回终于没有零头了。因此, 6 就是 6 和 12 的一个公度单位,从而是 12 和 30 的公度单位,从而是 30 和 132 的公度单位,从而是 132 和 690 的公度单位,从而是 690 和 2202 的公度单位。

跨越千年的RSA算法

我们不妨把 Euclid 算法对 a 和 b 进行这番折腾后得到的结果记作 x 。从上面的描述中我们看出, x 确实是 a 和 b 的公度单位。不过,它为什么一定是最大的公度单位呢?为了说明这一点,下面我们来证明,事实上, a 和 b 的任意一个公度单位一定能够度量 x ,从而不会超过 x 。如果某条长为 y 的线段能同时度量 a 和 b ,那么注意到,它能度量 b 就意味着它能度量 b 的任意整倍数,要想让它也能度量 a 的话,只需而且必需让它能够度量 c 。于是, y 也就能够同时度量 b 和 c ,根据同样的道理,这又可以推出 y 一定能度量 d ……因此,最后你会发现, y 一定能度量 x 。

用现在的话来讲,求两条线段的最大公度单位,实际上就是求两个数的最大公约数——最大的能同时整除这两个数的数。用现在的话来描述 Euclid 算法也会简明得多:假设刚开始的两个数是 a 和 b ,其中 a > b ,那么把 a 除以 b 的余数记作 c ,把 b 除以 c 的余数记作 d ,c 除以 d 余 e , d 除以 e 余 f ,等等等等,不断拿上一步的除数去除以上一步的余数。直到某一次除法余数为 0 了,那么此时的除数就是最终结果。因此, Euclid 算法又有一个形象的名字,叫做“辗转相除法”。

辗转相除法的效率非常高,刚才大家已经看到了,计算 690 和 2202 的最大公约数时,我们依次得到的余数是 132, 30, 12, 6 ,做第 5 次除法时就除尽了。实际上,我们可以大致估计出辗转相除法的效率。第一次做除法时,我们是用 a 来除以 b ,把余数记作 c 。如果 b 的值不超过 a 的一半,那么 c 更不会超过 a 的一半(因为余数小于除数);如果 b 的值超过了 a 的一半,那么显然 c 直接就等于 a - b ,同样小于 a 的一半。因此,不管怎样, c 都会小于 a 的一半。下一步轮到 b 除以 c ,根据同样的道理,所得的余数 d 会小于 b 的一半。接下来, e 将小于 c 的一半, f 将小于 d 的一半,等等等等。按照这种速度递减下去的话,即使最开始的数是上百位的大数,不到 1000 次除法就会变成一位数(如果算法没有提前结束的话),交给计算机来执行的话保证秒杀。用专业的说法就是,辗转相除法的运算次数是对数级别的。

很长一段时间里,古希腊人都认为,任意两条线段都是可以公度的,我们只需要做一遍辗转相除便能把这个公度单位给找出来。事实真的如此吗?辗转相除法有可能失效吗?我们至少能想到一种可能:会不会有两条长度关系非常特殊的线段,让辗转相除永远达不到终止的条件,从而根本不能算出一个“最终结果”?注意,线段的长度不一定(也几乎不可能)恰好是整数或者有限小数,它们往往是一些根本不能用有限的方式精确表示出来的数。考虑到这一点,两条线段不可公度完全是有可能的。

为了让两条线段辗转相除永远除不尽,我们有一种绝妙的构造思路:让线段 a 和 b 的比值恰好等于线段 b 和 c 的比值。这样,辗转相除一次后,两数的关系又回到了起点。今后每一次辗转相除,余数总会占据除数的某个相同的比例,于是永远不会出现除尽的情况。不妨假设一种最为简单的情况,即 a 最多只能包含一个 b 的长度,此时 c 等于 a - b 。解方程 a / b = b / (a - b) 可以得到 a : b = 1 : (√5 - 1) / 2 ,约等于一个大家非常熟悉的比值 1: 0.618 。于是我们马上得出:成黄金比例的两条线段是不可公度的。

跨越千年的RSA算法

更典型的例子则是,正方形的边长和对角线是不可公度的。让我们画个图来说明这一点。如图,我们试着用辗转相除求出边长 AB 和对角线 AC 的最大公度单位。按照规则,第一步我们应该用 AB 去度量 AC ,假设所得的零头是 EC 。下一步,我们应该用 EC 去度量 AB ,或者说用 EC 去度量 BC (反正正方形各边都相等)。让我们以 EC 为边作一个小正方形 CEFG ,容易看出 F 点将正好落在 BC 上,同时三角形 AEF 和三角形 ABF 将会由于 HL 全等。因此, EC = EF = BF 。注意到 BC 上已经有一段 BF 和 EC 是相等的了,因而我们用 EC 去度量 BC 所剩的零头,也就相当于用 EC 去度量 FC 所剩的零头。结果又回到了最初的局面——寻找正方形的边长和对角线的公度单位。因而,辗转相除永远不会结束。线段 AB 的长度和线段 AC 的长度不能公度,它们处于两个不同的世界中。

跨越千年的RSA算法

如果正方形 ABCD 的边长 1 ,正方形的面积也就是 1 。从上图中可以看到,若以对角线 AC 为边做一个大正方形,它的面积就该是 2 。因而, AC 就应该是一个与自身相乘之后恰好等于 2 的数,我们通常把这个数记作 √2 。《几何原本》的第十卷专门研究不可公度量,其中就有一段 1 和 √2 不可公度的证明,但所用的方法不是我们上面讲的这种,而更接近于课本上的证明:设 √2 = p / q ,其中 p / q 已是最简分数,但推着推着就发现,这将意味着 p 和 q 都是偶数,与最简分数的假设矛盾。

用今天的话来讲, 1 和 √2 不可公度,实际上相当于是说 √2 是无理数。因此,古希腊人发现了无理数,这确实当属不争的事实。奇怪的是,无理数的发现常常会几乎毫无根据地归功于一个史料记载严重不足的古希腊数学家 Hippasus 。根据各种不靠谱的描述, Hippasus 的发现触犯了 Pythagoras (古希腊哲学家)的教条,最后被溺死在了海里。

可公度线段和不可公度线段的概念与有理数和无理数的概念非常接近,我们甚至可以说明这两个概念是等价的——它们之间有一种很巧妙的等价关系。注意到,即使 a 和 b 本身都是无理数, a 和 b 还是有可能被公度的,例如 a = √2 并且 b = 2 · √2 的时候。不过,有一件事我们可以肯定: a 和 b 的比值一定是一个有理数。事实上,可以证明,线段 a 和 b 是可公度的,当且仅当 a / b 是一个有理数。线段 a 和 b 是可公度的,说明存在一个 c 以及两个整数 m 和 n ,使得 a = m · c ,并且 b = n · c 。于是 a / b = (m · c) / (n · c) = m / n ,这是一个有理数。反过来,如果 a / b 是一个有理数,说明存在整数 m 和 n 使得 a / b = m / n ,等式变形后可得 a / m = b / n ,令这个商为 c ,那么 c 就可以作为 a 和 b 的公度单位。

有时候,“是否可以公度”的说法甚至比“是否有理”更好一些,因为这是一个相对的概念,不是一个绝对的概念。当我们遇到生活当中的某个物理量时,我们绝不能指着它就说“这是一个有理的量”或者“这是一个无理的量”,我们只能说,以某某某(比如 1 厘米、 1 英寸、 0.2 毫米或者一支铅笔的长度等等)作为单位来衡量时,这是一个有理的量或者无理的量。考虑到所选用的单位长度本身也是由另一个物理量定义出来的(比如 1 米被定义为光在真空中 1 秒走过的路程的 1 / 299792458 ),因而在讨论一个物理量是否是有理数时,我们讨论的其实是两个物理量是否可以被公度。


(二)中国剩余定理

如果两个正整数的最大公约数为 1 ,我们就说这两个数是互质的。这是一个非常重要的概念。如果 a 和 b 互质,这就意味着分数 a / b 已经不能再约分了,意味着 a × b 的棋盘的对角线不会经过中间的任何交叉点,意味着循环长度分别为 a 和 b 的两个周期性事件一同上演,则新的循环长度最短为 a · b 。

跨越千年的RSA算法

最后一点可能需要一些解释。让我们来举些例子。假如有 1 路和 2 路两种公交车,其中 1 路车每 6 分钟一班,2 路车每 8 分钟一班。如果你刚刚错过两路公交车同时出发的壮景,那么下一次再遇到这样的事情是多少分钟之后呢?当然, 6 × 8 = 48 分钟,这是一个正确的答案,此时 1 路公交车正好是第 8 班, 2 路公交车正好是第 6 班。不过,实际上,在第 24 分钟就已经出现了两车再次同发的情况了,此时 1 路车正好是第 4 班, 2 路车正好是第 3 班。但是,如果把例子中的 6 分钟和 8 分钟分别改成 4 分钟和 7 分钟,那么要想等到两车再次同发,等到第 4 × 7 = 28 分钟是必需的。类似的,假如某一首歌的长度正好是 6 分钟,另一首歌的长度正好是 8 分钟,让两首歌各自循环播放, 6 × 8 = 48 分钟之后你听到的“合声”将会重复,但实际上第 24 分钟就已经开始重复了。但若两首歌的长度分别是 4 分钟和 7 分钟,则必需到第 4 × 7 = 28 分钟之后才有重复,循环现象不会提前发生。

究其原因,其实就是,对于任意两个数,两个数的乘积一定是它们的一个公倍数,但若这两个数互质,则它们的乘积一定是它们的最小公倍数。事实上,我们还能证明一个更强的结论: a 和 b 的最大公约数和最小公倍数的乘积,一定等于 a 和 b 的乘积。在第四节中,我们会给出一个证明。

很多更复杂的数学现象也都跟互质有关。《孙子算经》卷下第二十六问:“今有物,不知其数。三、三数之,剩二;五、五数之,剩三;七、七数之,剩二。问物几何?答曰:二十三。”翻译过来,就是有一堆东西,三个三个数余 2 ,五个五个数余 3 ,七个七个数余 2 ,问这堆东西有多少个?《孙子算经》给出的答案是 23 个。当然,这个问题还有很多其他的解。由于 105 = 3 × 5 × 7 ,因而 105 这个数被 3 除、被 5 除、被 7 除都能除尽。所以,在 23 的基础上额外加上一个 105 ,得到的 128 也是满足要求的解。当然,我们还可以在 23 的基础上加上 2 个 105 ,加上 3 个 105 ,等等,所得的数都满足要求。除了形如 23 + 105n 的数以外,还有别的解吗?没有了。事实上,不管物体总数除以 3 的余数、除以 5 的余数以及除以 7 的余数分别是多少,在 0 到 104 当中总存在唯一解;在这个解的基础上再加上 105 的整倍数后,可以得到其他所有的正整数解。后人将其表述为“中国剩余定理”:给出 m 个两两互质的整数,它们的乘积为 P ;假设有一个未知数 M ,如果我们已知 M 分别除以这 m 个数所得的余数,那么在 0 到 P - 1 的范围内,我们可以唯一地确定这个 M 。这可以看作是 M 的一个特解。其他所有满足要求的 M ,则正好是那些除以 P 之后余数等于这个特解的数。注意,除数互质的条件是必需的,否则结论就不成立了。比如说,在 0 到 7 的范围内,除以 4 余 1 并且除以 2 也余 1 的数有 2 个,除以 4 余 1 并且除以 2 余 0 的数则一个也没有。

从某种角度来说,中国剩余定理几乎是显然的。让我们以两个除数的情况为例,来说明中国剩余定理背后的直觉吧。假设两个除数分别是 4 和 7 。下表显示的就是各自然数除以 4 和除以 7 的余数情况,其中 x mod y 表示 x 除以 y 的余数,这个记号后面还会用到。

i012345678910111213141516171819
i mod 401230123012301230123
i mod 701234560123456012345
i2021222324252627282930313233343536373839
i mod 401230123012301230123
i mod 760123456012345601234

i mod 4 的值显然是以 4 为周期在循环, i mod 7 的值显然是以 7 为周期在循环。由于 4 和 7 是互质的,它们的最小公倍数是 4 × 7 = 28 ,因而 (i mod 4, i mod 7) 的循环周期是 28 ,不会更短。因此,当 i 从 0 增加到 27 时, (i mod 4, i mod 7) 的值始终没有出现重复。但是, (i mod 4, i mod 7) 也就只有 4 × 7 = 28 种不同的取值,因而它们正好既无重复又无遗漏地分给了 0 到 27 之间的数。这说明,每个特定的余数组合都在前 28 项中出现过,并且都只出现过一次。在此之后,余数组合将产生长度为 28 的循环,于是每个特定的余数组合都将会以 28 为周期重复出现。这正是中国剩余定理的内容。

中国剩余定理有很多漂亮的应用,这里我想说一个我最喜欢的。设想这样一个场景:总部打算把一份秘密文件发送给 5 名特工,但直接把文件原封不动地发给每个人,很难保障安全性。万一有特工背叛或者被捕,把秘密泄露给了敌人怎么办?于是就有了电影和小说中经常出现的情节:把绝密文件拆成 5 份, 5 名特工各自只持有文件的 1/5 。不过,原来的问题并没有彻底解决,我们只能祈祷坏人窃取到的并不是最关键的文件片段。因此,更好的做法是对原文件进行加密,每名特工只持有密码的 1/5 ,这 5 名特工需要同时在场才能获取文件全文。但这也有一个隐患:如果真的有特工被抓了,当坏人们发现只拿到其中一份密码没有任何用处的同时,特工们也会因为少一份密码无法解开全文而烦恼。此时,你或许会想,是否有什么办法能够让特工们仍然可以恢复原文,即使一部分特工被抓住了?换句话说,有没有什么密文发布方式,使得只要 5 个人中半数以上的人在场就可以解开绝密文件?这样的话,坏人必须要能操纵半数以上的特工才可能对秘密文件造成实质性的影响。这种秘密共享方式被称为 (3, 5) 门限方案,意即 5 个人中至少 3 人在场才能解开密文。

利用中国剩余定理,我们可以得到一种巧妙的方案。回想中国剩余定理的内容:给定 m 个两两互质的整数,它们的乘积为 P ;假设有一个未知数 M ,如果我们已知 M 分别除以这 m 个数所得的余数,那么在 0 到 P - 1 的范围内,我们可以唯一地确定这个 M 。我们可以想办法构造这样一种情况, n 个数之中任意 m 个的乘积都比 M 大,但是任意 m - 1 个数的乘积就比 M 小。这样,任意 m 个除数就能唯一地确定 M ,但 m - 1 个数就不足以求出 M 来。 Mignotte 门限方案就用到了这样一个思路。我们选取 n 个两两互质的数,使得最小的 m 个数的乘积比最大的 m - 1 个数的乘积还大。例如,在 (3, 5) 门限方案中,我们可以取 53 、 59 、 64 、 67 、 71 这 5 个数,前面 3 个数乘起来得 200128 ,而后面两个数相乘才得 4757 。我们把文件的密码设为一个 4757 和 200128 之间的整数,比如 123456 。分别算出 123456 除以上面那 5 个数的余数,得到 19 、 28 、 0 、 42 、 58 。然后,把 (53, 19) 、 (59, 28) 、 (64, 0) 、 (67, 42) 、 (71, 58) 分别告诉 5 名特工,也就是说特工 1 只知道密码除以 53 余 19 ,特工 2 只知道密码除以 59 余 28 ,等等。这样,根据中国剩余定理,任意 3 名特工碰头后就可以唯一地确定出 123456 ,但根据 2 名特工手中的信息只能得到成百上千个不定解。例如,假设我们知道了 x 除以 59 余 28 ,也知道了 x 除以 67 余 42 ,那么我们只能确定在 0 和 59 × 67 - 1 之间有一个解 913 ,在 913 的基础上加上 59 × 67 的整倍数,可以得到其他满足要求的 x ,而真正的 M 则可以是其中的任意一个数。

不过,为了让 Mignotte 门限方案真正可行,我们还需要一种根据余数信息反推出 M 的方法。换句话说,我们需要有一种通用的方法,能够回答《孙子算经》中提出的那个问题。我们会在下一节中讲到。


(三)扩展的辗转相除

中国剩余定理是一个很基本的定理。很多数学现象都可以用中国剩余定理来解释。背九九乘法口诀表时,你或许会发现,写下 3 × 1, 3 × 2, ..., 3 × 9 ,它们的个位数正好遍历了 1 到 9 所有的情况。 7 的倍数、 9 的倍数也是如此,但 2 、 4 、 5 、 6 、 8 就不行。 3 、 7 、 9 这三个数究竟有什么特别的地方呢?秘密就在于, 3 、 7 、 9 都是和 10 互质的。比如说 3 ,由于 3 和 10 是互质的,那么根据中国剩余定理,在 0 到 29 之间一定有这样一个数,它除以 3 余 0 ,并且除以 10 余 1 。它将会是 3 的某个整倍数,并且个位为 1 。同样的,在 0 到 29 之间也一定有一个 3 的整倍数,它的个位是 2 ;在 0 到 29 之间也一定有一个 3 的整倍数,它的个位是 3 ……而在 0 到 29 之间,除掉 0 以外, 3 的整倍数正好有 9 个,于是它们的末位就正好既无重复又无遗漏地取遍了 1 到 9 所有的数字。

这表明,如果 a 和 n 互质,那么 a · x mod n = 1 、 a · x mod n = 2 等所有方程都是有解的。 18 世纪的法国数学家 Étienne Bézout 曾经证明了一个基本上与此等价的定理,这里我们姑且把它叫做“ Bézout 定理”。事实上,我们不但知道上述方程是有解的,还能求出所有满足要求的解来。

我们不妨花点时间,把方程 a · x mod n = b 和中国剩余定理的关系再理一下。寻找方程 a · x mod n = b 的解,相当于寻找一个 a 的倍数使得它除以 n 余 b ,或者说是寻找一个数 M 同时满足 M mod a = 0 且 M mod n = b 。如果 a 和 n 是互质的,那么根据中国剩余定理,这样的 M 一定存在,并且找到一个这样的 M 之后,在它的基础上加减 a · n 的整倍数,可以得到所有满足要求的 M 。因此,为了解出方程 a · x mod n = b 的所有解,我们也只需要解出方程的某个特解就行了。假如我们找到了方程 a · x mod n = b 中 x 的一个解,在这个解的基础上加上或减去 n 的倍数(相当于在整个被除数 a · x 的基础上加上或者减去 a · n 的倍数,这里的 a · x 就是前面所说的 M ),就能得到所有的解了。

更妙的是,我们其实只需要考虑形如 a · x mod n = 1 的方程。因为,如果能解出这样的方程, a · x mod n = 2 、 a · x mod n = 3 也都自动地获解了。假如 a · x mod n = 1 有一个解 x = 100 ,由于 100 个 a 除以 n 余 1 ,自然 200 个 a 除以 n 就余 2 , 300 个 a 除以 n 就余 3 ,等等,等式右边余数不为 1 的方程也都解开了。

让我们尝试求解 115x mod 367 = 1 。注意,由于 115 和 367 是互质的,因此方程确实有解。我们解方程的基本思路是,不断寻找 115 的某个倍数以及 367 的某个倍数,使得它们之间的差越来越小,直到最终变为 1 。由于 367 除以 115 得 3 ,余 22 ,因而 3 个 115 只比 367 少 22 。于是, 15 个 115 就要比 5 个 367 少 110 ,从而 16 个 115 就会比 5 个 367 多 5 。好了,真正巧妙的就在这里了: 16 个 115 比 5 个 367 多 5 ,但 3 个 115 比 1 个 367 少 22 ,两者结合起来,我们便能找到 115 的某个倍数和 367 的某个倍数,它们只相差 2 : 16 个 115 比 5 个 367 多 5 ,说明 64 个 115 比 20 个 367 多 20 ,又考虑到 3 个 115 比 1 个 367 少 22 ,于是 67 个 115 只比 21 个 367 少 2 。现在,结合“少 2 ”和“多 5 ”两个式子,我们就能把差距缩小到 1 了: 67 个 115 比 21 个 367 少 2 ,说明 134 个 115 比 42 个 367 少 4 ,而 16 个 115 比 5 个 367 多 5 ,于是 150 个 115 比 47 个 367 多 1 。这样,我们就解出了一个满足 115x mod 367 = 1 的 x ,即 x = 150 。大家会发现,在求解过程,我们相当于对 115 和 367 做了一遍辗转相除:我们不断给出 115 的某个倍数和 367 的某个倍数,通过辗转对比最近的两个结果,让它们的差距从“少 22 ”缩小到“多 5 ”,再到“少 2 ”、“多 1 ”,其中 22, 5, 2, 1 这几个数正是用辗转相除法求 115 和 367 的最大公约数时将会经历的数。因而,算法的步骤数仍然是对数级别的,即使面对上百位上千位的大数,计算机也毫无压力。这种求解方程 a · x mod n = b 的算法就叫做“扩展的辗转相除法”。

注意,整个算法有时也会以“少 1 ”的形式告终。例如,用此方法求解 128x mod 367 = 1 时,最后会得出 43 个 128 比 15 个 367 少 1 。这下怎么办呢?很简单, 43 个 128 比 15 个 367 少 1 ,但是 367 个 128 显然等于 128 个 367 ,对比两个式子可知, 324 个 128 就会比 113 个 367 多 1 了,于是得到 x = 324 。

最后还有一个问题:我们最终总能到达“多 1 ”或者“少 1 ”,这正是因为一开始的两个数是互质的。如果方程 a · x mod n = b 当中 a 和 n 不互质,它们的最大公约数是 d > 1 ,那么在 a 和 n 之间做辗转相除时,算到 d 就直接终止了。自然,扩展的辗转相除也将在到达“多 1 ”或者“少 1 ”之前提前结束。那怎么办呢?我们有一种巧妙的处理方法:以 d 为单位重新去度量 a 和 n (或者说让 a 和 n 都除以 d ),问题就变成我们熟悉的情况了。让我们来举个例子吧。假如我们要解方程 24 · x mod 42 = 30 ,为了方便后面的解释,我们来给这个方程编造一个背景:说一盒鸡蛋 24 个,那么买多少盒鸡蛋,才能让所有的鸡蛋 42 个 42 个地数最后正好能余 30 个?我们发现 24 和 42 不是互质的,扩展的辗转相除似乎就没有用了。不过没关系。我们找出 24 和 42 的最大公约数,发现它们的最大公约数是 6 。现在,让 24 和 42 都来除以 6 ,分别得到 4 和 7 。由于 6 已经是 24 和 42 的公约数中最大的了,因此把 24 和 42 当中的 6 除掉后,剩下的 4 和 7 就不再有大于 1 的公约数,从而就是互质的了。好了,现在我们把题目改编一下,把每 6 个鸡蛋视为一个新的单位量,比如说“ 1 把”。记住, 1 把鸡蛋就是 6 个鸡蛋。于是,原问题就变成了,每个盒子能装 4 把鸡蛋,那么买多少盒鸡蛋,才能让所有的鸡蛋 7 把 7 把地数,最后正好会余 5 把?于是,方程就变成了 4 · x mod 7 = 5 。由于此时 4 和 7 是互质的了,因而套用扩展的辗转相除法,此方程一定有解。可以解出特解 x = 3 ,在它的基础上加减 7 的整倍数,可以得到其他所有满足要求的 x 。这就是改编之后的问题的解。但是,虽说我们对原题做了“改编”,题目内容本身却完全没变,连数值都没变,只不过换了一种说法。改编后的题目里需要买 3 盒鸡蛋,改编前的题目里当然也是要买 3 盒鸡蛋。 x = 3 ,以及所有形如 3 + 7n 的数,也都是原方程的解。

大家或许已经看到了,我们成功地找到了 24 · x mod 42 = 30 的解,依赖于一个巧合: 24 和 42 的最大公约数 6 ,正好也是 30 的约数。因此,改用“把”作单位重新叙述问题,正好最后的“余 30 个”变成了“余 5 把”,依旧是一个整数。如果原方程是 24 · x mod 42 = 31 的话,我们就没有那么走运了,问题将变成“买多少盒才能让最后数完余 5 又 1/6 把”。这怎么可能呢?我们是整把整把地买,整把整把地数,当然余数也是整把整把的。因此,方程 24 · x mod 42 = 31 显然无解。

综上所述,如果关于 x 的方程 a · x mod n = b 当中的 a 和 n 不互质,那么求出 a 和 n 的最大公约数 d 。如果 b 恰好是 d 的整倍数,那么把方程中的 a 、 n 、 b 全都除以 d ,新的 a 和 n 就互质了,新的 b 也恰好为整数,用扩展的辗转相除求解新方程,得到的解也就是原方程的解。但若 b 不是 d 的整倍数,则方程无解。

扩展的辗转相除法有很多应用,其中一个有趣的应用就是大家小时候肯定见过的“倒水问题”。假如你有一个 3 升的容器和一个 5 升的容器(以及充足的水源),如何精确地取出 4 升的水来?为了叙述简便,我们不妨把 3 升的容器和 5 升的容器分别记作容器 A 和容器 B 。一种解法如下:

1. 将 A 装满,此时 A 中的水为 3 升, B 中的水为 0 升;
2. 将 A 里的水全部倒入 B ,此时 A 中的水为 0 升, B 中的水为 3 升;
3. 将 A 装满,此时 A 中的水为 3 升, B 中的水为 3 升;
4. 将 A 里的水倒入 B 直到把 B 装满,此时 A 中的水为 1 升, B 中的水为 5 升;
5. 将 B 里的水全部倒掉,此时 A 中的水为 1 升, B 中的水为 0 升;
6. 将 A 里剩余的水全部倒入 B ,此时 A 中的水为 0 升, B 中的水为 1 升;
7. 将 A 装满,此时 A 中的水为 3 升, B 中的水为 1 升;
8. 将 A 里的水全部倒入 B ,此时 A 中的水为 0 升, B 中的水为 4 升;

这样,我们就得到 4 升的水了。显然,这类问题可以编出无穷多个来,比如能否用 7 升的水杯和 13 升的水杯量出 5 升的水,能否又用 9 升的水杯和 15 升的水杯量出 10 升的水,等等。这样的问题有什么万能解法吗?有!注意到,前面用 3 升的水杯和 5 升的水杯量出 4 升的水,看似复杂的步骤可以简单地概括为:不断将整杯整杯的 A 往 B 里倒,期间只要 B 被装满就把 B 倒空。由于 3 × 3 mod 5 = 4 ,因而把 3 杯的 A 全部倒进 B 里,并且每装满一个 B 就把水倒掉, B 里面正好会剩下 4 升的水。类似地,用容积分别为 a 和 b 的水杯量出体积为 c 的水,实际上相当于解方程 a · x mod b = c 。如果 c 是 a 和 b 的最大公约数,或者能被它们的最大公约数整除,用扩展的辗转相除便能求出 x ,得到对应的量水方案。特别地,如果两个水杯的容积互质,问题将保证有解。如果 c 不能被 a 和 b 的最大公约数整除,方程就没有解了,怎么办?不用着急,因为很显然,此时问题正好也没有解。比方说 9 和 15 都是 3 的倍数,那我们就把每 3 升的水视作一个单位,于是你会发现,在 9 升和 15 升之间加加减减,倒来倒去,得到的量永远只能在 3 的倍数当中转,绝不可能弄出 10 升的水来。这样一来,我们就给出了问题有解无解的判断方法,以及在有解时生成一种合法解的方法,从而完美地解决了倒水问题。

最后,让我们把上一节留下的一点悬念给补完:怎样求解《孙子算经》中的“今有物,不知其数”一题。已知有一堆东西,三个三个数余 2 ,五个五个数余 3 ,七个七个数余 2 ,问这堆东西有多少个?根据中国剩余定理,由于除数 3 、 5 、 7 两两互质,因而在 0 到 104 之间,该问题有唯一的答案。我们求解的基本思路就是,依次找出满足每个条件,但是又不会破坏掉其他条件的数。我们首先要寻找一个数,它既是 5 的倍数,又是 7 的倍数,同时除以 3 正好余 2 。这相当于是在问, 35 的多少倍除以 3 将会余 2 。于是,我们利用扩展的辗转相除法求解方程 35x mod 3 = 2 。这个方程是一定有解的,因为 5 和 3 、 7 和 3 都是互质的,从而 5 × 7 和 3 也是互质的(到了下一节,这一点会变得很显然)。解这个方程可得 x = 1 。于是, 35 就是我们要找到的数。第二步,是寻找这么一个数,它既是 3 的倍数,又是 7 的倍数,同时除以 5 余 3 。这相当于求解方程 21x mod 5 = 3 ,根据和刚才相同的道理,这个方程一定有解。可以解得 x = 3 ,因此我们要找的数就是 63 。最后,我们需要寻找一个数,它能同时被 3 和 5 整除,但被 7 除余 2 。这相当于求解方程 15x mod 7 = 2 ,解得 x = 2 。我们想要找的数就是 30 。现在,如果我们把 35 、 63 和 30 这三个数加在一起会怎么样?它将会同时满足题目当中的三个条件!它满足“三个三个数余 2 ”,因为 35 除以 3 是余 2 的,而后面两个数都是 3 的整倍数,所以加在一起后除以 3 仍然余 2 。类似地,它满足“五个五个数余 3 ”,因为 63 除以 5 余 3 ,另外两个数都是 5 的倍数。类似地,它也满足“七个七个数余 2 ”,因而它就是原问题的一个解。你可以验证一下, 35 + 63 + 30 = 128 ,它确实满足题目的所有要求!为了得出一个 0 到 104 之间的解,我们在 128 的基础上减去一个 105 ,于是正好得到《孙子算经》当中给出的答案, 23 。

已知 M 除以 m 个两两互质的数之后所得的余数,利用类似的方法总能反解出 M 来。至此,我们也就完成了 Mignotte 秘密共享方案的最后一环。


(四)Fermat 小定理

很多自然数都可以被分解成一些更小的数的乘积,例如 12 可以被分成 4 乘以 3 ,其中 4 还可以继续地被分成 2 乘以 2 ,因而我们可以把 12 写作 2 × 2 × 3 。此时, 2 和 3 都不能再继续分解了,它们是最基本、最纯净的数。我们就把这样的数叫做“质数”或者“素数”。同样地, 2 、 3 、 5 、 7 、 11 、 13 等等都是不可分解的,它们也都是质数。它们是自然数的构件,是自然数世界的基本元素。 12 是由两个 2 和一个 3 组成的,正如水分子是由两个氢原子和一个氧原子组成的一样。只不过,和化学世界不同的是,自然数世界里的基本元素是无限的——质数有无穷多个。

关于为什么质数有无穷多个,古希腊的 Euclid 有一个非常漂亮的证明。假设质数只有有限个,其中最大的那个质数为 p 。现在,把所有的质数全部乘起来,再加上 1 ,得到一个新的数 N 。也就是说, N 等于 2 · 3 · 5 · 7 · … · p + 1 。注意到, N 除以每一个质数都会余 1 ,比如 N 除以 2 就会商 3 · 5 · 7 · … · p 余 1 , N 除以 3 就会商 2 · 5 · 7 · … · p 余 1 ,等等。这意味着, N 不能被任何一个质数整除,换句话说 N 是不能被分解的,它本身就是质数。然而这也不对,因为 p 已经是最大的质数了,于是产生了矛盾。这说明,我们刚开始的假设是错的,质数应该有无穷多个。需要额外说明的一点是,这个证明容易让人产生一个误解,即把头 n 个质数乘起来再加 1 ,总能产生一个新的质数。这是不对的,因为既然我们无法把全部质数都乘起来,那么所得的数就有可能是由那些我们没有乘进去的质数构成的,比如 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30031 ,它可以被分解成 59 × 509 。

从古希腊时代开始,人们就近乎疯狂地想要认识自然数的本质规律。组成自然数的基本元素自然地就成为了一个绝佳的突破口,于是对质数的研究成为了探索自然数世界的一个永久的话题。这就是我们今天所说的“数论”。

用质数理论来研究数,真的会非常方便。 a 是 b 的倍数(或者说 a 能被 b 整除, b 是 a 的约数),意思就是 a 拥有 b 所含的每一种质数,而且个数不会更少。我们举个例子吧,比如说 b = 12 ,它可以被分解成 2 × 2 × 3 , a = 180 ,可以被分解成 2 × 2 × 3 × 3 × 5 。 b 里面有两个 2 ,这不稀罕, a 里面也有两个 2 ; b 里面有一个 3 ,这也没什么, a 里面有两个 3 呢。况且, a 里面还包含有 b 没有的质数, 5 。对于每一种质数, b 里面所含的个数都比不过 a ,这其实就表明了 b 就是 a 的约数。

现在,假设 a = 36 = 2 × 2 × 3 × 3 , b = 120 = 2 × 2 × 2 × 3 × 5 。那么, a 和 b 的最大公约数是多少?我们可以依次考察,最大公约数里面可以包含哪些质数,每个质数都能有多少个。这个最大公约数最多可以包含多少个质数 2 ?显然最多只能包含两个,否则它就不能整除 a 了;这个最大公约数最多可以包含多少个质数 3 ?显然最多只能包含一个,否则它就不能整除 b 了;这个最大公约数最多可以包含多少个质数 5 ?显然一个都不能有,否则它就不能整除 a 了。因此, a 和 b 的最大公约数就是 2 × 2 × 3 = 12 。

在构造 a 和 b 的最小公倍数时,我们希望每种质数在数量足够的前提下越少越好。为了让这个数既是 a 的倍数,又是 b 的倍数,三个 2 是必需的;为了让这个数既是 a 的倍数,又是 b 的倍数,两个 3 是必需的;为了让这个数既是 a 的倍数,又是 b 的倍数,那一个 5 也是必不可少的。因此, a 和 b 的最小公倍数就是 2 × 2 × 2 × 3 × 3 × 5 = 360 。

你会发现, 12 × 360 = 36 × 120 ,最大公约数乘以最小公倍数正好等于原来两数的乘积。这其实并不奇怪。在最大公约数里面,每种质数各有多少个,取决于 a 和 b 当中谁所含的这种质数更少一些。在最小公倍数里面,每种质数各有多少个,取决于 a 和 b 当中谁所含的这种质数更多一些。因此,对于每一种质数而言,最大公约数和最小公倍数里面一共包含了多少个这种质数, a 和 b 里面也就一共包含了多少个这种质数。最大公约数和最小公倍数乘在一起,也就相当于是把 a 和 b 各自所包含的质数都乘了个遍,自然也就等于 a 与 b 的乘积了。这立即带来了我们熟悉的推论:如果两数互质,这两数的乘积就是它们的最小公倍数。

第三节里,我们曾说到,“因为 5 和 3 、 7 和 3 都是互质的,从而 5 × 7 和 3 也是互质的”。利用质数的观点,这很容易解释。两个数互质,相当于是说这两个数不包含任何相同的质数。如果 a 与 c 互质, b 与 c 互质,显然 a · b 也与 c 互质。另外一个值得注意的结论是,如果 a 和 b 是两个不同的质数,则这两个数显然就直接互质了。事实上,只要知道了 a 是质数,并且 a 不能整除 b ,那么不管 b 是不是质数,我们也都能确定 a 和 b 是互质的。我们后面会用到这些结论。

在很多场合中,质数都扮演着重要的角色。 1640 年,法国业余数学家 Pierre de Fermat (通常译作“费马”)发现,如果 n 是一个质数的话,那么对于任意一个数 a , a 的 n 次方减去 a 之后都将是 n 的倍数。例如, 7 是一个质数,于是 27 - 2 、 37 - 3 , 47 - 4 ,甚至 1007 - 100 ,统统都能被 7 整除。但 15 不是质数(它可以被分解为 3 × 5 ),于是 a15 - a 除以 15 之后就可能会出现五花八门的余数了。这个规律在数论研究中是如此基本如此重要,以至于它有一个专门的名字—— Fermat 小定理。作为一个业余数学家, Fermat 发现了很多数论中精彩的结论, Fermat “小”定理只是其中之一。虽然与本文无关,但有一点不得不提:以 Fermat 的名字命名的东西里,最著名的要数 Fermat 大定理了(其实译作“ Fermat 最终定理”更贴切)。如果你没听说过,上网查查,或者看看相关的书籍。千万不要错过与此相关的一系列激动人心的故事。

言归正传。 Fermat 小定理有一个非常精彩的证明。我们不妨以“ 37 - 3 能被 7 整除”为例进行说明,稍后你会发现,对于其他的情况,道理是一样的。首先,让我来解释一下“循环移位”的意思。想象一个由若干字符所组成的字符串,在一块大小刚好合适的 LED 屏幕上滚动显示。比方说, HELLOWORLD 就是一个 10 位的字符串,而我们的 LED 屏幕不多不少正好容纳 10 个字符。刚开始,屏幕上显示 HELLOWORLD 。下一刻,屏幕上的字母 H 将会移出屏幕,但又会从屏幕右边移进来,于是屏幕变成了 ELLOWORLDH 。下一刻,屏幕变成了 LLOWORLDHE ,再下一刻又变成了 LOWORLDHEL 。移动到第 10 次,屏幕又会回到 HELLOWORLD 。在此过程中,屏幕上曾经显示过的 ELLOWORLDH, LLOWORLDHE, LOWORLDHEL, ... ,都是由初始的字符串 HELLOWORLD 通过“循环移位”得来的。现在,考虑所有仅由 A 、 B 、 C 三个字符组成的长度为 7 的字符串,它们一共有 37 个。如果某个字符串循环移位后可以得到另一个字符串,我们就认为这两个字符串属于同一组字符串。比如说, ABBCCCC 和 CCCABBC 就属于同一组字符串,并且该组内还有其他 5 个字符串。于是,在所有 37 个字符串当中,除了 AAAAAAA 、 BBBBBBB 、 CCCCCCC 这三个特殊的字符串以外,其他所有的字符串正好都是每 7 个一组。这说明, 37 - 3 能被 7 整除。

在这个证明过程中,“ 7 是质数”这个条件用到哪里去了?仔细想想你会发现,正因为 7 是质数,所以每一组里才恰好有 7 个字符串。如果字符串的长度不是 7 而是 15 的话,有些组里将会只含 3 个或者 5 个字符串。比方说, ABCABCABCABCABC 所在的组里就只有 3 个字符串,循环移动 3 个字符后,字符串将会和原来重合。

Fermat 小定理有一个等价的表述:如果 n 是一个质数的话,那么对于任意一个数 a ,随着 i 的增加, a 的 i 次方除以 n 的余数将会呈现出长度为 n - 1 的周期性(下表所示的是 a = 3 、 n = 7 的情况)。这是因为,根据前面的结论, an 与 a 的差能够被 n 整除,这说明 an 和 a 分别都除以 n 之后将会拥有相同的余数。这表明,依次计算 a 的 1 次方、 2 次方、 3 次方除以 n 的余数,算到 a 的 n 次方时,余数将会变得和最开始相同。另一方面, ai 除以 n 的余数,完全由 ai-1 除以 n 的余数决定。比方说,假如我们已经知道 33 除以 7 等于 3 余 6 ,这表明 33 里包含 3 个 7 以及 1 个 6 ;因此, 34 里就包含 9 个 7 以及 3 个 6 ,或者说 9 个 7 以及 1 个 18 。为了得到 34 除以 7 的余数,只需要看看 18 除以 7 余多少就行了。可见,要想算出 ai-1 · a 除以 n 的余数,我们不需要完整地知道 ai-1 的值,只需要知道 ai-1 除以 n 的余数就可以了。反正最后都要对乘积取余,相乘之前事先对乘数取余不会对结果造成影响(记住这一点,后面我们还会多次用到)。既然第 n 个余数和第 1 个余数相同,而余数序列的每一项都由上一项决定,那么第 n + 1 个、第 n + 2 个余数也都会跟着和第 2 个、第 3 个余数相同,余数序列从此处开始重复,形成长为 n - 1 的周期。

i123456789101112131415
3i3927812437292187656119683590491771475314411594323478296914348907
3i mod 7326451326451326

需要注意的是, n - 1 并不见得是最小的周期。下表所示的是 2i 除以 7 的余数情况,余数序列确实存在长度为 6 的周期现象,但实际上它有一个更小的周期, 3 。

i123456789101112131415
2i24816326412825651210242048409681921638432768
2i mod 7241241241241241

那么,如果除数 n 不是质数,而是两个质数的乘积(比如 35 ),周期的长度又会怎样呢?让我们试着看看, 3i 除以 35 的余数有什么规律吧。注意到 5 和 7 是两个不同的质数,因而它们是互质的。根据中国剩余定理,一个数除以 35 的余数就可以唯一地由它除以 5 的余数和除以 7 的余数确定出来。因而,为了研究 3i 除以 35 的余数,我们只需要观察 (3i mod 5, 3i mod 7) 即可。由 Fermat 小定理可知,数列 3i mod 5 有一个长为 4 的周期,数列 3i mod 7 有一个长为 6 的周期。 4 和 6 的最小公倍数是 12 ,因此 (3i mod 5, 3i mod 7) 存在一个长为 12 的周期。到了 i = 13 时, (3i mod 5, 3i mod 7) 将会和最开始重复,于是 3i 除以 35 的余数将从此处开始发生循环。

i12345678910111213141516171819202122
3i mod 53421342134213421342134
3i mod 73264513264513264513264
3i mod 353927113329171613412139271133291716134
i23242526272829303132333435363738394041424344
3i mod 52134213421342134213421
3i mod 75132645132645132645132
3i mod 351213927113329171613412139271133291716

类似地,假如某个整数 n 等于两个质数 p 、 q 的乘积,那么对于任意一个整数 a ,写出 ai 依次除以 n 所得的余数序列, p - 1 和 q - 1 的最小公倍数将成为该序列的一个周期。事实上, p - 1 和 q - 1 的任意一个公倍数,比如表达起来最方便的 (p - 1) × (q - 1) ,也将成为该序列的一个周期。这个规律可以用来解释很多数学现象。例如,大家可能早就注意过,任何一个数的乘方,其个位数都会呈现长度为 4 的周期(这包括了周期为 1 和周期为 2 的情况)。其实这就是因为, 10 等于 2 和 5 这两个质数的乘积,而 (2 - 1) × (5 - 1) = 4,因此任意一个数的乘方除以 10 的余数序列都将会产生长为 4 的周期。

i12345678910
3i392781243729218765611968359049
3i的个位3971397139
4i416642561024409616384655362621441048576
4i的个位4646464646
5i5251256253125156257812539062519531259765625
5i的个位5555555555

1736 年,瑞士大数学家 Leonhard Euler (通常译作“欧拉”)对此做过进一步研究,讨论了当 n 是更复杂的数时推导余数序列循环周期的方法,得到了一个非常漂亮的结果:在 1 到 n 的范围内有多少个数和 n 互质(包括 1 在内), a 的 i 次方除以 n 的余数序列就会有一个多长的周期。这个经典的结论就叫做“ Euler 定理”。作为历史上最高产的数学家之一, Euler 的一生当中发现的定理实在是太多了。为了把上述定理和其他的“ Euler 定理”区别开来,有时也称它为“ Fermat - Euler 定理”。这是一个非常深刻的定理,它有一些非常具有启发性的证明方法。考虑到在后文的讲解中这个定理不是必需的,因此这里就不详说了。

这些东西有什么用呢?没有什么用。几千年来,数论一直没有任何实际应用,数学家们研究数论的动力完全来源于数字本身的魅力。不过,到了 1970 年左右,情况有了戏剧性的变化。

有的朋友可能要说了,你怎么赖皮呢,“没有任何实际应用”,那刚才的 Mignotte 秘密共享方案算什么?其实, Mignotte 秘密共享方案已经是很后来的事了。秘密共享本来远没那么复杂,为了使得只要 5 个人中半数以上的人在场就可以解开绝密文件,总部可以把绝密文件锁进一个特殊的机械装置里,装置上有三个一模一样的锁孔,并配有 5 把完全相同且不可复制的钥匙。只有把其中任意 3 把钥匙同时插进钥匙孔并一起转动,才能打开整个装置。把 5 把钥匙分发给 5 名特工,目的就直接达到了。因而,通常情况下我们并不需要动用 Mignotte 秘密共享方案。那么,利用中国剩余定理费尽周折弄出的 Mignotte 秘密共享方案,意义究竟何在呢?这种新的秘密共享方案直到 1983 年才被提出,想必是为了解决某个以前不曾有过的需求。 20 世纪中后期究竟出现了什么?答案便是——计算机网络。锁孔方案只适用于物理世界,不能用于网络世界。为了在网络世界中共享秘密,我们需要一种纯信息层面的、只涉及数据交换的新方法, Mignotte 秘密共享方案才应运而生。

数论知识开始焕发新生,一切都是因为这该死的计算机网络。


(五)公钥加密的可能性

计算机网络的出现无疑降低了交流的成本,但却给信息安全带来了难题。在计算机网络中,一切都是数据,一切都是数字,一切都是透明的。假如你的朋友要给你发送一份绝密文件,你如何阻止第三者在你们的通信线路的中间节点上窃走信息?其中一种方法就是,让他对发送的数据进行加密,密码只有你们两人知道。但是,这个密码又是怎么商定出来的呢?直接叫对方编好密码发给你的话,密码本身会有泄漏的风险;如果让对方给密码加个密再发过来呢,给密码加密的方式仍然不知道该怎么确定。如果是朋友之间的通信,把两人已知的小秘密用作密钥(例如约定密钥为 A 的生日加上 B 的手机号)或许能让人放心许多;但对于很多更常见的情形,比方说用户在邮件服务提供商首次申请邮箱时,会话双方完全没有任何可以利用的公共秘密。此时,我们需要一个绝对邪的办法……如果说我不告诉任何人解密的算法呢?这样的话,我就可以公开加密的方法,任何人都能够按照这种方法对信息进行加密,但是只有我自己才知道怎样给由此得到的密文解密。然后,让对方用这种方法给文件加密传过来,问题不就解决了吗?这听上去似乎不太可能,因为直觉上,知道加密的方法也就知道了解密的方法,只需要把过程反过来做就行了。加密算法和解密算法有可能是不对称的吗?

有可能。小时候我经常在朋友之间表演这么一个数学小魔术:让对方任意想一个三位数,把这个三位数乘以 91 的乘积的末三位告诉我,我便能猜出对方原来想的数是多少。如果对方心里想的数是 123 ,那么对方就计算出 123 × 91 等于 11193 ,并把结果的末三位 193 告诉我。看起来,这么做似乎损失了不少信息,让我没法反推出原来的数。不过,我仍然有办法:只需要把对方告诉我的结果再乘以 11 ,乘积的末三位就是对方刚开始想的数了。你可以验证一下, 193 × 11 = 2123 ,末三位正是对方所想的秘密数字!其实道理很简单, 91 乘以 11 等于 1001 ,而任何一个三位数乘以 1001 后,末三位显然都不变(例如 123 乘以 1001 就等于 123123 )。先让对方在他所想的数上乘以 91 ,假设乘积为 X ;我再在 X 的基础上乘以 11 ,其结果相当于我俩合作把原数乘以了 1001 ,自然末三位又变了回去。然而, X 乘以 11 后的末三位是什么,只与 X 的末三位有关。因此,对方只需要告诉我 X 的末三位就行了,这并不会丢掉信息。站在数论的角度来看,上面这句话有一个更好的解释:反正最后都要取除以 1000 的余数,在中途取一次余数不会有影响(还记得吗,“反正最后都要对乘积取余,相乘之前事先对乘数取余不会对结果造成影响”)。知道原理后,我们可以构造一个定义域和值域更大的加密解密系统。比方说,任意一个数乘以 500000001 后,末 8 位都不变,而 500000001 = 42269 × 11829 ,于是你来乘以 42269 ,我来乘以 11829 ,又一个加密解密不对称的系统就构造好了。这是一件很酷的事情,任何人都可以按照我的方法加密一个数,但是只有我才知道怎么把所得的密文变回去。在现代密码学中,数论渐渐地开始有了自己的地位。

不过,加密和解密的过程不对称,并不妨碍我们根据加密方法推出解密方法来,虽然这可能得费些功夫。比方说,刚才的加密算法就能被破解:猜出对方心里想的数相当于求解形如 91x mod 1000 = 193 的方程,这可以利用扩展的辗转相除法很快求解出来,根本不需要其他的雕虫小技(注意到 91 和 1000 是互质的,根据 Bézout 定理,方程确实保证有解)。为了得到一个可以公开加密钥匙的算法,我们还需要从理论上说服自己,在只知道加密钥匙的情况下构造出解密钥匙是非常非常困难的。

1970 年左右,科学家们开始认真地思考“公钥加密系统”的可能性。 1977 年,来自 MIT 的 Ron Rivest 、 Adi Shamir 和 Leonard Adleman 三个人合写了一篇论文,给出了一种至今仍然安全的公钥加密算法。随后,该算法以三人名字的首字母命名,即 RSA 算法。

RSA 算法为什么会更加安全呢?因为 RSA 算法用到了一种非常犀利的不对称性——大数分解难题。

为了判断一个数是不是质数,最笨的方法就是试除法——看它能不能被 2 整除,如果不能的话再看它能不能被 3 整除,这样不断试除上去。直到除遍了所有比它小的数,都还不能把它分解开来,它就是质数了。但是,试除法的速度太慢了,我们需要一些高效的方法。 Fermat 素性测试就是一种比较常用的高效方法,它基于如下原理: Fermat 小定理对一切质数都成立。回想 Fermat 小定理的内容:如果 n 是一个质数的话,那么对于任意一个数 a , a 的 n 次方减去 a 之后都将是 n 的倍数。为了判断 209 是不是质数,我们随便选取一个 a ,比如 38 。结果发现,38209 - 38 除以 209 余 114 (稍后我们会看到,即使把 209 换成上百位的大数,利用计算机也能很快算出这个余数来),不能被 209 整除。于是, 209 肯定不是质数。我们再举一个例子。为了判断 221 是不是质数,我们随机选择 a ,比如说还是 38 吧。你会发现 38221 - 38 除以 221 正好除尽。那么, 221 是否就一定是质数了呢?麻烦就麻烦在这里:这并不能告诉我们 221 是质数,因为 Fermat 小定理毕竟只说了对一切质数都成立,但没说对其他的数成不成立。万一 221 根本就不是质数,但 a = 38 时碰巧也符合 Fermat 小定理呢?为了保险起见,我们不妨再选一个不同的 a 值。比方说,令 a = 26 ,可以算出 26221 - 26 除以 221 余 169 ,因而 221 果然并不是质数。这个例子告诉了我们,如果运气不好的话,所选的 a 值会让不是质数的数也能骗过检测,虽然这个概率其实并不大。因此,我们通常的做法便是,多选几个不同的 a ,只要有一次没通过测试,被检测的数一定不是质数,如果都通过测试了,则被检测的数很可能是质数。没错, Fermat 素性测试的效率非常高,但它是基于一定概率的,有误报的可能。如果发现某个数 n 不满足 Fermat 小定理,它一定不是质数;但如果发现某个数 n 总能通过 Fermat 小定理的检验,只能说明它有很大的几率是质数。

Fermat 素性测试真正麻烦的地方就是,居然有这么一种极其特殊的数,它不是质数,但对于任意的 a 值,它都能通过测试。这样的数叫做 Carmichael 数,最小的一个是 561 ,接下来的几个则是 1105, 1729, 2465, 2821, 6601, 8911… 虽然不多,但很致命。因此,在实际应用时,我们通常会选用 Miller-Rabin 素性测试算法。这个算法以 Gary Miller 的研究成果为基础,由 Michael Rabin 提出,时间大约是 1975 年。它可以看作是对 Fermat 素性测试的改良。如果选用了 k 个不同的 a 值,那么 Miller-Rabin 素性测试算法出现误判的概率不会超过 1 / 4k ,足以应付很多现实需要了。

有没有什么高效率的、确定性的质数判定算法呢?有,不过这已经是很后来的事情了。 2002 年, Manindra Agrawal 、 Neeraj Kayal 和 Nitin Saxena 发表了一篇重要的论文 PRIMES is in P ,给出了第一个高效判断质数的确定性算法,并以三人名字的首字母命名,叫做 AKS 素性测试。不过,已有的质数判断算法已经做得很好了,因此对于 AKS 来说,更重要的是它的理论意义。

有了判断质数的算法,要想生成一个很大的质数也并不困难了。一种常见的做法是,先选定一串连续的大数,然后去掉其中所有能被 2 整除的数,再去掉所有能被 3 整除的数,再去掉所有能被 5 整除的数……直到把某个范围内(比如说 65000 以内)的所有质数的倍数全都去掉。剩下的数就不多了,利用判断质数的算法对它们一一进行测试,不久便能找出一个质数来。

怪就怪在,我们可以高效地判断一个数是不是质数,我们可以高效地生成一个很大的质数,但我们却始终找不到高效的大数分解方法。任意选两个比较大的质数,比如 19394489 和 27687937 。我们能够很容易计算出 19394489 乘以 27687937 的结果,它等于 536993389579193 ;但是,除了试除法以外,目前还没有什么本质上更有效的方法(也很难找到更有效的方法)能够把 536993389579193 迅速分解成 19394489 乘以 27687937 。这种不对称性很快便成了现代密码学的重要基础。让我们通过一个有趣的例子来看看,大数分解的困难性是如何派上用场的吧。

假如你和朋友用短信吵架,最后决定抛掷硬币来分胜负,正面表示你获胜,反面表示对方获胜。问题来了——两个人如何通过短信公平地抛掷一枚硬币?你可以让对方真的抛掷一枚硬币,然后将结果告诉你,不过前提是,你必须充分信任对方才行。在双方互不信任的情况下,还有办法模拟一枚虚拟硬币吗?在我们生活中,有一个常见的解决方法:考你一道题,比如“明天是否会下雨”、“地球的半径是多少”或者“《新华字典》第 307 页的第一个字是什么”,猜对了就算你赢,猜错了就算你输。不过,上面提到的几个问题显然都不是完全公平的。我们需要一类能快速生成的、很难出现重复的、解答不具技巧性的、猜对猜错几率均等的、具有一个确凿的答案并且知道答案后很容易验证答案正确性的问题。大数分解为我们构造难题提供了一个模板。比方说,让对方选择两个 90 位的大质数,或者三个 60 位的大质数,然后把乘积告诉你。无论是哪种情况,你都会得到一个大约有 180 位的数。你需要猜测这个数究竟是两个质数乘在一起得来的,还是三个质数乘在一起得来的。猜对了就算正面,你赢;猜错了就算反面,对方赢。宣布你的猜测后,让对方公开他原先想的那两个数或者三个数,由你来检查它们是否确实都是质数,乘起来是否等于之前给你的数。

大数分解难题成为了 RSA 算法的理论基础。


(六)RSA 算法

所有工作都准备就绪,下面我们可以开始描述 RSA 算法了。

首先,找两个质数,比如说 13 和 17 。实际使用时,我们会选取大得多的质数。把它们乘在一起,得 221 。再计算出 (13 - 1) × (17 - 1) = 192。根据前面的结论,任选一个数 a ,它的 i 次方除以 221 的余数将会呈现长度为 192 的周期(虽然可能存在更短的周期)。换句话说,对于任意的一个 a,a, a193, a385, a577, ... 除以 221 都拥有相同的余数。注意到, 385 可以写成 11 × 35 ……嘿嘿,这下我们就又能变数学小魔术了。叫一个人随便想一个不超过 221 的数,比如 123 。算出 123 的 11 次方除以 221 的余数,把结果告诉你。如果他的计算是正确的,你将会得到 115 这个数。看上去,我们似乎很难把 115 还原回去,但实际上,你只需要计算 115 的 35 次方,它除以 221 的余数就会变回 123 。这是因为,对方把他所想的数 123 连乘了 11 次,得到了一个数 X ;你再把这个 X 乘以自身 35 次,这相当于你们合作把 123 连乘了 385 次,根据周期性现象,它除以 221 的余数仍然是 123 。然而,计算 35 个 X 连乘时,反正我们要取乘积除以 221 的余数,因此我们不必完整地获知 X 的值,只需要知道 X 除以 221 的余数就够了。因而,让对方只告诉你 X 取余后的结果,不会造成信息的丢失。

不过这一次,只知道加密方法后,构造解密方法就难了。容易看出, 35 之所以能作为解密的钥匙,是因为 11 乘以 35 的结果在数列 193, 385, 577, ... 当中,它除以 192 的余数正好是 1 。因此,攻击者可以求解 11x mod 192 = 1 ,找出满足要求的密钥 x 。但关键是,他怎么知道 192 这个数?要想得到 192 这个数,我们需要把 221 分解成 13 和 17 的乘积。当最初所选的质数非常非常大时,这一点是很难办到的。

根据这个原理,我们可以选择两个充分大的质数 p 和 q ,并算出 n = p · q 。接下来,算出 m = (p - 1)(q - 1) 。最后,找出两个数 e 和 d ,使得 e 乘以 d 的结果除以 m 余 1 。怎么找到这样的一对 e 和 d 呢?很简单。首先,随便找一个和 m 互质的数(这是可以做到的,比方说,可以不断生成小于 m 的质数,直到找到一个不能整除 m 的为止),把它用作我们的 e 。然后,求解关于 d 的方程 e · d mod m = 1(就像刚才攻击者想要做的那样,只不过我们有 m 的值而他没有)。 Bézout 定理将保证这样的 d 一定存在。

好了,现在, e 和 n 就可以作为加密钥匙公之于众, d 和 n 则是只有自己知道的解密钥匙。因而,加密钥匙有时也被称作公钥,解密钥匙有时也被称作私钥。任何知道公钥的人都可以利用公式 c = ae mod n 把原始数据 a 加密成一个新的数 c ;私钥的持有者则可以计算 cd mod n ,恢复出原始数据 a 来。不过这里还有个大问题: e 和 d 都是上百位的大数,怎么才能算出一个数的 e 次方或者一个数的 d 次方呢?显然不能老老实实地算那么多次乘法,不然效率实在太低了。好在,“反复平方”可以帮我们快速计算出一个数的乘方。比方说,计算 a35 相当于计算 a34 · a ,也即 (a17)2 · a ,也即 (a16 · a)2 · a,也即 ((a8)2 · a)2 · a……最终简化为 ((((a2)2)2)2 · a)2 · a ,因而 7 次乘法操作就够了。在简化的过程中, a 的指数以成半的速度递减,因而在最后的式子当中,所需的乘法次数也是对数级别的,计算机完全能够承受。不过,减少了运算的次数,并没有减小数的大小。 a 已经是一个数十位上百位的大数了,再拿 a 和它自己多乘几次,很快就会变成一个计算机内存无法容纳的超级大数。怎么办呢?别忘了,“反正最后都要对乘积取余,相乘之前事先对乘数取余不会对结果造成影响”,因此我们可以在运算过程中边算边取余,每做一次乘法都只取乘积除以 n 的余数。这样一来,我们的每次乘法都是两个 n 以内的数相乘了。利用这些小窍门,计算机才能在足够短的时间里完成 RSA 加密解密的过程。

RSA 算法实施起来速度较慢,因此在运算速度上的任何一点优化都是有益的。利用中国剩余定理,我们还能进一步加快运算速度。我们想要求的是 a35 除以 n 的余数,而 n 是两个质数 p 和 q 的乘积。由于 p 和 q 都是质数,它们显然也就互质了。因而,如果我们知道 a35 分别除以 p 和 q 的余数,也就能够反推出它除以 n 的余数了。因此,在反复平方的过程中,我们只需要保留所得的结果除以 p 的余数和除以 q 的余数即可,运算时的数字规模进一步降低到了 p 和 q 所在的数量级上。到最后,我们再借助“今有物,不知其数”的求解思路,把这两条余数信息恢复成一个 n 以内的数。更神的是,别忘了, ai 除以 p 的余数是以 p - 1 为周期的,因此为了计算 a35 mod p ,我们只需要计算 a35 mod (p-1) mod p 就可以了。类似地,由于余数的周期性现象,计算 a35 mod q 就相当于计算 a35 mod (q-1) mod q 。这样一来,连指数的数量级也减小到了和 p 、 q 相同的水平, RSA 运算的速度会有明显的提升。

需要注意的是, RSA 算法的安全性并不完全等价于大数分解的困难性(至少目前我们还没有证明这一点)。已知 n 和 e 之后,不分解 n 确实很难求出 d 来。但我们并不能排除,有某种非常巧妙的方法可以绕过大数分解,不去求 p 和 q 的值,甚至不去求 m 的值,而直接求出一个满足要求的 d 来。不过,即使考虑到这一点,目前人们也没有破解密钥 d 的好办法。 RSA 算法经受住了实践的考验,并逐渐成为了行业标准。如果 A 、 B 两个人想要建立会话,那么我们可以让 A 先向 B 索要公钥,然后想一个两人今后通话用的密码,用 B 的公钥加密后传给 B ,这将只能由 B 解开。因此,即使窃听者完全掌握了双方约定密码时传递的信息,也无法推出这个密码是多少来。

上述方案让双方在不安全的通信线路上神奇地约定好了密码,一切看上去似乎都很完美了。然而,在这个漂亮的解决方案背后,有一个让人意想不到的、颇有些喜剧色彩的漏洞——中间人攻击。在 A 、 B 两人建立会话的过程中,攻击者很容易在线路中间操纵信息,让 A 、 B 两人误以为他们是在直接对话。让我们来看看这具体是如何操作的吧。建立会话时, A 首先呼叫 B 并索要 B 的公钥,此时攻击者注意到了这个消息。当 B 将公钥回传给 A 时,攻击者截获 B 的公钥,然后把他自己的公钥传给 A 。接下来, A 随便想一个密码,比如说 314159 ,然后用他所收到的公钥进行加密,并将加密后的结果传给 B 。 A 以为自己加密时用的是 B 的公钥,但他其实用的是攻击者的公钥。攻击者截获 A 传出来的信息,用自己的私钥解出 314159 ,再把 314159 用 B 的公钥加密后传给 B 。 B 收到信息后不会发现什么异样,因为这段信息确实能用 B 的私钥解开,而且确实能解出正确的信息 314159 。今后, A 、 B 将会用 314159 作为密码进行通话,而完全不知道有攻击者已经掌握了密码。

怎么封住这个漏洞呢?我们得想办法建立一个获取对方公钥的可信渠道。一个简单而有效的办法就是,建立一个所有人都信任的权威机构,由该权威机构来储存并分发大家的公钥。这就是我们通常所说的数字证书认证机构,英文是 Certificate Authority ,通常简称 CA 。任何人都可以申请把自己的公钥放到 CA 上去,不过 CA 必须亲自检查申请者是否符合资格。如果 A 想要和 B 建立会话,那么 A 就直接从 CA 处获取 B 的公钥,这样就不用担心得到的是假的公钥了。

新的问题又出来了:那么,怎么防止攻击者冒充 CA 呢? CA 不但需要向 A 保证“这个公钥确实是 B 的”,还要向 A 证明“我确实就是 CA ”。

把加密钥匙和解密钥匙称作“公钥”和“私钥”是有原因的——有时候,私钥也可以用来加密,公钥也可以用来解密。容易看出,既然 a 的 e 次方的 d 次方除以 n 的余数就回到了 a ,那么当然, a 的 d 次方的 e 次方除以 n 的余数也会变回 a 。于是,我们可以让私钥的持有者计算 a 的 d 次方除以 n 的余数,对原文 a 进行加密;然后公钥的持有者取加密结果的 e 次方除以 n 的余数,这也能恢复出原文 a 。但是,用我自己的私钥加密,然后大家都可以解密,这有什么用处呢?不妨来看看这样“加密”后的效果吧:第一,貌似是最荒谬的,大家都可以用我的公钥解出它所对应的原始文件;第二,很关键的,大家只能查看它背后的原文件,不能越过它去修改它背后的原文件;第三,这样的东西是别人做不出来的,只有我能做出来。

这些性质正好完美地描述出“数字签名”的实质,刚才的 CA 难题迎刃而解。 CA 首先生成一个自己的公钥私钥对,然后把公钥公之于众。之后, CA 对每条发出去的消息都用自己的私钥加个密作为签名,以证明此消息的来源是真实的。收到 CA 的消息后,用 CA 的公钥进行解密,如果能恢复出 CA 的原文,则说明对方一定是正宗的 CA 。因为,这样的消息只有私钥的持有者才能做出来,它上面的签名是别人无法伪造的。至此为止,建立安全的通信线路终于算是有了一个比较完美的方案。

实际应用中,建立完善的安全机制更加复杂。并且,这还不足以解决很多其他形式的网络安全问题。随便哪个简单的社交活动,都包含着非常丰富的协议内涵,在互联网上实现起来并不容易。比方说,如何建立一个网络投票机制?这里面的含义太多了:我们需要保证每张选票确实都来自符合资格的投票人,我们需要保证每个投票人只投了一票,我们需要保证投票人的选票内容不会被泄露,我们需要保证投票人的选票内容不会被篡改,我们还需要让唱票环节足够透明,让每个投票人都确信自己的票被算了进去。作为密码学与协议领域的基本模块, RSA 算法随时准备上阵。古希腊数学家对数字执着的研究,直到今天也仍然绽放着光彩。

  转自 从前有个数
2012 / . 12 / . 31

五个有趣的拓扑变换问题

如果你喜欢上次的空间想象能力挑战,你一定会喜欢 V. V. Prasolov 的 Intuitive Topology 一书。书中的第一章有五个非常经典的“拓扑变换”类谜题,在此与大家分享。注意游戏规则:我们假设所有物体都是用橡胶做成的,可以随意地拉伸、挤压、弯曲,但不允许切断、粘连等任何改变图形本质结构的操作。

1. 能否把左图连续地变形为右图?

五个有趣的拓扑变换问题


2. 能否把左图连续地变形为右图?

五个有趣的拓扑变换问题


3. 左图所示的立体图形表面画有一个圆。能否通过连续变换,把这个圆变到右图所示的位置?

五个有趣的拓扑变换问题


4. 在一个轮胎的表面上打一个洞。能否通过连续变换,把这个轮胎的内表面翻到外面来?

五个有趣的拓扑变换问题


5. 能否把左图连续地变形为右图?

五个有趣的拓扑变换问题














1. 能否把左图连续地变为右图?

五个有趣的拓扑变换问题


答案是可以的,如下图所示:

五个有趣的拓扑变换问题


这意味着,假如人类的身体可以像橡胶人一样任意变形,那么用两手的拇指和食指做成两个套着的圆环之后,我们可以不放开手指,把圆环给解开来。 Algorithmic and Computer Methods for Three-Manifolds 一书里画了一张非常漂亮的示意图:

五个有趣的拓扑变换问题


更加有趣的是,如果仅仅是手腕上多了一块手表,上述方案就不能得逞了:

五个有趣的拓扑变换问题


2. 能否把左图连续地变为右图?

五个有趣的拓扑变换问题


答案是可以的,如下图所示:

五个有趣的拓扑变换问题


3. 左图所示的立体图形表面画有一个圆。能否通过连续变换,把这个圆变到右图所示的位置?

五个有趣的拓扑变换问题


答案是可以的,如下图所示:

五个有趣的拓扑变换问题


4. 在一个轮胎的表面上打一个洞。能否通过连续变换,把这个轮胎的内表面翻到外面来?

五个有趣的拓扑变换问题


答案是可以的。首先,作出如下图所示的连续变换。可以看到,一个表面有洞的轮胎本质上等于两个粘在一起的纸圈!不过,注意纸圈 1 和纸圈 2 的地位不太一样:一个是白色的面(即最初轮胎的内表面)冲外,一个是阴影面(即最初轮胎的外表面)冲外。现在,把纸圈 2 当成原来的纸圈 1 ,把纸圈 1 当成原来的纸圈 2 ,倒着把它们变回轮胎形,轮胎的内外表面也就颠倒过来了。

五个有趣的拓扑变换问题


有趣的是,把轮胎的内表面翻出来之后,轮胎上的“经线”和“纬线”(姑且这么叫吧)也将会颠倒过来:

五个有趣的拓扑变换问题


Wikipedia 上有一个巨帅无比的动画,直接展示出了把一个圆环面的内表面翻到外面来的过程。此动画看着非常上瘾,小心一看就是 10 分钟!

五个有趣的拓扑变换问题


5. 能否把左图连续地变为右图?

五个有趣的拓扑变换问题


答案是可以的。首先,作出如下图所示的连续变换,于是就变成了问题 1 中的图 (a) 。再利用问题 1 的办法,即可变出我们想要的形状来。

五个有趣的拓扑变换问题

  转自 从前有个数
2012 / . 11 / . 20

本华·曼德博──分形之父

 

 



关键词: 分形,本华·曼德博

 

本华·曼德博(1924-2010),是分形几何的创立者。他1924年生于波兰华沙,1936年随全家移居法国巴黎,在那里经历了动荡的二战时期;1948年在加州理工学院获得航空硕士学位;1952年在巴黎大学获得数学博士学位。曾经是普林斯顿、巴黎等大学的访问教授,哈佛大学的“数学实践讲座”的教授,IBM公司的研究成员和会员,耶鲁大学数理科学斯特林教席教授兼荣誉教授。曼德博的研究范围广泛,包括数学物理到金融数学的众多领域,但他最大的成就则是创立了分形几何学。他创造了“分形”这个名词,并且描述了曼德博集 合。他也致力于向大众介绍自己的理论,通过面向普通公众的著作和演讲,使他的研究成果广为人知。

 


原始图形

上图是曼德博集最常见的表现形式,它给我们提供了一种理解周围世界的粗糙程度的方式。这一以数学家本华·曼德博命名的理论观察到,不管是在物理、生物和经济等各种领域中的许多复杂现象,都可以“以严格而有力的定量形式逼近。”

 

Hank Morgan《时代生活图片》Getty Images


1982年的本华·曼德博

曼德博生于华沙,为躲避纳粹而和家人移居法国。在法国,这位年轻的博学者开始了他的研究生涯,一生中在全世界许多最有名望的学术机构中任职,其中包括加利福尼亚理工学院、新泽西州的普林斯顿高等研究院,以及巴黎的法国国家科学研究中心。他的职业生涯大部分时间是作为IBM的研究员度过的,在这期间他首次遇到了那个引领他观察到他最著名的理论的问题。在20世纪60年代,IBM科学家对于有时会干扰他们的传输、引发错误的电子“噪声”非常头痛。虽然他们注意到问题出现在集群中,但无法更进一步地识别问题所在,直到曼德博注意到这些噪声形成了一种模式,对它们越密切地检查,这一模式似乎就越复杂。

 


更进一步

曼德博的观察为他于1982年发表的创造性的著作《自然的分形几何》提供了素材。在这本著作中,他创造了“分形”(fractal)这个词,源于拉丁词fractus,意思是破坏的或者断开的。

 


再进一步

理解曼德博的观察的最佳方式是思考这个让数学家们在年轻时非常着迷的极其简单的问题的答案:“英国的海岸线有多长?”答案取决于你看待海岸线的尺度。绘制地图的人画的线可能是笔直的,但靠近了观察则是弯曲的。越是放大,就会显出越多的曲折,如此重复,无穷无尽。

 


图形形式的主意

作为一种更好地理解曼德博的想法的方式,你可以看看本文相册中的图片,它们从第一张开始,逐渐放大,展露细节,这些都是根据等式$z = z^2 + c$所绘出的。

 


海马的尾巴

曼德博的成果带来的出乎意料的结果之一是这些图片变得非常流行,人们在杯子、T恤和相册封面中运用这些图片。

 


放大海马的尾巴

在曼德博发展起他的理论之前,数学家们拒绝从几何角度尝试理解类似云或海岸线之类的对象,称它们是“可怕的”、“病态的”。

 


双钩

曼德博观察到的复杂性最终会被用于理解除数学对象以外的其他对象。他的观察被用来描述例如证券市场价格变动、混乱的流体动态、地质运动、行星轨道、动物的群体行为、社会经济学模式,甚至音乐等各类事物。

 

编者后记:

 

附一篇《新京报》的纪念文章“别了,分形之父”。

 

原文链接:http://www.time.com/time/photogallery/0,29307,2026200_2200960,00.html
翻  译:白之牙
推荐人:WideBridge

 

2012 / . 11 / . 19

各种版本的过河问题


1.最古老的过河问题

一个农民携带一只狼,一只羊和一棵白菜,要借助一条小船过河。小船上除了农民只能再带狼、羊、白菜中的一样。而农民不在时,狼会吃羊,羊会吃白菜。农民如何过河呢?

 

2.三个道士与三个和尚

三个老道士与三个和尚分别在一条河的两岸,都要到河的对岸去。河中只有一条小船,可容两人。只有一个道士和一个和尚会划船。而且无论在船上或在岸上,道士的数量都不能超过和尚的数量。如何过河?

 

3.四个道士与四个和尚

四个老道士与四个和尚分别在一条河的两岸,都要到河的对岸去。河中只有一条小船,可容两人。只有一个道士和一个和尚会划船。而且无论在船上或在岸上,道士的数量都不能超过和尚的数量。如何过河?

 

4.夫妻过河

(1)两对夫妻要过河,河中只有一条小船,可容两人。两个丈夫都不愿让自己的妻子和另一个男人在一起,除非自己也在场。如何过河?

(2)三对夫妻要过河,河中只有一条小船,可容两人。每个个丈夫都不愿让自己的妻子和另一个男人在一起,除非自己也在场。如何过河?

又,如果是四对夫妻,类似的情况,能够安排过河吗?

 

5.一家人及警察与犯人

现有一条河,共有八个人要过河,分别是爸爸,妈妈,两个儿子,两个女儿,一个警察,一个犯人.现有一条木伐,一次最多载两个人,在这八个人中,有妈妈,爸爸,警察会开船,即这个船上必须有爸爸,妈妈,警察三个中的一个,船才会开动.船过去无法自动回来.并且要避免以下三件事发生, 
1,警察不在犯人会伤害一家六口. 
2,爸爸不在,妈妈会伤害儿子. 
3,妈妈不在,爸爸会伤害女儿. 
应当如何过河?

 

5.一家人过独木桥

有一家五口人要在夜晚过一座独木桥。他们家里的老爷爷行动非常不便,过桥需要12分钟;孩子们的父亲贪吃且不爱运动,体重严重超标,过河需要时间也较长,8分钟;母亲则一直坚持劳作,动作还算敏捷,过桥要6分钟;两个孩子中姐姐需要3分钟,弟弟只要1分钟。当时正是初一夜晚又是阴天,不要说月亮,连一点星光都没有,真所谓伸手不见五指。所幸的是他们有一盏油灯,同时可以有两个人借助灯光过桥。但要命的灯油将尽,这盏灯只能再维持30分钟了!他们焦急万分,该怎样过桥呢?

来自 xkcd.com

 

2012 / . 11 / . 16

喝酒也要用几何:让你看上去喝得更多

把缸子里的水倒进一个细杯子里,水位明显上升了,小孩子们便会手舞足蹈地说,哇,水变多了耶!不过,实际经验告诉我们,成年人似乎也好不到哪儿去。在感知不同形状的物体体积时,人们似乎有一种天生的障碍。


20 世纪,心理学家 Jean Piaget 曾提出了著名的认知发展理论。他发现,小孩儿明显缺乏对物体体积的认知能力。把缸子里的水倒进一个细杯子里,水位明显上升了,小孩子们便会手舞足蹈地说,哇,水变多了耶!

 

不过,实际经验告诉我们,成年人似乎也好不到哪儿去。在感知不同形状的物体体积时,人们似乎有一种天生的障碍。如果用一个横截面积更小的杯子来喝酒,别人或许会真的以为你喝得更多呢!

细而高的杯子看上去就是大些

问题的关键在于半径与体积的关系上:半径扩大到原来的 n 倍,横截面积会扩大到原来的 n 2倍。为了让圆柱体的体积保持不变,它的高度必须要缩小到原来的 1/n 2 。

 

同样地,把一个圆柱体的半径缩小 1/10,看上去似乎是微不足道的;然而,要想让圆柱体的体积保持不变,高度必须要增加到原来的 1/(0.9*0.9),大约是 1.23 倍。从视觉上看,23% 的高度变化要比 10% 的半径变化明显得多,于是乍看上去体积似乎变大了。

左边那个圆柱体的体积看上去是不是更大一些呢?其实,这三个圆柱体的体积是相同的。


杯子上部的空间比你想象的更大

下图是一个酒杯,里面的酒没有倒满。那么,你认为酒的体积占整个酒杯容积的百分之多少?

如果酒杯没有装满的话,你可以少喝多少酒?

 

为了解决这个问题,我们需要知道圆台体积的计算公式:

因此,整个杯子的容积为:

但液面高度只达到整个酒杯高度的 5/6,因此液体体积为:

两者一除,答案简直让人不敢相信:酒的体积竟然只有整个酒杯容积的 73.74%,也就是说这样便能少喝超过 1/4 的酒!

 

可是,为什么仅仅少了 1/6 的高度,就能少喝 1/4 的酒呢?这仍然是半径与体积的关系在作怪。人们总是关注酒杯液面的高度,却忽视了倾斜的杯壁对体积的影响。而酒杯内部是一个立体的空间,这更是放大了这种影响。如果半径以线性的速度增加,横截面积将会以平方级的速度增加,因此,靠近杯口的位置占据的空间比人们想象中的更多。

 

过年了免不了喝酒,不过还是要提醒大家,喝酒伤身,少喝为宜。换一个细一些的杯子,别给自己倒太满,你能少喝不少酒呢。

 

2012 / . 11 / . 16

十天内掌握线性代数:惊人的超速学习实验

 

 



 

最近,我的朋友斯考特·杨(Scott Young)成就了一个惊人的壮举:他在一年之内,完成了传说中的MIT计算机科学课程表的全部33门课,从线性代数到计算理论。最重要的是,他是自学的,观看在线教程讲座,并用实际的考试作自我评估。(到斯考特的FAQ页面,看看他如何完成这个挑战)


按照他的进度,读完一门课程大概只需要1.5个星期。我坚信,能快速掌握复杂信息,对成就卓越事业至关重要。因此,我很自然地问起斯考特,让他给我们分享他的学习奥秘。所幸他答应了。接下来是一份斯考特的详细解说稿,深入剖析他的学习技巧(包括具体例子),展示他如何拿下这MIT挑战。以下时间交给斯考特……


看我怎么驾驭MIT计算机科学的课程


我老想着学快一点,再快一点,并为此兴奋不已。掌握那些重要的学问吧,专业知识与娴熟技艺将是你的职业资本,帮你赚取金钱与享受生活。如果过得好是你的目标,学问能引你到向往之地。


尽管学得更快有很多好处,但大多数人并不愿意学习“如何学习”。大概是因为我们不肯相信有这种好事,在我们看来,学习的速度只取决于好基因与天赋。确实总有些人身怀天赋本钱,但研究表明你的学习方法也很重要。更深层次的知识加工,与时而反复的温故知新,在某些情况下会加倍你的学习效率。是的,“刻意练习”方面的研究表明,没有正确的方法,学习将永远停滞。


今天,我想分享一下学习策略,看看我如何在12个月内完成4年MIT计算机科学的课程。这套策略历经33门课的锤炼,试图弄清楚学得更快的窍门,哪些方法有用,哪些没用。


 

为什么临时抱佛脚没用?


很多学生可能嘲笑我,妄想只花1年的时间学会4年的课程。毕竟,我总可以临时抱佛脚,什么都不懂还能顺利通过考试,不是吗? 很可惜,这个策略在MIT行不通。首先,MIT的考试苛求解决问题的技巧,还经常出些没见过的题型。其次,MIT的课程讲究循序渐进,就算你能死记硬背侥幸通过一次考试,同系列课程的第七课可能就跟不上了。除了死记硬背,我不得不另辟蹊径,加速理解过程。


你能加速理解吗?


“啊哈!”当我们终于想通了,都曾经这样恍然大悟地欢呼过。问题是,大多数人都没有系统地思考。经典的学生求学之路,就是听讲座,读书;如果还不懂,只好枯燥地做大量习题(题海)或重看笔记。没有系统的方法,想更快地理解似乎是天方夜谭。毕竟,顿悟的心理机制,还全然不知。


更糟的是,理解本身,很难称得上是一种开关。它像洋葱的层层表皮,从最肤浅的领会到深层次的理解,逐层巩固对科学革命的认知。给这样的洋葱剥皮,则是常人知之甚少、易被忽略的理解过程。


加速学习的第一步,就是揭秘这个过程。如何洞悉问题,加深你的理解,取决于两个因素:


 



    1. 建立知识联系;

    1. 自我调试排错。


 


知识联系很重要,因为它们是了解一个想法的接入点。我曾纠结于傅里叶变换,直至我意识到它将压强转化为音高、或将辐射转化为颜色。这些见解,常在你懂的和你不懂的之间建立联系。调试排错也同样重要,因为你常常犯错,这些错误究根到底,还是知识残缺,胸无成竹。贫瘠的理解,恰似一个错漏百出的软件程序。如果你能高效地自我调试,必将大大提速学习进程。建立准确的知识联系与调试排错,就足够形成了深刻的问题见解。而机械化技能与死记硬背,通常也只在你对问题的本质有了肯定的直觉以后,才有所裨益。


钻研(The Drilldown Method):你学得更快


经年累月,我完善了一个方法,可以加速逐层增进理解的过程。这个方法至今已被我用于各科目的课题,包括数学、生物学、物理学、经济学与工程学。只需些许修改,它对掌握实用技能也效果很好,比如编程、设计或语言。这个方法的基本结构是:知识面、练习、自省。我将解释每个阶段,让你了解如何尽可能有效率地执行它们,同时给出详细的例子,展示我是怎么应用在实际课程的。


 

第一阶段:知识面覆盖


你不可能组织一场进攻,如果你连一张地形图都没有。因此,深入研习的第一步,就是对你需要学习的内容有个大致印象。若在课堂上,这意味着你要看讲义或读课本;若是自学,你可能要多读几本同主题的书,相互考证。


学生们常犯的一个错误,就是认为这个阶段是最重要的。从很多方面来讲,这个阶段却是效率最低的,因为你每单位时间的投入只换来了最少量的知识回报。我常常加速完成这个阶段,很有好处,这样,我就可以投入更多时间到后面两个阶段。


如果你在看课程讲座的视频,最好是调到1.5x或2x倍速快进。这很容易做到,只要你下载好视频,然后使用播放器(如VLC)的“调速”功能。我用这法子两天内看完了一学期的课程视频。如果你在读一本书,我建议你不要花时间去高亮文本。这样只会让你的知识理解停留在低层次,而从长远来看,也使学习效率低下。更好的方法是,阅读时只偶尔做做笔记,或在读过每个主要章节后写一段落的总结。


这里有个例子,是我上机器视觉这门课时的笔记。


第二阶段:练习


做练习题,能极大地促进你的知识理解。但是,如果你不小心,可能会落入两个效率陷阱:


 



    1. 没有获得即时的反馈:研究表明,如果你想更好地学习,你需要即时的反馈。因此,做题时最好是答案在手,天下我有,每做完一题就对答案,自我审查。没有反馈或反馈迟来的练习,只会严重牵制学习效率;

    1. 题海战术:正如有人以为学习是始于教室终于教室,一些学生也认为大多数的知识理解产自练习题。是的,你总能通过题海战术最终搭起知识框架,但过程缓慢、效率低下。


 


练习题,应该能凸显你需要建立更好直觉的知识领域。一些技巧,比如我将会谈到的费曼技巧(the Feynman technique),对此则相当有效。对于非技术类学科,它更多的是要求你掌握概念而不是解决问题,所以,你常常只需要完成最少量的习题。对这些科目,你最好花更多的时间在第三阶段,形成学科的洞察力。


 

第三阶段:自省


知识面覆盖,与做练习题,是为了让你知道你还有什么不懂。这并不像听上去那么容易,毕竟知之为知之,不知为不知,难矣。你以为你都懂了,其实不是,所以老犯错;或者,你对某综合性学科心里没底,但又看不确切还有哪里不懂。


接下来的技巧,我称之为“费曼技巧”,将帮助你查漏补缺,在求知路上走得更远。当你能准确识别出你不懂的知识点时,这个技巧助你填补知识的缺口,尤其是那些最难以填补的巨大缺口。这个技巧还能两用。即使你真的理解了某个想法,它也能让你关联更多的想法,于是,你可以继续钻研,深化理解。


费曼技巧(The Feynman Technique)


这个技巧的灵感,源于诺贝尔物理奖获得者,理查德·费曼(Richard Feynman)。在他的自传里,他提到曾纠结于某篇艰深的研究论文。他的办法是,仔细审阅这篇论文的辅助材料(supporting material),直到他掌握了相关的知识基础、足以理解其中的艰深想法为止。


费曼技巧,亦同此理。对付一个知识枝节繁杂如发丝、富有内涵的想法,应该分而化之,切成小知识块,再逐个对付,你最终能填补所有的知识缺口,否则,这些缺口将阻挠你理解这个想法。对此,请看这个简短的教程视频


费曼技巧很简单:


 



    1. 拿张白纸;

    1. 在白纸顶部写上你想理解的某想法或某过程;

    1. 用你自己的话解释它,就像你在教给别人这个想法。


 


最要紧的是,对一个想法分而化之,虽然可能重复解释某些已经弄懂的知识点。但你最终会到达一个临界点,无法再解释清楚。那里正是你需要填补的知识缺口。为了填补这个缺口,你可以查课本、问老师、或到互联网搜寻答案。通常来说,一旦你精准地定义了你的不解或误解,找到确切的答案则相对而言更轻松。


我已经使用过这个费曼技巧有数百次,确信它能应付各种各样的学习情境。然而,由于学习情境各有特点,它需要灵活变通,似乎显得难以入门,所以,我将尝试举些不同的例子。


 

对付你完全摸不着头脑的概念


对此,我仍坚持使用费曼技巧,但翻开课本,找到解释这个概念的章节。我先浏览一遍作者的解释,然后仔细地摹仿它,并也试着用自己的思维详述和阐明它。如此一来,当你不能用自己的话写下任何解释时,“引导式”费曼技巧很有用处。这里有个例子,展示我如何理解摄影测量学。


对付各种过程


你也能通过费曼技巧去了解一个你需要用到的过程。审视所有的步骤,不光解释每一步在干什么,还要清楚它是怎么执行的。我常这样理解数学的证明过程、化学的方程式、与生物学的糖酵解过程。这里有个例子,展示我如何想到怎么实现网格加速。


对付各种公式


公式,应该被理解,而不只是死记硬背。因此,当你看到一个公式,却无法理解它的运作机理时,试着用费曼技巧分而化之。这里有个例子,展示我如何理解傅里叶分析方程。


对付需要记忆的内容


费曼技巧,也可以帮你自查是否掌握非技术类学科那些博大精深的知识概念。对于某个主题,如果你能顺利应用费曼技巧,而无需参考原始材料(讲义、课本等),就证明你已经理解和记住它。这里有个例子,展示我如何回忆起经济学中的掠夺性定价概念。


形成更深刻的直觉(Deeper Intuition)


结合做习题,费曼技巧能帮你剥开知识理解的浅层表皮。但它也能帮你钻研下去,走得更远,不只是浅层的理解,而是形成深刻的知识直觉。直观地理解一个想法,并非易事。它看似有些许神秘,但这不是它的本相。一个想法的多数直觉,可作以下归类:


 

类比、可视化、简化


类比:你理解一个想法,是通过确认它与某个更易理解的想法之间的重要相似点;可视化:抽象概念也常成为有用的直觉,只要我们能在脑海为它们构筑画面,即使这个画面只是一个更大更多样化想法的不完全表达;简化:一位著名的科学家曾说过,如果你不能给你的祖母解释一样东西,说明你还没有完全理解它。简化是一门艺术,它加强了基础概念与复杂想法之间的思维联系。


你可以用费曼技巧去激发这些直觉。对于某个想法,一旦你有了大致的理解,下一步就是深入分析,看能不能用以上三种直觉来阐释它。期间,就算是借用已有的意象喻义,也是情有可原的。例如,把复数放到二维空间里理解,很难称得上是新颖的,但它能让你很好地可视化这个概念,让概念在脑海中构图成型。DNA复制,被想象成拉开一条单向拉链,这也不是一个完美的类比,但只要你心里清楚其中的异同,它会变得有用。


学得更快的策略


在这篇文章里,我描述了学习的三个阶段:知识面、练习、与自省。但这可能让你误解,错以为它们总在不同的时期被各自执行,从不重叠或反复。实际上,随着不断地深入理解知识,你可能会周而复始地经历这些阶段。你刚开始读一个章节,只能有个大概的肤浅印象,但做过练习题和建立了直觉以后,你再回过来重新阅读,又会有更深刻的理解,即温故而知新。


钻研吧,即便你不是学生


这个过程不只是适用于学生,也同样有助于学习复杂技能或积累某话题的专业知识。学习像编程或设计的技能,大多数人遵循前两个阶段。他们阅读一本相关的基础书籍,然后在一个项目里历练。然而,你能运用费曼技巧更进一步,更好地锁定与清晰表述你的深刻见解。积累某话题的专业知识,亦同此理;唯一的差别是,你在建立知识面以前,需要搜集一些学习材料,包括相关的研究文章、书籍等。无论如何,只要你弄清楚了想掌握的知识领域,你就钻研下去,深入学习它。

 

  转自 数学的美学世界
2012 / . 11 / . 13

陶哲轩试图解决弱哥德巴赫猜想

 

数世纪悬而未决的猜想有望获得证明

环球科学·数学篇

 

关键词: 数论,数学猜想

 

哥德巴赫猜想是数学界历史最悠久的悬案之一,同时它也是人们最容易领会的问题之一。所谓弱哥德巴赫猜想,是说任何奇数均可分解为三个素数之和(素数就是不能被除了它本身和1之外的任何整数整除的数)。例如:

35 = 19 + 13 + 3 或 77 = 53 + 13 + 11


美国加利福尼亚大学的数学家陶哲轩(Terence Tao)现在正一步一步接近成功证明此猜想。目前他已经证明,任何奇数均可表示为五个素数之和,并且认为很有希望把这一数字降低到三个素数。陶哲轩认为,攻克一道近三个世纪以来让一流数学家束手无策的难题所引起的震撼自不待言,而达到这一梦寐以求的目标,或许也会让数学家获得有助于解决一些实际问题(例如加密敏感数据)的灵感。

 


弱哥德巴赫猜想与其孪生兄弟——强哥德巴赫猜想,都是18世纪德国数学家克里斯蒂安·哥德巴赫(Christian Goldbach)提出来的。强哥德巴赫猜想认为,任何大于2的偶数均可表示为两个素数之和。从其名称可知,如果强猜想为真,那么弱猜想当然也就随之成立:要想将一个奇数表示为三个素数之和,只须将此奇数减去3,然后对所得的偶数运用强哥德巴赫猜想即可。

 

对于直到十八位的所有整数,数学家已经在电脑上考察了这两个哥德巴赫猜想是否成立,其结果是它们全都成立,没有任何例外。而且,越大的整数,将其分解为另外两个数之和的方式也就越多,更不用说分解为三个数了。因此,整数越大,这些猜想为真的可能性也就越大。事实上,数学家己经证明,如果强哥德巴赫猜想存在例外,那么这些例外情况的分布将会随着整数趋于无穷大而越来越稀疏。而对于弱猜想,数学家在20世纪30年代证明的一个经典定理指出,弱猜想至多只有有限个例外情况。换言之,弱哥德巴赫猜想对于“足够大”的整数肯定为真。陶哲轩的工作就是把电脑所验证的对于足够小整数成立的结果与上述对足够大的整数成立的定理结合起来。据他说,他通过“一系列小技巧”改进了早期的计算结果,从而证明只要放宽到五个素数,就可以使这两个各自让弱猜想成立的整数范围出现交集。

 


接下来陶哲轩希望能扩展他的方法,进而证明在所有情况下三个素数就足以让弱猜想成立了。但这不可能对证明强猜想有什么帮助。陶哲轩指出,证明弱猜想要容易得多,其难度与强猜想相比完全不在一个档次上,因为把一个整数分解为三个整数之和时,“所有的数均是素数这种幸运机会将比分解为两个整数时多得多”。因而,在哥德巴赫辞世两百多年之后,我们甚至还没有找到一条路子来搞定他留下的这个老大难问题。

 

编者后记:

 

更多的哥德巴赫猜想的背景资料,可参看中科院贾朝华教授的《从哥德巴赫说开去》

 

原文来源:环球科学•数学篇
作  者:Davide Castelvecchi
翻  译:郭凯声
推荐人:刘明,《环球科学》新媒体经理/资深编辑

 

2012 / . 11 / . 13

为方轮自行车铺路

平时看到的自行车轮子都是圆形的,这样在水平地面上行驶时轮子的轴心也能在水平线上。如果将自行车的车轮换成其他形状(比如方形),自然不可能在平地上平稳行驶,不过如果将水平地面换成其他形状的曲线,平稳行驶还是能做到的。

要让方轮自行车平稳行驶,路面应该做成什么形状呢,你知道吗?

Imgur

Imgur

 

答案以及推导在这里:http://bimania.org/2012/11/13/square-wheels/

2012 / . 11 / . 10

解释离婚的情感动力学数学模型

继男生追女生的数学模型之后又一大作

 

何塞—曼纽尔•雷(Jose-Manuel Rey),从马德里获得数学博士学位,在圣安德鲁斯大学和伦敦大学学院做过一年博士后研究,现为西班牙马德里孔普卢顿大学(Universidad Complutense in Madrid)教授。

 

背景
西方社会的离婚是普遍存在的。它提出了重大的科学和社会学问题,不管是理论上还是解决方式上。学者和问题处理专家认为存在一种情感关系热力学第二定律(second law of thermodynamics for sentimental relationships)。仅有爱是不够的,还需努力来维持。

 

方法论与主要研究发现
我们基于第二定律的简单表述用最优控制理论作为建立情感动力学模型的新方法。我们的分析与社会学数据保持一致。我们揭示出,如果双方有类似的情感属性,最优努力策略将带来长久幸福的婚姻。这一策略因两方面因素的组合而受结构扰动的制约:一是努力差距,因为最优策略通常需要不愉快;一是努力降低到不可持续水平的趋势,因为动力学不稳定。

结论与意义
这些数学事实表明,这一数学模型揭示了可以解释真实情景中配偶关系破裂的基本机制。这个框架里的悖论是一贯想天长地久的婚姻可能会破裂,其可被解释为第二定律的机械结果。

导论
有着浪漫特性的情感关系通常被认为是平衡西方社会幸福生活的基本组成部分。当人们被问及什么是幸福生活的必备要素时,大家通常将“爱”和“亲密关系”摆在首位。很难以想象人类生活的另一方面涉及许多文化、社会、心理、经济问题。但是浪漫关系的原始阶段似乎受化学过程的控制。维持一段情感关系这一问题在一定程度上属于理性判断的范畴。人们通常卷入长期的关系,最典型的就是经过适当考虑的婚姻关系。即使在西方社会,盛行的仍是一夫一妻制。配偶通常声称,他们的目的是维持他们的关系并和睦相处。但欧美大量报道的高离婚率表明了他们计划实施的失败。配偶关系破裂这一现象在美国被视为流行病,“脚踏两只船最终导致离婚”这一统计被媒体和学术报告频繁引用。欧盟27国的离婚率并不比那个数字低,一些欧洲国家也表现出很高的离婚率。此外,未婚配偶的数据则讲述了情感破裂更糟糕的故事。
不同学科的学者们一致认为,婚姻不稳定的主要原因应归结为二十世纪劳动中性别分工的变化所引起的经济力量的释放。然而这一原因并不能解释过去几十年里正在进行的、充斥各处的婚姻破裂。事实上,其并没有理解为什么这么多配偶最终离婚而其他人却没有离婚。这一理解尤为重要,因为婚姻破裂所诱发的社会变化将深刻影响当代西方社会的社会结构以及社会中好人。 
对大多数配偶来说,事实是双方都打断维持长久的关系,并为这一目标而努力以反驳报道出来的高离婚率。本文称这种反驳为失败悖论。根据戈特曼等人(Gottman et al)的研究,(按:戈特曼、默里、斯文森、蒂森等于2002年合著的《婚姻数学——动态非线性模型》(Mathematics of Marriage–Dynamic Nonlinear Models),麻省理工学院出版社)婚姻研究领域急需(数学的)理论。本文旨在缓解这一需求。尤其是本文将为这种失败悖论提供一个一致的解释。
戈特曼等人的研究看上去是迄今为止对配偶关系所进行的唯一数学研究。在实验观察时他们用一对非线性差分方程评估了双方的短期互动,斯特罗伽茨(Strogatz)率先提出了一个配偶互动的简单动态系统模型。我们这里采用不同的动力学方法:配偶被作为一个单位,(不考虑内部互动)他们的情感动力学因其长期和睦共处的意愿而被理性描述。
鉴于配偶分手这一普遍现象,超越关系的具体瑕疵而寻找能解释分手的基础的、确定性机制似乎是和情理的。我们在社会学数据的基础上提出了一个基于最优控制理论能解释同类婚配偶长期关系理性计划的数学模型。如果双方有同类的特征,我们称之为同类混配偶。同类婚配是西方社会情感关系最主要的类型。我们的模型实际上需要同类婚的弱读式。我们通过基于情感互动热力学第二定律(second thermodynamic law for sentimental interaction)的动力学方程描述关系形式的进展。第二定律指出,除非有‘能量’供给,否则一段关系将破裂。广为接受的事实使我们将情感关系建模成控制问题。以努力这一形式存在的能量在控制变量中起着重要作用。最优控制理论已经被广泛地应用于应用科学,如工程学和经济学。我们的最优控制模型为婚姻和亲密关系分析提供了一个全新的数学方法。 
考虑到一些条件的可行性,我们模型表明,维持长期成功的关系是可能的,其取决于动力学平衡轨迹。然而很明显的是,长期关系不可能没有努力。这一模型最引人注目的发现是保持幸福关系的努力水平总是比选择最优推理额努力水平要高。考虑到两种努力水平可容忍的努力差距,维持一段关系是切实可行的。这一数学分析的最主要结果是服从于第二定理的情感动力学本质上是不稳固的。其表明,当努力放松时,情感的日益恶化会轻易地发生。这一分析还确立了能解释渐进退化导致破裂或使人不满的情感生活的机制。
本文的研究结果有助于解答关系失败悖论:根据第二定理,长久幸福关系的优化设计与动态不稳定性保持一致,并有可能不是破裂。这一显著的发现解决了这一失败悖论,因为真实的关系被认为是服从于不稳定性和不确定性的更多原因。这一结果也揭示出如何保持健康有活力的长久关系。
第二部分中为社会学数据所支持的关键证据将作为检验模型发现一致性的框架。失败悖论这一问题也源于社会学证据。这一模型的要素将随着潜在基础的讨论而提出。这一模型分析的主要预言将体现在第三部分,其中一些将表明其与第二部分的事实保持一致。为了方便更流利的讨论,数学术语请见附录。

 

方法论

 

典型事实
马丁和巴姆帕斯(Martin and Bumpass)使用1985年的数据表明,在长达40年的时间里,美国三段婚姻中有两段将以分居或离婚而结束。这一比例可能还没有达到,但是2002年的数据显示其并不低。50%的人在其较早的40年里已经离婚不止一次。2005年发表的数据证明其只比欧盟27国的平均离婚率(44%)稍高。在欧盟一些国家,这一比例甚至高达71%。
如果包括未婚同居,这一数据将上升,尽管基于同居状态的数据不难获得。最近的研究证实,非婚姻同居总体上决不比婚姻稳定。他们报告道,49%的婚前同居在5年分手(10年后分手是62%),然而只有20%的婚姻在5年内以分居或离婚告终(10年后告终是33%)。我们正在观察的这一现象的典型实施可以阐述如下:
1)在爱情关系中存在普遍的失败。
2)典型的配偶相信关系持久的主要因素在于追求幸福。而且大部分人认为,他们自己的关系不会破裂。
失败悖论:打断长久持续的关系如何极可能破裂?
3)配偶分手是一种渐进劣化过程的结果。
4)配偶双方的主观幸福在婚后逐渐降低。

模型
这一模型基于两个主要的假设,也就是下面第二部分要讨论的第二定理和上述第二点所说的配偶关系的长期规划。

 

效用结构:效用与负效用函数的典型形状

情感均衡

长久关系

 

 

分手机制

 


内容来源:http://article.yeeyan.org/view/39879/137341


2012 / . 11 / . 08

博弈入门:从数学游戏开始

个人认为博弈还是很好玩的

转自果壳网:  http://www.guokr.com/article/500/ 

推理剧《古畑任三郎》之“数学家杀人事件”中有这么一个小插曲,这是古畑和数学家之间的一个小游戏:

两个人轮流数数,从1开始数到16,每人每次可以数1到3个数,规定最后数到16的人就输了。我们可爱的古畑大叔并不知道其中诀窍,所以连着输了两局。



但是过了两天,古畑从另一个数学家那里掌握到了诀窍,大致来看是这样的:要让对方数到16的话,自己就必须数到15才行,要数到15你会发现只要数到11即可,因为如果对方数一个数数到到12,你可以连着数3个数直到15;如果对方数2个数数到13,那么你也数两个数数到15;如果对方数三个数数到14,那么你就数一个数数到15。于是只要数到11就能确保自己数到15,那么同样的道理,要数到11就只要数到7,要数到7就要数到3,所以呢,谁先数到3,然后一步步数到7,11,15,最后把16丢给对方那就赢了。



好了,诸如此类的博弈其实更接近一个纯数学问题,这类问题基本上有如下一些共性:


有两名玩家,① 游戏有一个确定的局面,该局面是双方可见的(完全信息);② 规则对游戏双方是相同的(公平的),它规定了哪些操作(策略)是可行的;③ 玩家的操作将使游戏从一个局面确定地走向另一个局面,无随机行动;④ 游戏将会在有限步内结束,此时有唯一的一方成为赢家。

满足上述条件的游戏,称为无偏博弈。


比如说五子棋就不能算是无偏博弈,因为黑棋有禁手的缘故?就算是无禁手的五子棋也不属于无偏博弈。记住第②条,规则对双方是相同的,这意味着两名玩家面对同一局面时,能采取的策略是一样的。换句话说,或者让两个人都可以使用白色和黑色的棋子,或者让棋子只有黑色或只有白色,而且游戏结束条件也必须“无偏差”,你可以规定先使五子连成一条直线的人为赢家,但不能规定黑棋代表一个人,白棋代表另一个人。而这当然不能算是一般意义的五子棋了。同样的道理,凡是有固定颜色的棋子代表某方玩家的,诸如围棋,象棋,陆战旗等都不属于无偏博弈。



无偏博弈在数学上有一定的章法可循。现在来考虑一个和上面古畑先生玩的相同性质的一个“取石子游戏”:桌子上有15个石子,每人每次可以拿去1到3个石子,拿走最后一个石子的人赢。



这个游戏其实不管从推理还是从结论上说都和文章开头的游戏一样,不过这次我们尝试找出更普遍的规律。因为石子的数量总是递减的,所以这个游戏必将在有限步(15步)内结束。我们可以用余下石子的数目来表示局面,于是一共有16个局面。因为规定了拿走最后一个石子的人赢,换句话说当石子个数为0时,就是一个“轮到谁谁就输”的局面,我们通常叫这种局面为必败态。既然0是必败态,那么当局面为1,2,3时,先手就可以采取规则所允许的策略(拿走1个,2个,或是3个)来把局面变成0,于是称1,2,3为胜态;而当局面为4时,不论采取何种策略,局面都将走向胜态,从而4是一个必败态。



现在不用再分析下去我们就知道,一个无偏博弈的局面可以分成两种:必败态和胜态。



胜态一定可以通过某种策略走向必败态;而必败态采取任何策略都将走向胜态。



假如游戏开始时的局面是胜态,那么先手总可以采取适当的策略使胜态走向必败态,然后交给后手。而后手面对必败态,无论他怎么行动,都将走向胜态。假如先手足够聪明的话,先手就让后手永远面临必败态,而自己永远面临胜态,直至游戏结束。这就是一个先手(采取适当策略)能必胜的游戏。反之,如果游戏开始的局面是必败态,那么这就是一个后手必胜的游戏。



在文章的最后,大家来练练手吧,还是刚才的取石子游戏,桌子上有15个石子,每人每次可以拿去1个或3个石子,拿走最后一个石子的人赢,能否列出所有的必败态,找出先手的必胜策略呢?
2012 / . 10 / . 31

那些在网上转烂了的谜题最早都出自哪儿?

大家可以来讨论下问题的答案,或者觉得有其他“转烂了”的谜题,也可以在下面补充

转自果壳网
海盗分金问题、羊与车问题、一块钱哪儿去了⋯⋯或许大家都能背出这些经典问题的答案了,但国内论坛社区里仍然不停地转载这些谜题,标题越来越耸动,参与讨论的人也从未减少。那么,这些问题究竟是从哪里来的呢?
哪国人养鱼(Zebra Puzzle)1. 一条街上有五座不同颜色的房子,每座房子住着不同国籍的人,每个人抽不同的烟,喝不同的饮料,养不同的宠物。
2. 英国人住在红房子里。
3. 西班牙人养狗。
4. 住在绿房子里的人喝咖啡。
5. 乌克兰人喝茶。
6. 绿房子就在乳白色房子的右边。
7. 抽流金岁月(烟名)的人养蜗牛。
8. 抽薄荷烟的住在黄房子里。
9. 住在中间的房子里的人喝牛奶。
10. 挪威人住在第一座房子里。
11. 抽契斯特菲尔德(烟名)的人住在养狐狸的人旁边。
12. 抽薄荷烟的人住在养马的人旁边。
13. 抽好彩(烟名)的人喝橙汁。
14. 日本人抽百乐门(烟名)。
15. 挪威人住在蓝房子隔壁。
那么,谁喝水?谁养斑马?

这个谜题已知的最早出处是 1962 年 12 月 17 日的《生活》(Life)杂志国际版上。1963 年 3 月 25 日,杂志公布了答案和世界各地数百个解决者的名单。这个谜题有无数的变种,其中一个就是网络上流传更广的“哪国人养鱼”。人怕出名猪怕壮,这个叙述繁琐的谜题竟莫名其妙地归功于了 20 世纪最聪明的大脑——爱因斯坦。此题乃“爱因斯坦年幼时所编”的说法广为流传,于是这个谜题也经常被叫做“爱因斯坦谜题”(Einstein‘s Puzzle)。但也有人说,作者其实是路易斯·卡罗尔(Lewis Carroll)。好吧,我们不要管这些追星族了,因为现在没有任何证据证明作者是他们中的任何一个。况且,谜题里的香烟品牌在爱因斯坦小时候还没有出现呢。


海盗分金谜题(Pirate Puzzle)

这是个流传很广的谜题,包含了诸如海盗、金钱、民主之类的流行元素。故事是这样的:有五个理性的海盗 A、B、C、D、E,他们得到了 100 个金币,要进行分赃。海盗世界等级分明,这五个海盗的排名如下:A > B > C > D > E。分赃制度也很民主:首先由等级最高的海盗提出一个分配方案,然后所有海盗(包括提议人)投票表决是否接受。若有半数或半数以上的人同意,则通过提议,否则把提议人扔下船去,由等级第二高的海盗接着提议,以此类推。海盗们考虑的因素如下:首先自己要活下去,然后要得到最多的钱;如果得到的钱反正都一样,他们更乐意把别人害死。

 

对于 A 来说,最佳方案是这样的:A 自己得 98,B 分得 0,C 分得 1,D 分得 0,E 分得 1。解答几乎出乎所有人的意料。一般我们都会把金币分给其他四个海盗以求他们通过提议而保住性命,而解答却告诉我们贪心更好。海盗谜题第一次出现在 1999 年 5 月的《科学美国人》上,文章标题为《海盗谜题》(A Puzzle for Pirate),作者是英国数学家伊恩·斯图尔特(Ian Stewart)。他详细地分析了这个问题,并把海盗的人数推广到 n 个,得到了十分有趣的结论。这个谜题是他从斯蒂芬·奥莫德罗(Stephen M. Omohundro)那儿听说的,据猜测,这个谜题已经流传了至少 10 年。

 

无论从哪个方面来看,这都是一道经典的谜题。在任何博弈论的课程中,都会讲到这个有趣的问题。


一块钱哪儿去了?

三个旅客住进一家旅馆,老板收了他们 30 元,每人 10 元。后来老板决定给他们一些优惠,给服务员 5 元让他退给旅客。很明显老板不会数学,给了个不能被 3 整除的数。聪明的服务员自己偷偷地藏下了 2 元,然后退给每个旅客 1 元。现在每个顾客优惠了 1 元,那么每人交了 9 元,一共交了 27 元,加上服务员的 2 元就是 29 元。可是一开始他们给了老板 30 元,那另外的一元到哪里去了呢?

 

几乎每个人看了之后都会上当,再看一遍之后还是觉得无比正确,再看一遍⋯⋯不少马大虎直到看了答案才明白过来,没想到这么简单啊。上网一搜,标题都是“一年级趣味数学”,自尊心大受打击。

 

这个谜题最早是从哪儿来的呢?在中文网络中最流行的说法是,这个谜题来自一道“新西兰面试题”,真实性等待谣言粉碎机鉴定。事实上,这个问题的历史可能比大家想象的要长得多,它至少可以追溯到加利福尼亚大学 1949 年出版的数学课本中,而最早的出处恐怕已经不得而知了。

 

这个“悖论”的成功得益于 27 + 2 = 29 跟 30 相差无几(若是相差太大必然会引起怀疑),想象力丰富的听众还没弄明白是两个什么东西加了起来,就开始浮想联翩了。谁知道这个算式本身就是错的,2 元已经包括在 27 元里面了,27 - 2 = 25 就是老板手里的钱,并没有少。

 

后来人们给出了一个专属于这个谜题的解答,自嘲当初的失误:“几个月后,其中的两个旅客又住进了这家旅馆,老板收了每人 10 元,一共 20 元。后来他又想给旅客优惠,又是 5 元;然后又是那个服务员,不过这次他扣下了 3 元,还给旅客每人 1 元。现在每个旅客交了 9 元,合起来是 18 元,加上服务员的 3 元,一共 21 元。看,少了的那 1 元在这里”。


不可能完成的谜题(Impossible Puzzle)

有两个不相等的整数 x,y ,它们都大于 1 且和小于 100 ,数学家“和先生”知道这两个数的和,数学家“积先生”知道这两个数的积,他们进行了如下对话:

积先生:我不知道 x 和 y 分别是啥。
和先生:我知道你不知道。
积先生:我现在知道了。
和先生:如果你知道了,那我也知道了。

那么,x 和 y 各是多少?

 

现在知道为什么这叫做不可能完成的谜题了吧,因为光看这几句“废话”我们似乎根本不可能算出 x 和 y 来。1969 年,荷兰数学家汉斯·弗莱登塔尔(Hans Freudenthal)发表了这个谜题,当时被称为“弗莱登塔尔问题”(Freudenthal Problem)。直到 1976 年大卫·斯布罗斯(David Sprows)在《数学杂志》(Mathematics Magazine)上才给出了这个问题的英文版本。1979 年,马丁·加德纳(Martin Gardner)在他的专栏上又一次提到了这个谜题,并称它为“不可能完成的谜题”,之后这个问题就开始大红大紫了。它有无数个变种,并广泛流传。题目描述看似简单,解答却并不简单。图灵奖获得者艾兹赫尔·迪杰斯特拉(Edsger W. Dijkstra)说他在 1978 年曾经解决了这个问题的另一个版本。之前他无数次尝试心算解决它却屡屡入睡,终于在一个无眠的夜晚,花了六个小时,硬是没有用纸和笔,在脑子里解决了那个问题。在证明过程中,他还小小地用了一下哥德巴赫猜想。


失踪的正方形(Missing Square Puzzle)

这个谜题不需要介绍,图已经说明了一切。上面的三角形中少了一个小格,它去了哪里?

 

马丁·加德纳说这是由纽约业余魔术师保罗·嘉理(Paul Curry)在 1953 年发明的,所以也称为“嘉理悖论”(Curry’s Paradox)。所有像嘉理悖论这样的谜题都被叫做“裁剪悖论”(Dissection Paradox)。马丁·加德纳在他的《数学,魔术和秘密》(Mathematics Magic and Mystery)中介绍了另一个类似的悖论,叫做虎珀悖论(Hooper’s Paradox),由数学家威廉·虎珀(William Hooper)在他 1774 年出版的《理性的娱乐》(Rational Recreations)中提出。后来经道格拉斯·罗杰斯(Douglas Rogers)教授调查,虎珀悖论其实最早出自 1769 至 1770 年间法国作者吉尔斯·盖特(Edmé Gilles Guyot)出版的论文集《新奇的物理和数学娱乐》(Nouvelles récréations physiques et mathématiques)里。


史上最难的逻辑谜题(The Hardest Logic Puzzle Ever)

有三个精灵,一个只说真话,一个只说假话,另一个随机说真话或者假话。你可以向这三个精灵问三个是非题,每次问谁都可以,下一个问题可以根据上一个问题的答案来问。你的任务就是判断他们的身份。不幸的是,他们可以听懂你的话,却用他们的方言—— Da 和 Ja ——来回答。你不知道那个表示对,哪个表示错。那么,你应该问哪三个问题呢?

 

这个标题党要归功于麻省理工学院的逻辑学家乔治·史蒂芬·布罗斯(George Stephen Boolos)。1996 年,他在《哈佛哲学评论》(The Harvard Review of Philosophy)发表了同名文章,文章中说这个谜题是由美国数学家雷蒙德·斯穆里安(Raymond Smullyan)发明的。谜题看上去有点绕,其实事情原本没有这么复杂。斯穆里安曾经提出过这个问题的简化版本“骑士与流氓”(Knights and Knaves),里面没有情绪不稳定的第三者,而且他们说的话你也听得懂。后来有人嫌这个不够难,就加了“你听不懂他们的话”这个条件。这个人就是图灵奖获得者约翰·麦卡锡(John McCarthy)。再后来,题目又多出了一个第三者,这样便算得上是“史上最难的逻辑谜题”了。这些相关的谜题都可以在斯穆里安的《这本书叫什么名字》(What is the name of this book)和《舍赫拉查德的谜题》(The Riddle of Scheherazade)中看到。


蒙提霍尔问题(Monty Hall Problem)

假设你参加一个电视游戏节目,节目现场有三扇门,其中一扇门后面是一辆车,另外两扇门后面则是山羊。主持人让你选择其中的一扇门。不妨假设你选择了一号门吧。主持人故意打开了另外一扇门,比如说三号门,让你看见三号门的后面是山羊。然后主持人问你,“你想改变你的选择,换成二号门吗?”这时候,你会怎么做?

 

这个游戏最早出现在美国的电视游戏节目《Let’s make a deal》中。1975 年,史蒂夫·塞尔文(Steve Selvin)教授在《美国统计学家》(American Statistician)上发表文章,把这个问题称为“蒙提霍尔问题”(Monty Hall Problem),因为那个节目主持人就叫蒙提霍尔(Monty Hall)。玛丽莲·沃斯·莎凡特 (Marilyn vos Savant),吉尼斯世界记录认定的最高 IQ 人类,在《Parade》杂志上开了一个名叫“问问玛丽莲”(Ask Marilyn)的专栏,专门回答读者各式各样的问题。1990 年,一个叫 Craig F. Whitaker 的读者给这个专栏寄去这个问题,玛丽莲是这样解答的:“坚持选一号门赢的概率是 1/3,但换成二号门赢的概率是 2/3,因此你应该换一扇门。设想下面的情况,有 100 万扇门,你选了一号门之后,知道内幕的主持人打开了除了二号门之外所有其它的门,你必然会果断地改变选择,是不是?”这个解答发布后,引起了巨大的争议,因为这大大违反了人们的直觉。甚至有不少大学博士去信“纠正”她的错误,理由是:主持人开了一扇门之后,剩下一辆车和一只羊,概率显然变成了 1/2 。他们督促玛丽莲“承认错误”,有人甚至表明自己“为美国的未来担忧”,这些记录至今还留在 玛丽莲的网站 上。大家不妨去参观一下,看看有多少 PhD 栽了跟头。

 

X 人人网小程序,你的青春在这里