标题党 之 密码学家用PS3成功预测美国2008大选结果

    昨天,一帮密码学家在网上宣称,他们通过一台PS3成功预测出了2008年大选的结果。但为了不干预事件的进程,他们将放出描述大选结果的文档的md5值。大选结束后,密码学家们会放出该文档,证实他们之前确实成功预测到了这个结果。这份电子文档的md5值为:

3D515DEAD7AA16560ABA3E9DF05CBC80

    你能猜出这背后有什么阴谋诡计吗?

    在字谜界有一个非常有趣的故事。美国大选结果出炉的前一天,某报纸上刊登了一则纵横字谜,正中间的那个最长的单词的提示是:美国新一任总统的名字。字谜爱好者纷纷给报社打电话,说大选结果还没出来,我他妈的咋知道新总统是谁,这背后到底隐藏了什么秘密。第二天,报纸上刊登了字谜的答案,中间那个单词果然就是新总统的名字。这家报社“预测”出了大选的结果。你可能已经想到了,这是一个设计得非常巧妙的字谜。这则纵横字谜有两个答案,每个答案都完全符合所有的提示,只是中间的那个人名字不同。纵横字谜中任一个字母的改变都会引起连锁反应导致很大一片字母的改变,因此要想设计出这样一个字谜是非常困难的。但是,就有这么牛的人设计出来了。
    你相信吗?就有那么牛的人,他居然可以构造出两篇文档,hash出来的md5是完全一样的!比起纵横字谜来,这似乎变得更不可思议,因为一篇文档中任何一处微小的改变都会使原来的md5值面目全非。但是,就有这样一种算法,它可以在短时间内构造出md5发生“碰撞”的情况。这就是前几年炒得沸沸扬扬的“山东大学王小云教授成功破解md5”一事。
    当时的新闻很不负责任,没有几个是说清楚了的。和大多数人想的不同,md5被破解并不是真的md5被破解了,你无法把md5还原为原来的信息(因为md5是多对一、不可逆的),也几乎不可能构造一个字符串具有指定的md5值。但是,王小云教授发现,作为一种验证码,md5已经不再可靠了,因为利用他的发现可以很轻易地构造出md5发生冲突的情况。考虑这样一种情况,你需要在未来的某个时间公开一份秘密文档,但到时候你必须证明这份文档确实就是之前说要公开的那一份。比如,你参加CCTV的垃圾娱乐节目,主持人叫你猜一个充气娃娃的价格,你猜是1000元,然后被干冰吓跑,主持人阴笑着宣布这个充气娃娃的真实价格是998。但制作单位如何证明这个价格确实就是998呢?即使是把真实价格藏在一块遮板后面,也有作假的可能。一种不错的方式就是,预先算出998的md5值,由于md5值是不可逆转的,因此即使公开md5别人也拿它没办法;但这个md5可以起一个验证作用,我在报出998的同时你可以验证998的md5值和刚才给的是不是一样,这样才能确保制作单位没有作假。这就需要md5算法具有很低的碰撞概率。现在看来,这种验证方法也不能相信了,因为人为构造md5冲突的两个原始信息变得越来越容易,你猜价格是A我就说是B,你说是B我就说是A,而A和B的md5是一样的。这样的话,我可以做很多坏事,比如说些什么我能预测股票的走向,我五年前就知道我会和你在一起之类的屁话。从这个意义上说,md5不再安全,它已经被破解了。

消息来源:http://blog.wired.com/27bstroke6/2007/11/cryptographers.html
查看更多:http://www.win.tue.nl/hashclash/Nostradamus/
做人要厚道,转贴请注明出处

