Birthday Problem — Nghịch lý sinh nhật
Bài toán kinh điển cho thấy trực giác về xác suất sai ở đâu, và vì sao tấn công va chạm hash chỉ tốn √N phép thử.
Đường mô phỏng dựng từ vị trí xảy ra trùng đầu tiên của 20,000 lượt, nên nó là 20,000 lượt ĐÓ đọc theo mọi cỡ nhóm chứ không phải chạy lại. Hai đường bám nhau trong khoảng ±0.71% là đúng như sai số Monte Carlo cho phép.
Sai số Monte Carlo của 20,000 lượt là ±0.3535%. Nằm trong 3σ nghĩa là chênh lệch chỉ do số lượt hữu hạn, không phải do công thức hay bộ sinh số sai.
Với 365 ngày trong năm. Quy luật xấp xỉ là √(2·365·ln2) ≈ 22 — tăng theo CĂN của số ngày, nên năm dài gấp 4 lần cũng chỉ cần gấp đôi số người.
Đây là toàn bộ nghịch lý. Trực giác đếm số cặp có MÌNH; bài toán đếm mọi cặp, và số đó tăng theo bình phương.
Trong mật mã học đây là cận trên của an toàn: hàm băm b bit bị tìm ra va chạm sau khoảng 2^(b/2) phép thử, nên SHA-1 160 bit chỉ còn 80 bit sức chống va chạm.
| Số cặp có thể | 253 |
| Số lượt mô phỏng | 20,000 |
| Với 23 người | 50.73% |
| Với 50 người | 97.04% |
| Ứng dụng thật | Tấn công sinh nhật trong mật mã học: tìm va chạm hash chỉ cần khoảng √N phép thử, không phải N |
Đường mô phỏng dựng từ vị trí xảy ra trùng đầu tiên của 20,000 lượt, nên nó là 20,000 lượt ĐÓ đọc theo mọi cỡ nhóm chứ không phải chạy lại. Hai đường bám nhau trong khoảng ±0.71% là đúng như sai số Monte Carlo cho phép.
Cùng công thức, quét tới nhóm 60 người. Đường cắt mốc 50% ở 23 người — con số nhỏ đến mức phản trực giác vì số cặp tăng theo bình phương: nhóm 23 người đã có 253 cặp.
| Số cặp có thể | 253 |
| Số lượt mô phỏng | 20,000 |
| Với 23 người | 50.73% |
| Với 50 người | 97.04% |
| Ứng dụng thật | Tấn công sinh nhật trong mật mã học: tìm va chạm hash chỉ cần khoảng √N phép thử, không phải N |
Nghịch lý sinh nhật hỏi cần bao nhiêu người để xác suất có ít nhất hai người trùng ngày sinh vượt 50%. Đáp án 23 người gây bất ngờ vì trực giác đếm số người, trong khi cái thực sự tăng là số cặp — 23 người tạo ra 253 cặp. Đây là mô hình gốc của bài toán đụng độ hàm băm và trùng khoá ngẫu nhiên trong hệ thống thật.
| n để P vượt 50% | 23 người với 365 ngày |
| Số cặp C(n,2) | đại lượng thực sự điều khiển kết quả |
| √N | quy mô mẫu gây đụng độ với N khả năng |
Phần quan trọng nhất của trang này. Một phương pháp được mô tả mà không nói chỗ nó hỏng là phiên bản quảng cáo của phương pháp đó.
Nghịch lý sinh nhật hỏi cần bao nhiêu người để xác suất có ít nhất hai người trùng ngày sinh vượt 50%. Đáp án 23 người gây bất ngờ vì trực giác đếm số người, trong khi cái thực sự tăng là số cặp — 23 người tạo ra 253 cặp. Đây là mô hình gốc của bài toán đụng độ hàm băm và trùng khoá ngẫu nhiên trong hệ thống thật.
1. Tính xác suất bù: mọi người đều khác ngày sinh. 2. P(khác hết) = 365/365 × 364/365 × … × (365−n+1)/365. 3. Xác suất cần tìm là 1 trừ giá trị trên. 4. Xấp xỉ nhanh: P ≈ 1 − exp(−n(n−1)/(2·365)). 5. Tổng quát hoá sang N khả năng bất kỳ để áp cho bài toán đụng độ hàm băm hoặc trùng mã đơn hàng.
Nhầm với câu hỏi khác hẳn: xác suất có người trùng ngày sinh với riêng bạn cần tới 253 người, vì lúc đó chỉ còn n−1 cặp. Giả định ngày sinh phân bố đều — thực tế có mùa sinh, khiến xác suất trùng còn cao hơn tính toán lý thuyết.
n để P vượt 50% — 23 người với 365 ngày; Số cặp C(n,2) — đại lượng thực sự điều khiển kết quả; √N — quy mô mẫu gây đụng độ với N khả năng.
Đã chạy được: công cụ tính toán thật trên nền tảng này.