密碼學I：離散概率（續）

導覽

課程地址請見Coursera。

對於離散概率的更詳細解釋，請見：WikiBooks (English)

注意：文章中對專業名詞進行解釋的鏈接均來自中文維基百科，中國大陸讀者若想訪問請自備... ...

歡迎訪問作者博客。

若未閱讀上篇文章密碼學I：離散概率的，*強烈*建議前去閱讀。

獨立性

定義

獨立性：若存在兩事件、，事件的發生無法向你提供關於事件的任何信息，則稱、兩事件是互相獨立的。即：

通常來講，獨立性衡量的是兩事件間互不相關的程度。

隨機變數中的獨立性

若有兩個在集合中取值的隨機變數，那麼如果這兩個隨機變數滿足：

這意味著即使你知道你也不知道關於的取值的任何信息。

異或運算（XOR，）

這是一種在密碼學中相當重要和基礎的運算。

關於其重要的原因我們將稍後講到。

定義

一種對數值和進行的運算，記為：

其運算基本規則為：兩兩數值相同時為假，而數值不同時為真。

這也就是說，，。

通常來講，我們所寫的形如不是對整個數值進行運算，而是對數值的每一位進行運算。即（一般我們用表示「真」，用表示「假」）：

請見：維基百科 - 邏輯異或（中文 - 大陸簡體）

異或運算（XOR）的重要性質

闡述：若存在一個隨機變數，和一個獨立均勻隨機變數，此時和的異或（無論以什麼方式分布）總是一個均勻的隨機變數。

換句話說如果我取一個隨機的分布，然後用獨立均勻隨機變數和它進行異或運算，最終得到的一定是一個均勻隨機變量，即：

證明現不列出。可能會在作者博客上給出。

生日悖論（The birthday paradox）

定義

定義：假設在全集中選擇幾個獨立、以相同方式分布的隨機變數 ，則若選擇次，則基本上有很大的幾率（超過）會有兩個相同的元素。換句話說，若抽樣次，那麼很有可能（超過）你的兩個抽樣會是 一樣的，即：

該定理被叫做「悖論」是因為經常使用該定理來描述人們的生日。因為根據該定理，最少僅僅需要個人聚集在一起就能夠使得有兩個人有同樣的生日的概率大於，即24個人。這就是為什麼叫做悖論，因為24應該是一個比大多數人的預計都要小的數。

應用

所以只要取樣個數超過全集大小的平方根，抽到相同元素的概率將會很快趨近於

以後我們會再返回並更具體地學習生日悖論，但目前就到此為止。

結語

本節和上一節主要介紹了概率分布基礎、事件、隨機變數基本知識以及一種在密碼學中非常常用也非常重要的演算法XOR（異或運算，$oplus$）及其基本性質，最後簡要介紹了密碼學中一個非常中心的理論：生日悖論。

本節和上一節的知識相當基礎和重要。

下一節/下一章我們會開始學習我們的加密系統的第一個例子。

本節完

本章完

推薦閱讀：