趣题:直觉 VS 理性思考 经典概率问题

    各种违反常理的错觉图片和数学事实告诉我们,我们的直觉并不可靠。其实这本身就是一种错觉,它让我们觉得我们的直觉总是不可信的。而事实上,多数情况下我们的直觉都是可信的,而理性的思考反而会带来一些错误。

    我的书桌有8个抽屉,分别用数字1到8编号。每次我拿到一份文件后,我都会把这份文件随机地(概率均等地)放在某一个抽屉中。但我非常粗心,有1/5的概率我会忘了把文件放在抽屉里,最终把这个文件搞丢了。
    现在,我要找一份非常重要的文件(比如GF的处女鉴定书)。我将按顺序打开每一个抽屉,直到找到这份文件为止,或者令人同情地,翻遍了所有抽屉都还没找到这份文件。考虑下面三个问题:

  • 1. 假如我打开了第一个抽屉,发现里面没有我要的文件。这份文件在其余7个抽屉里的概率是多少?
  • 2. 假如我翻遍了前4个抽屉,里面都没有我要的文件。这份文件在剩下的4个抽屉里的概率是多少?
  • 3. 假如我翻遍了前7个抽屉,里面都没有我要的文件。这份文件在最后一个抽屉里的概率是多少?

    你猜一猜这三个概率值是越来越大还是越来越小?你能算出准确的值来吗?

    三个概率值分别是7/9, 2/3和1/3。可能这有点出人意料,这个概率在不断减小;但设身处地地想一下,这也不是没有道理的。这正反映了我们实际生活中的心理状态:假如我肯定我的文件没被搞丢,每次发现抽屉里没有我要的东西时我都会更加坚信它在剩下的抽屉里;但如果我的文件很可能被搞丢了,那每翻过一个抽屉但没找到我的文件时,我就会更加担心。我会越来越担心,感到希望越来越渺茫,直到自己面对着第8个抽屉,呆呆地看着我的最后一丝希望,同时心里想:完了,这下可能是真丢了。

    平均每10份文件就有两份被搞丢,其余8份平均地分给了8个抽屉。假如我把所有搞丢了的文件都找回来了,那么它们应该有2个抽屉那么多。这让我们想到了这样一个有趣的思路:在这8个抽屉后加上两个虚拟抽屉──抽屉9和抽屉10,这两个抽屉专门用来装我丢掉的文件。我甚至可以把题目等价地变为:随机把文件放在10个抽屉里,但找文件时不允许打开最后两个抽屉。当我已经找过n个抽屉但仍没找到指定的文件时,文件只能在剩下的10-n个抽屉里,但我只能寻找剩下的8-n个抽屉,因此所求的概率是(8-n)/(10-n)。当0<=n<=8时,函数是一个递减函数。

参考资料:cut-the-knot
做人要厚道 转贴请注明出处

