【數學理論】 06. 只需要23人走進一間大禮堂，就能有一半機率兩個人選到同一個位子

--- title: 【數學理論】 06. 只需要23人走進一間大禮堂，就能有一半機率兩個人選到同一個位子 — 生日悖論（Birthday Paradox） tags: - 【數學理論】 - 悖論 url: https://hackmd.io/GNLVFIylSCeDxlk0FoH6RA lastSync: 2025-05-25T08:45:48.439Z hackmd: url: https://hackmd.io/GNLVFIylSCeDxlk0FoH6RA title: 【數學理論】 06. 只需要23人走進一間大禮堂，就能有一半機率兩個人選到同一個位子 — 生日悖論（Birthday Paradox） lastSync: 2025-05-25T05:17:23.878Z --- 只需要23人走進一間大禮堂，就能有一半機率兩個人選到同一個位子。 === 生日悖論（Birthday Paradox） ---  按照慣例，開頭先來說一個故事。 記得某次加班到大概晚上11點左右，我進捷運站時遇到一個人，當時站內只有我跟他還有站務人員而已。 因為一些原因，我們就聊了起來，他好奇問了我的星座，當知道我是牡羊座後，他很訝異的說**他也是牡羊座**。並且說他幾月幾號生。 神奇的是，他的生日竟然只跟我差一天，這個機率是很低的。我們簡單粗算一下兩個人生日只差一天的機率。 首先我們不考慮閏年或有生日集中的月份，一年有 **$365$ 天** 且每個人的生日分布均勻，在我生日是固定的情況下，對方生日只跟我差一天只會有兩種情況： - 他的生日在我前面一天（我的生日日期 $+1=$ 他的生日）。 - 他的生日在我後面一天（我的生日日期 $-1=$ 他的生日）。 如此一來，**一年當中只會有兩天跟我生日只差一天**，也就是： $$ \dfrac{2}{365}\approx 0.00548=0.548\% $$ 那生日跟我同一天的機率我們就可以很簡單推算出來就是： $$ \dfrac{1}{365}\approx 0.00274=0.247\% $$ 也就是說，**你跟另外一個人共 $2$ 個人走進一間大禮堂，裡面有 $365$ 個位子可以坐，先在心裡選好位子再坐，你們兩個人剛好選到相鄰位子的機率只有 $0.548\%$，而選到同一個位子的機率更是只有 $0.247\%$。** 所以我們知道，生日要配對到的機率是很低的。 --- 還記得高中時，先學**排列組合**再學**機率**，因為**機率**裡有一大堆可以令人感到快(ㄜˇ)樂(ㄒㄧㄣ)的**排列組合**。 在 $C$、$P$、$H$、**擲骰子**（還分均勻骰子跟不均勻骰子）、**取球**（還分取後放回跟取後不放回）的題海中，有一個宛如浮木的問題映入我的眼簾。 **「如果在一群人中，只需要 $n$ 個人，就能讓至少兩個人生日相同的機率超過 $50\%$，那 $n$ 最少要多少？」** 答案是： $n=23$ 這個答案很有趣，也就是只需要有 **$23$ 人** 就有超過 $50\%$ **的機率** 至少有兩個人生日是一樣！ 這句話的意思就好像是：**$23$ 個人走進一間大禮堂，裡面有 $365$ 個位子可以坐，先在心裡選好位子再坐，但有五成以上的機率至少兩個人偏偏選到同一個位子。** 當下聽到老師提出這個問題覺得半信半疑，沒想到老師做了一個實驗，對照了大家的生日，沒想到班上約莫30個人左右，竟然真的有兩到三對同學的生日是一樣的。 這個結果跟我們一開始算的 $0.247\%$ 大相逕庭，常理來說可能要超過1、200人才有可能出現兩人生日相同的機率大於 $50\%$， 這個反直覺的悖論又被稱為**生日悖論（Birthday Paradox）** 要了解這個悖論之前，讓我們有些先備知識，先來談談**生日問題 (Birthday Problem)**。 ## **生日問題 (Birthday Problem)** >[!Note] **生日問題 (Birthday Problem)** >如果在一群人中，只需要 $n$ 個人，就能讓至少兩個人生日相同的機率超過 $50\%$，那 $n$ 為多少？ 我們一樣不考慮閏年或有生日集中的月份，一年有 **$365$ 天**，且每個人的生日分布均勻： 1. **計算所有人生日都不同的機率** 如果第一個人的生日是任意一天，第二個人的生日有 $364$ 天可選（不能與第一個人相同），第三個人有 $363$ 天，以此類推。當有 $n$ 個人時，所有生日都不同的機率為： $$ P(\text{所有人生日不同}) = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \dots \times \frac{(365 - n + 1)}{365} $$ 2. **計算至少有兩人生日相同的機率** 至少有兩人生日相同的機率是以上情況的補集： $$ P(\text{至少兩人生日相同}) = 1 - P(\text{所有人生日不同}) $$ --- 有了計算的概念後，接著讓我們計算當 $n = 23$ 時的情況： ### 當 $n = 23$ 1. **所有人生日都不同的機率** $$ P(\text{所有人生日不同}) = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \dots \times \frac{343}{365} \approx 0.4927 $$ 約為 $49.27\%$。 2. **至少有兩人生日相同的機率** $$ P(\text{至少兩人生日相同}) = 1 - 0.4927 = 0.5073 $$ 約為 $50.73\%$，超過了 $50\%$。 --- 現在我們把 $n$ 加大，看看 $n = 50$ 時的情況： ### 當 $n = 50$ 1. **所有人生日都不同的機率** $$ P(\text{所有人生日不同}) = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \dots \times \frac{316}{365} \approx 0.0296 $$ 約為 $2.96\%$。 2. **至少有兩人生日相同的機率** $$ P(\text{至少兩人生日相同}) = 1 - 0.0296 = 0.9704 $$ 約為 $97.04\%$，接近 $100\%$。 --- 我們把 $n$ 再加大，看看 $n = 70$ 時的情況： ### 當 $n = 70$ 1. **所有人生日都不同的機率** $$ P(\text{所有人生日不同}) = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \dots \times \frac{296}{365} \approx 0.00084 $$ 約為 $0.084\%$。 2. **至少有兩人生日相同的機率** $$ P(\text{至少兩人生日相同}) = 1 - 0.00084 = 99.99916 $$ 約為 $99.99\%$，基本上跟 $100\%$ 差不多了。 --- 接下來用程式跑一下可視化的結果。 :::spoiler 點擊以查看程式碼 ```python= import numpy as np import matplotlib.pyplot as plt from matplotlib.animation import FuncAnimation def calculate_birthday_probability(n_people): """Calculate the probability of at least one birthday match in a group of n people""" no_match_prob = 1.0 for i in range(n_people): no_match_prob *= (365 - i) / 365 return 1 - no_match_prob # 建立中間的表 plt.rcParams['figure.figsize'] = [12, 7] # Increased height plt.rcParams['figure.autolayout'] = True # Automatic layout adjustment fig, ax = plt.subplots() ax.set_xlim(0, 100) ax.set_ylim(0, 100) plt.subplots_adjust(top=0.9, bottom=0.15, right=0.95, left=0.1) # 初始化 line, = ax.plot([], [], 'b-', linewidth=2) points, = ax.plot([], [], 'ro') annotations = [] # 新增格線 ax.grid(True, linestyle='--', alpha=0.7) # 建立圖名與標籤 ax.set_title('Birthday Problem: Probability vs Group Size', fontsize=14, pad=20) ax.set_xlabel('Number of People', fontsize=12) ax.set_ylabel('Probability of Birthday Match (%)', fontsize=12) # 初始化資料 x_data, y_data = [], [] def init(): """Initialize animation""" line.set_data([], []) points.set_data([], []) return line, points def animate(frame): """Animation function""" # Remove old annotations for ann in annotations: ann.remove() annotations.clear() # 更新點 x_data.append(frame + 1) y_data.append(calculate_birthday_probability(frame + 1) * 100) # 更新線 line.set_data(x_data, y_data) # 更新重要節點 important_numbers = [23, 50, 70] x_points = [n for n in important_numbers if n <= frame + 1] y_points = [calculate_birthday_probability(n) * 100 for n in x_points] points.set_data(x_points, y_points) # 更新標註 for x, y in zip(x_points, y_points): # Adjust annotation position based on point location if x == 23: xytext = (10, 10) # Default offset for first point elif x == 50: xytext = (-60, -20) # Move annotation down and left for second point else: # x == 70 xytext = (-60, -20) # Move annotation down and left for third point ann = ax.annotate(f'n={x}\n{y:.1f}%', xy=(x, y), xytext=xytext, textcoords='offset points', bbox=dict(boxstyle='round,pad=0.5', fc='white', ec='gray', alpha=0.7)) annotations.append(ann) return line, points # 建立動畫 anim = FuncAnimation(fig, animate, init_func=init, frames=100, interval=50, blit=False) # 將動畫存成GIF檔 anim.save('birthday_problem.gif', writer='pillow') # 跑程式時展示動畫 plt.show() ``` ::: <img src="https://raw.githubusercontent.com/lewisjjj800soic/HackMD-images-backup/main/Mathematic-Theorems/06/01.gif" alt="圖片描述" style="display: block; margin: 0 auto;" width="500"> 上圖可以看到，只要超過 $70$ 人，機率就幾乎等於 $100\%$ 了。 根據上面數學的推導以及程式可視化的結果，我們確實驗證了「**在一群人中，只需要 $23$ 個人，就能讓至少兩個人生日相同的機率超過 $50\%$**」這個結果，因為這個結果實在過於反直覺，因此又被稱作是**生日悖論（Birthday Paradox）**。 --- ## **生日悖論** >[!Important] **生日悖論（Birthday Paradox）** >**在一群人中，只需要 $23$ 個人，就能讓至少兩個人生日相同的機率超過 $50\%$** **生日悖論**之所以令人驚訝，是因為我們通常低估了**配對數量**的增長速度。在 $23$ 個人中，實際可能的生日配對數可以用我們熟悉的**排列組合**來呈現。因為要求的是 $n$ 人當中找 $k$ 人來配對，相當於是 $$C^{n}_{k} = \frac{n!}{k!(n-k)!}$$ 當我們要在 $23$ 人當中找 $2$ 人來配對，配對數相當於是 $$ C^{23}_{2} = \frac{23 \times 22}{2} = 253 \, \text{對} $$ 所以一開始我說的：「**你跟另外一個人共 $2$ 個人走進一間大禮堂，裡面有 $365$ 個位子可以坐，先在心裡選好位子再坐，你們兩個人剛好選到相鄰位子的機率只有 $0.548\%$，而選到同一個位子的機率更是只有 $0.247\%$。**」 以及我後來的舉例：「**$23$ 個人走進一間大禮堂，裡面有 $365$ 個位子可以坐，先在心裡選好位子再坐，但有五成以上的機率至少兩個人偏偏選到同一個位子。**」 這兩句話其實是不一樣的。 我一開始說的：「**任意一人**跟**你**生日相同的機率」。這句話忽略了**重複配對**的概念。 事實上我們關注的是：「**任意兩人**生日相同的機率」。 打個比方，假如我自己骰一個**正六面體的均勻骰子**，我自己想要一次就骰到六的機率很低，但是如果有一群人，一次就骰到六的機率就會大大提升。 這並不是玩文字遊戲，而是利用人的常理來進行引導式思考，才會產生這種**違反直覺的悖論**，我想這就是數學類悖論迷人的地方吧！ 接下來，我們可以用程式來實驗看看跑一萬次模擬的結果。 :::spoiler 點擊以查看程式碼 ```python= import random # 設定總共有幾人 num_people = 23 # 設定總共有幾個位子 num_seats = 365 # 設定總共跑幾次 num_trials = 10000 def simulate_seat_collisions(num_people, num_trials, num_seats): collisions = 0 for i in range(num_trials): seats_chosen = [random.randint(1, num_seats) for j in range(num_people)] if len(seats_chosen) != len(set(seats_chosen)): collisions += 1 return collisions, collisions / num_trials # 執行模擬 collision_count, collision_probability = simulate_seat_collisions(num_people, num_trials, num_seats) print(f"總共有 '{num_people}' 人") print(f"總共跑了 '{num_trials}' 次") print(f"總共發生 '{collision_count}' 次兩人選到同一個位子的事件") print(f"選到同個位子的機率為: {collision_probability * 100:.2f}%") ``` ::: 執行上面的程式後，會產生以下輸出： ``` 總共有 '23' 人總共跑了 '10000' 次總共發生 '5118' 次兩人選到同一個位子的事件選到同個位子的機率為: 51.18% ``` 改成總共有 $50$ 人，執行上面的程式後，會產生以下輸出： ``` 總共有 '50' 人總共跑了 '10000' 次總共發生 '9679' 次兩人選到同一個位子的事件選到同個位子的機率為: 96.79% ``` 改成總共有 $70$ 人，執行上面的程式後，會產生以下輸出： ``` 總共有 '70' 人總共跑了 '10000' 次總共發生 '9989' 次兩人選到同一個位子的事件選到同個位子的機率為: 99.89% ``` 根據上面的程式實驗結果，我們會發現跟我們前面計算的結果是相似的。也就是： |$n$值|計算兩人生日相同機率|程式實驗結果| |---|---|---| |$n=23$|$50.73\%$|$51.18\%$| |$n=50$|$97.04\%$|$96.79\%$| |$n=70$|$99.99\%$|$99.89\%$| 然而這個悖論真正可怕的地方在於，並不僅僅只是違反常理，有心人士可以利用生日悖論的概念來破解更有可能牽扯到世界上的安全系統，例如金融、數位簽名和區塊鏈等，這種攻擊手段又被稱作是**生日攻擊（Birthday Attack）**。 ## 生日攻擊（Birthday Attack）在講解之前，必須先介紹一個很有趣又可愛的原理：**鴿巢原理** --- ### 鴿巢原理（Pigeonhole Principle） 鴿巢原理是數學中的一個簡單但非常重要的概念，主要描述以下現象： >[!Important] **鴿巢原理（Pigeonhole Principle）** >如果將 $n+1$ 隻鴿子放入 $n$ 個巢裡，那麼至少會有一個巢裡會有兩隻鴿子。 以我們剛剛提到的生日悖論來舉個例子，當今天一間大禮堂有 **$367$ 人**，那我們可以很肯定的說：**這間大禮堂至少會有兩個人生日同一天**，因為一年最多只有 $366$ 天(鴿巢)，但總共有 $367$ 人(鴿子)，所以根據鴿巢原理，**這間大禮堂至少會有兩個人生日同一天**。 有人可能會想：**這不是廢話嗎？**，但根據鴿巢原理，我們可以得到很多很有趣的推論： >[!Tip] **新北市至少有兩個人頭髮的數量是一樣的。** 因為人類頭髮平均有15萬根(鴿巢)左右，但新北市人口截至2023 年 1 月卻約有400.4 萬(鴿子)，所以根據鴿巢原理，**新北市至少有兩個人頭髮的數量是一樣的。** >[!Tip] **如果我襪子的顏色只有兩種，那我只要隨便抓三隻襪子，必定可以抓到同色的一雙襪子。** 因為襪子的顏色(鴿巢)只有兩種，如果隨手抓三雙(鴿子)，所以根據鴿巢原理，**只要閉著眼睛隨便抓三隻襪子，必定可以抓到同色的一雙襪子。** >[!Tip] **一場有 n 個人(n大於等於2)的聚會當中，互相並隨意找人握手，必有兩人握過手的人數相同。** 因為每個人最多跟除了自己以外的人 $(n-1\ 人)$ 握過手，或是不跟任何人 $(0\ 人)$ 握手，也就是可以跟 $[0,n-1]$ 人握過手（但 $0$ 和 $n-1$ 不能同時存在，因為如果一個人不跟任何人握手，那就不會存在一個人跟除了自己以外的人握過手），所以根據鴿巢原理，**一場有 $n$ 個人( $n$ 隻鴿子)的聚會當中，每個人最多的握手次數是 $n-1$ 次( $n-1$ 個鴿巢)，必有兩人握過手的人數相同。** >大家可以停下來思考一下上面這幾個例子。 根據上面幾個例子其實不難發現，鴿巢原理的精隨就是**當輸入資訊量大於輸出資訊量，那至少會有兩個輸入會對應到同一個輸出**，**其實就是鴿子太多了，沒辦法讓每隻鴿子舒舒服服住在單個鴿巢，只能委屈某些鴿子擠在同一個巢中**。 而鴿巢理論這個**兩個輸入會對應到同一個輸出**的情況，在電腦科學中就叫「**碰撞**」。 接下來讓我們了解幾個名詞：**哈希函式**、**哈希值**、**哈希碰撞**。 --- ### 哈希函式與哈希值（Hash Function & Hash Values） **哈希函數**是用來將任意長度的輸入映射(也可以理解成是對應)到固定長度的輸出值，這個輸出值也叫做**哈希值**。 > 其中「Hash (哈希)」也可能被叫做是「雜湊」，以下就統一用哈希來稱呼。 哈希函式的用意在於**在大量數據中，如果需要快速找到特定的資料，利用哈希函式給予資料一個哈希值，減少查找資料的複雜度，提升效率。** >[!Tip] **簡單舉個例子** 現在你有一份大概十萬名客戶的名單，名單內包含客戶的姓名與電話，假如說今天結帳時你發現發票打錯了，客人是一位叫做**林淑芬**的會員，如果想要找到這名會員，用名字找的話會發現有差不多500位林淑芬，但如果是用**會員編號**，你就可以精準的找到你要找的林淑芬，把他手上那張開錯的發票奪回來。 在上面這個例子中，哈希函式就是給會員一個會員碼的程式，而哈希值就是會員編號，雖然輸入(名字)可能會出現同名同姓的情況，但是輸出(會員編號)卻只有一個，所以以會員編號做為哈希值，當想要找到特定的資料(人)，利用哈希值就可以快速找到想要的資料，大大提升效率。 但是，但因為輸入的可能性是無限的，而哈希值的範圍有限，因此根據鴿巢原理，**不同的輸入可能對應到相同的哈希值。** >[!Tip] **一樣以剛剛的例子** 假設今天幫會員編碼的程式只能從000000編到999999，也就是10萬筆，當會員人數超過10萬人時，理論上來說，就一定會出現有至少兩組相同的會員編號，也就是產生相同的哈希值，這種情況稱為「**哈希碰撞**」。 --- ### 哈希碰撞（Hash Collision） 在電腦科學中，**哈希碰撞**是一件很嚴重的事情。特別是在安全性和資安等情況中，例如我剛剛提到的金融、數位簽名和區塊鏈等，下面我舉一些**找到哈希碰撞可能會造成的問題**。 >[!Caution] **偽造文件或數據** 在數位簽名系統中，簽名的對象是文件的哈希值而不是文件本身。如果攻擊者找到兩個內容不同但哈希值相同的文件（碰撞），他們可以利用這一點進行偽造。 >1. 攻擊者創建兩個文件： > - 文件 A：無害的合法文件（如合同 A）。 > - 文件 B：惡意文件（如合同 B），內容不同但哈希值相同。 >2. 攻擊者請受害者簽署合同 A 的哈希值。 >3. 由於合同 A 和合同 B 的哈希值相同，攻擊者可以冒充受害者的簽名偽造合同 B。 >[!Caution] **破壞數據完整性驗證** 哈希函數經常被用來檢查文件或數據的完整性。如果有人找到哈希碰撞，就可以對文件或數據進行未經授權的修改，而不被發現。 > - 軟體下載網站提供哈希值（如 SHA-256）來驗證下載的軟體是否完整。 > - 如果攻擊者找到與原始軟體哈希值相同的惡意軟體，他可以替換原始軟體，讓用戶無法察覺被竄改。 >[!Caution] **在區塊鏈中的影響** 區塊鏈依賴哈希函數來鏈接區塊和驗證交易。如果找到碰撞，攻擊者可能篡改交易或改變整條區塊鏈的歷史。 > - 每個區塊包含前一個區塊的哈希值。 > - 如果攻擊者找到與某個區塊哈希值相同的另一個區塊，他可以創建一條偽造的區塊鏈，導致「雙花攻擊」或其他欺詐行為。 >[!Caution] **密碼學協議中的漏洞** 許多密碼學協議（如 TLS、數字證書）依賴哈希函數保證安全性。如果哈希函數碰撞被攻擊者利用，整個系統可能失效。 > - 攻擊者生成了一個偽造的 SSL/TLS 憑證，哈希值和真實憑證相同。 > - 用戶可能無法分辨這是偽造的憑證，導致安全通信被攔截或篡改。 經過上面的例子可以發現，哈希碰撞會造成嚴重的後果是因為**哈希碰撞使得哈希值的「唯一性」被破壞了**，因此如果這個哈希函式被發現非常容易找到哈希碰撞，那就代表這個哈希函式就不再是一個安全的哈希函式了。 而本結的重點 — **生日攻擊** 正是利用生日悖論提及的配對方法，找到**哈希碰撞**破壞**哈希值**的「唯一性」，以下進行一些簡單的數學推導跟講解。 --- ### 生日攻擊的數學推導 **生日攻擊**利用生日問題中的機率原理，說明在較大的集合中，發生碰撞（即兩個元素映射到同一值）的可能性比直覺上預期的要高。 在密碼學中，這種攻擊特別針對哈希函式，試圖找到兩個不同的輸入產生相同的哈希值，我們訂定以下命題。 >[!Tip] **生日攻擊命題** >假設有一個哈希函式，其輸出有 $N$ 個可能的不同值（例如，對於一個產生 128 位元哈希值的函式， $N = 2^{128}$。，選取 $k$ 個隨機輸入後，至少有兩個輸入產生相同哈希值（即發生碰撞）的機率。 #### 1. 計算無碰撞的機率首先跟生日悖論一樣，計算所有哈希值都不相同的機率： 1. **第一個輸入**：可以映射到 $N$ 個值中的任意一個，機率為 $1$。 2. **第二個輸入**：為避免碰撞，必須映射到剩下的 $N - 1$ 個值之一，機率為 $\frac{N-1}{N}$。 3. **第三個輸入**：必須映射到剩下的 $N - 2$ 個值之一，機率為 $\frac{N-2}{N}$。 4. **以此類推**：第 $k$ 個輸入必須映射到剩下的 $N - (k-1)$ 個值之一，機率為 $\frac{N-(k-1)}{N}$。 因此，所有 $k$ 個輸入的哈希值都不相同的總機率為： $$ P(\text{無碰撞}) = \frac{N-1}{N} \times \frac{N-2}{N} \times \cdots \times \frac{N-(k-1)}{N} $$ 這可以表示為： $$ P(\text{無碰撞}) = \prod_{i=1}^{k-1} \left(1 - \frac{i}{N}\right) $$ #### 2. 近似計算當 $N$ 很大且 $k$ 相對較小時，可以使用近似來簡化計算。使用自然指數函數的近似 $e^x \approx 1 + x$（當 $x$ 很小時），我們有： $$ \ln\left(P(\text{無碰撞})\right) = \sum_{i=1}^{k-1} \ln\left(1 - \frac{i}{N}\right) \approx -\sum_{i=1}^{k-1} \frac{i}{N} = -\frac{k(k-1)}{2N} $$ 因此： $$ P(\text{無碰撞}) \approx e^{-\frac{k(k-1)}{2N}} $$ #### 3. 計算發生碰撞的機率至少有兩個輸入產生相同哈希值的機率為 $1$ 減去無碰撞的機率： $$ P(\text{至少一個碰撞}) = 1 - P(\text{無碰撞}) \approx 1 - e^{-\frac{k(k-1)}{2N}} $$ 當 $k$ 相對較小時，$k(k-1) \approx k^2$，因此可以進一步近似為： $$ P(\text{至少一個碰撞}) \approx 1 - e^{-\frac{k^2}{2N}} $$ #### 4. 確定臨界值 $k$ 為了找到使碰撞機率達到某一特定值（例如 $50\%$）的 $k$，設 $P(\text{至少一個碰撞}) = 0.5$，則： $$ 0.5 \approx 1 - e^{-\frac{k^2}{2N}} $$ 解此方程，我們得到： $$ e^{-\frac{k^2}{2N}} \approx 0.5 $$ 取自然對數： $$ -\frac{k^2}{2N} \approx \ln(0.5) = -\ln(2) $$ 因此： $$ \frac{k^2}{2N} \approx \ln(2) $$ $$ k^2 \approx 2N \ln(2) $$ $$ k \approx \sqrt{2N \ln(2)} $$ 由於 $\ln(2) \approx 0.693$，因此： $$ k \approx 1.177 \sqrt{N} $$ #### 5. 推導結果當選取約 $1.177 \times \sqrt{N}$ 個隨機輸入時，至少有兩個輸入產生相同哈希值的機率約為 $50\%$。我們會發現，根據生日攻擊的原理，對於 $n$ 位的哈希值，找到碰撞的計算成本只需要約 $\sqrt{2^n}$ 次嘗試，而不是 $2^n$ 次，遠遠小於我們的認知。 這就是**生日攻擊**中常引用的結果，說明在**哈希函式**的輸出空間較大時，找到碰撞所需的嘗試次數遠少於輸出空間的大小。 ## 總結在這篇專欄中，我們從**生日問題**開始一陣腦力激盪，揭開了**生日悖論**的神秘面紗，再從**鴿巢原理**講述為什麼會發生**哈希碰撞**，最後利用數學推導了**生日攻擊**的機率原理。 我們會發現，一個在高中數學課本的小小問題，竟然有辦法牽扯到整個世界的安全體系，知識的汪洋不去探究實在很難發現其深奧的道理，包括在我寫這篇專欄之前也壓根沒想到生日悖論之後會有後面這一大段。 所以有時候去探究一件事情時，就算只是小事情，背後可能也會有身後的大道理呢！ 我是Lewis，我們[**下一篇**](https://hackmd.io/@lewisjjj800/rkhNq8ezeg)專欄見！