精讲《从一到无穷大》-50生日碰撞和数字签名
在上一回加莫夫带着我们讨论了一些有关硬币和扑克牌的概率问题。那么这一回我们还要再来讨论两个跟密码相关的概率问题。
首先我们可以做一个实验，在班级的微信或者QQ群里面，所有的人挨个报上自己的生日，猜一猜有多大的概率会有人在同一天过生日呢？也许有同学会讲这个概率太低了，一年有365天，如果群里有50个人的话，最多只能填满全年的7分之1。所以两个人的生日在同一天的概率实在是太低了。但是事实真的如此吗？其实这是一个著名的问题，称之为生日碰撞。他的结果令许多人惊奇，只要班里有23个人，那么有人生是相同的概率就会超过50%。如果有50个人的话，有人生日相同的概率就超过了97%。
我们来解释一下原因，利用P表示所有人的生日都不在同一天的概率，那么一减P就是至少有两个人生日在同一天的概率。为了方便起见，我们暂时不计算闰年的2月29号。如果班级里只有一个人的话，那么无论这个人的生日在哪一天，都不会有人与他的生日相同。所以生日不同的概率P等于一，而发生生日碰撞的概率一减P等于0。假如班级里有两个人，第一个人的生日在365天中的任意一天，而第二个人的生日不能与第一个人生日相同，就只有364种选择。所以第二个人不与第一个人撞车的概率是365分之364。这个班级两人生日不同的概率就是365分之364。而发生生日碰撞的概率就是一减去365分之364。
如果班级里有三个人，第一个人的生日在365天中的任意一天，第二个人的生日不能与第一个人相同，有364种选择，这个概率是365分之364，第三个人的生日不能与前两个人生日相同，只有363种选择，所以这个概率是365分之363。这样一来，三个人生日都不相同的概率就是365分之364乘以365分之363。而发生生日碰撞的概率就是一减去365分之364乘以365分之363。
按照这样的方法，我们还可以计算出班级里如果有N个人的时候，所有人的生日都不同的概率就是365分之364乘以365分之363，一直乘到365分之365减N加1。我们可以列出一张表，并且把所有人的生日都不同的概率P和发生生日碰撞的概率一减P同时列出。这样我们就会发现随着班级里人数的增加，生日彼此不同的概率急剧的下降，而发生生日碰撞的概率逐渐增加。我们可以画出图来表示这个趋势。大家看只要人数超过了23个人……