空间想象力大挑战!Smale球面外翻问题

      

    Smale球面外翻问题(Smale's Sphere Eversion Paradox)是微分拓扑学中的一个非常有趣的问题:在允许与自身相交的情况下,是否有可能无损地、平滑地、不留折痕地把一个球面的内侧翻到外面来。答案是肯定的,并且球面外翻的方法不只一种。上面这段有趣的动画里就演示了球面外翻问题的一种常见解法。你能看出这是怎么变的吗?你能把整个变换过程的每个细节都想清楚吗?你是否能在头脑里清晰地想象出整个过程?你又如何给别人解释这一过程?
    这个小程序可以帮助你观察这个球面外翻过程。你可以拉进拉远,从任意角度观察任一时刻该球面的形状。程序提供了球面透明、只查看半球等实用功能便于你一步一步进行分析。

YouTube链接:http://www.youtube.com/watch?v=R_w4HYXuo9M
了解更多:http://torus.math.uiuc.edu/jms/Papers/isama/color/opt2.htm

Poincaré圆盘模型:一个神奇的双曲世界

    今年恰逢PKU数学文化节十周年,其间开办的很多讲座我都去了。去听讲座的人好像都是数院的,我恐怕是唯一一个中文系的。考虑到我和中文系的MM没有共同话题,因此每一次听讲座时我都会顺便四处打望,看看有没有数院的美女,下来可以和她“交谈”一下。有趣的是我的做法与常人所想的恰好相反:据说数院的已经盯上中文系的MM了,而我一个中文系的竟然反过来去找数院的MM。
    昨天有一个关于非欧几何的讲座,这是目前所有的讲座中最为精彩的一次。讲座里提到了Poincaré的一个双曲几何模型,感觉非常有意思,在这里和大家分享一下。
    在所有的双曲几何模型中,Poincaré的圆盘模型可能是最有趣的一个。这个双曲世界存在于一个有限的平面区域里,整个世界限制在一个单位圆的范围内。这个世界中有两个最重要的物理定律:一,假如某物体X离原点O距离为d,那么该物体的温度为1-d^2;二,物体的大小与温度成正比。这样,假如某个人从这个世界的中心走向边缘,那么他的温度会从1慢慢变成0,同时整个人慢慢变小。他自身大小改变的同时周围的物体也等比例地放大或缩小,而这个世界里的人视野有限,看不见远处的东西,因此他不会觉得自己变小了或者变大了。因此,在这个世界里,物理学家们能够很轻易地发现第一定律,但要发现第二定律则非常具有挑战性,探索第二定律的过程必然很曲折,并且很可能出现哥白尼时代的故事。
    对于我们来说,这个世界是有界的;但对于这个世界中的人来说,这个世界是无穷大的。因为离原点越远,人就越小,于是相对来说他们所看到的空间也就越大。当人的位置趋于边界时,物体大小趋于0,此时的空间将变得无穷大,因此这个世界中的物体永远无法到达边界。同时,离原点越远的话越接近“绝对零度”,这将非常不适宜生物的生存,因此人们大多居住在原点,离原点越远城市规模越小,更远的地方则完全没有开发过,只适合于疯狂的冒险家进行极限运动。于是这个世界中的物理学家很自然地得到这个结论:世界是无穷大的。
    下面就神奇了。现在,考虑某个人想从A点走到B点。如果按照红色的线段直直地走过去,所走的路程并不是最短的,因为这条路线离原点较远。聪明的人会发现,我先往原点方向走一点,然后再到B点去,这样走的路程更短一些。我们猜想,最短路线很可能是一条偏向于原点的弧线(就好像原点把直线段“吸”过去了一样)。之所以产生这种奇怪的现象是因为,离原点越远物体就越小,人的步子也变小了,相对来说实际空间就变大了。因此,对我们来说距离相等的两点,对他们来说离原点越远其实际距离越大。因此,我们有必要重新定义这个双曲世界中“距离”的概念。由于物体大小与1-d^2成正比,因此我们可以定义,如果在离原点距离为d的位置上有一个充分小的位移,在我们看来距离为Δx,那么在这个世界中的实际距离就是Δx/(1-d^2)。这样就可以算出,从A到B的最近路线是一条垂直于边界的圆弧(蓝色的那条)。于是在这个世界中,“直线段”已经不再是我们熟悉的直线段了,而是一条条的弧线(还包括整个圆的直径)。而我们眼中的直线,在他们看来就是曲线。
      
    这个世界中的几何满足欧式几何的前面四个公设,但不满足第五公设。比如,两点确定一条直线,因为过两点的圆弧只有一条垂直于这个世界的边界;而直线可以无限延长,因为离边界越近两点的实际距离越大,你永远走不到尽头。但是,这个世界不满足第五公设。从图2可以看到,过一点可以作无数条直线不与已知直线相交;从图3可以看到,三角形的内角和小于180度。下面这幅图片可以帮助你更好地理解这个双曲模型。这是该平面上的一个三角形剖分,里面的所有三角形都是等边三角形,而且所有这些三角形都是一样大的。你可以看到7个等边三角形共用一个顶点,这说明三角形的内角和小于180度。

      

    另外值得一提的是,这个构想很适合写成一篇科幻小说。记得大刘的那篇科幻吗?一群电子器件诞生在某颗星球的内核,然后探索物理定律,历经重重困难,最终冲破了它们那个世界的“天然外壳”,看到了外面的世界,并相信我们整个宇宙也处于一个更大的星体内。这个双曲几何模型也很适合写出这样的小说来,比如以物理史书的方式叙述从古至今若干个传奇人物的故事,讲述他们是如何从一些奇怪的现象出发,通过各种试验证明自己的猜想,顶住社会各方面的压力,执著地探索宇宙的奥秘。小说中的人物可以带着读者一起进行探索,最后才告诉读者这个宇宙的本质是什么。

Matrix67原创
转贴请注明出处

函数上某一点导数为正,该点邻域不一定形成单增区间

    给出一个连续函数,某一点上的导数为正说明函数在这一点是上升的,换句话说函数从左边充分靠近该点时函数值总小于这个点,从右边靠近该点时函数值总大于这个点。但这并不等于说这一点左右是一个单增区间,也就是说该点左右任意小的邻域内函数都不是单调递增的。你能找出这样的函数来吗?

    昨天数学课上,我学到了一个比较牛B的东西:函数上某一点导数为正,该点邻域不一定形成单增区间。虽然左边的点都比该点低,右边的点都比该点高,但这并不能说明左边和右边各自都是单增的。这样的函数确实存在,而且并不是那种很怪的函数,仅仅是一个简单的初等函数:f(x) = x + 2x^2*sin(1/x)。由于x=0时函数没有定义,我们规定f(0)=0。按照导数的定义,函数在x=0时的导数值为
   Limit[ (f(0+Δx)-f(0))/(Δx-0), Δx->0 ]
= Limit[ f(Δx)/Δx, Δx->0 ]
= Limit[ 1 + 2Δx*sin(1/Δx) , Δx->0 ]
= 1

    这说明函数在x=0处的导数确实是正的。当x≠0时,按照求导法则可以求出f'(x) = 1 – 2*cos(1/x) + 4x*sin(1/x)。当|x|充分小时,最后一项可以忽略不计;此时只要1/x恰好等于2πn (n为整数),那么f'(x)保证是负的。这就告诉我们,x=0左右任意近的位置都存在导数为负的情况,这样不管邻域范围多小总能找到一个函数值在减小的地方。
    其实,看一下f(x)的函数图象,你会立即明白这是怎么回事。这个函数越接近原点抖动频率越快(到原点时“周期”无限小),同时振幅也越小(到原点时振幅为0,这样可以保证导数存在);但这个函数总的来说呈上升趋势。因此,这个函数才有我们前面提到的奇怪性质。