Coursera - Dan Boneh - Cryptography 1 - Week 1 - discrete probability 学习笔记【2】

承接上一篇文章。

这篇文章主要介绍生日悖论中，概率什么时候超过$\frac{1}{2}$，以及一个简单的例子。

记号

$|U|$：表示$U$的大小。 例如$U=00,01,10,11$，则$|U|=4$。
$\exists$：表示存在的意思。

生日悖论(The birthday paradox)

设$r_1,r_2,...,r_n\in U$，且$r_1,r_2,...,r_n$是独立同分布（independent identically distributed, i.i.d.）的随机变量，有如下定理：
定理：当$n=1.2\times |U{|}^{1/2}$时，有$Pr[\exists i\ne j:r_j=r_j]>\frac{1}{2}.$

对定理的解释：当变量的个数足够多的时候（$n=1.2\times |U{|}^{1/2}$，只要求达到$U$的开根号），就存在下标不同的两个数$r_i,r_j$，相同的概率超过$\frac{1}{2}$。

生日悖论的例子

令 U = { 0 , 1 } 128 U=\{0, 1\}^{128} U={0,1}128，那么从$U$中经过大约$1.2\times 2^{64}$次随机取样，样本中很有可能存在两个数相同。

预告：下一篇将介绍对称密码（Symmetric Ciphers）的定义、一次一密（One Time Pad，OTP）、以及完全保密（perfecy secrecy）。