생일 문제: 두 판 사이의 차이
편집 요약 없음 |
편집 요약 없음 |
||
5번째 줄: | 5번째 줄: | ||
생일 문제는 일반적인 인간의 직관과 다른 결과를 가지는 것으로 알려져 있다. 얼핏 생각하기에는 생일이 365가지이므로 임의의 두 사람의 생일이 같을 확률은 1/365이고, 따라서 365명쯤은 모여야 생일이 같은 경우가 있을 것이라고 생각하기 쉽다. 그러나 실제로는 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%를 넘고, 57명이 모이면 99%를 넘어간다. |
생일 문제는 일반적인 인간의 직관과 다른 결과를 가지는 것으로 알려져 있다. 얼핏 생각하기에는 생일이 365가지이므로 임의의 두 사람의 생일이 같을 확률은 1/365이고, 따라서 365명쯤은 모여야 생일이 같은 경우가 있을 것이라고 생각하기 쉽다. 그러나 실제로는 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%를 넘고, 57명이 모이면 99%를 넘어간다. |
||
생일이 같은 두 사람을 찾는 것과 비슷하게, [[암호학적 해시 함수|암호학적 해시 결과]]가 같은([[해시 충돌]]) 두 입력값을 찾는 것 역시 모든 입력값을 계산하지 않아도 충분히 높은 확률로 해시 충돌을 찾을 수 있다. 이러한 암호 공격을 [[생일 공격]](birthday attack)이라고 부른다. |
생일이 같은 두 사람을 찾는 것과 비슷하게, [[암호학적 해시 함수|암호학적 해시 결과]]가 같은([[해시 충돌]]) 두 입력값을 찾는 것 역시 모든 입력값을 계산하지 않아도 충분히 높은 확률로 해시 충돌을 찾을 수 있다. 이러한 암호 공격을 [[생일 공격]](birthday attack)이라고 부른다. |
||
== 확률 계산 == |
== 확률 계산 == |
2018년 11월 5일 (월) 15:47 판
생일 문제(生日問題)란 사람이 임의로 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률을 구하는 문제이다. 생일의 가능한 가짓수는 365개(2월 29일을 고려할 경우 366개)이므로 366명 이상의 사람이 모인다면 비둘기집 원리에 따라 생일이 같은 두 명이 반드시 존재하며, 23명 이상이 모인다면 그 중 두 명이 생일이 같은 확률은 1/2를 넘는다.
생일 문제는 일반적인 인간의 직관과 다른 결과를 가지는 것으로 알려져 있다. 얼핏 생각하기에는 생일이 365가지이므로 임의의 두 사람의 생일이 같을 확률은 1/365이고, 따라서 365명쯤은 모여야 생일이 같은 경우가 있을 것이라고 생각하기 쉽다. 그러나 실제로는 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%를 넘고, 57명이 모이면 99%를 넘어간다.
생일이 같은 두 사람을 찾는 것과 비슷하게, 암호학적 해시 결과가 같은(해시 충돌) 두 입력값을 찾는 것 역시 모든 입력값을 계산하지 않아도 충분히 높은 확률로 해시 충돌을 찾을 수 있다. 이러한 암호 공격을 생일 공격(birthday attack)이라고 부른다.
확률 계산
만약 366명 이상의 사람이 있다면 비둘기집 원리에 따라 생일이 같은 두 사람이 존재해야 한다. 365명 이하의 사람이 있을 경우를 계산한다. 명의 사람이 있을 때 그 중 생일이 같은 사람이 둘 이상 있을 확률을 이라고 한다면, 반대로 모든 사람의 생일이 다를 확률 은 이 된다. 먼저 을 구해보면, 두 번째 사람의 생일은 첫 번째 사람과 다르고, 세 번째 사람의 생일은 첫 번째와 두 번째 모두와 달라야 하므로 다음과 같은 식을 얻을 수 있다.
가 되고, 최종적으로 구하고자하는 생일이 같은 사람이 둘 이상 있을 확률 은
가 된다. 여기서, n≤365 인 자연수이고, !는 계승을 의미한다.
이 값을 특정 n 값에 대해 계산하면 다음과 같다.
n | p(n) |
---|---|
1 | 0.0% |
5 | 2.7% |
10 | 11.7% |
20 | 41.1% |
23 | 50.7% |
30 | 70.6% |
40 | 89.1% |
50 | 97.0% |
60 | 99.4% |
70 | 99.9% |
100 | 99.99997% |
200 | 99.9999999999999999999999999998% |
300 | (100 − (6×10−80))% |
350 | (100 − (3×10−129))% |
365 | (100 − (1.45×10−155))% |
366 | 100% |
367 | 100% |
즉, 50명만 모이면 그 가운데 2명 이상의 생일이 같을 확률이 97%이고, 100명이 모이면 거의 1에 가까워진다는 것을 알 수 있다.
참고 문헌
- Abramson, M.; Moser, W. O. J. (1970). “More Birthday Surprises”. 《American Mathematical Monthly》 77: 856–858. doi:10.2307/2317022.
- Bloom, D. (1973). “A Birthday Problem”. 《American Mathematical Monthly》 80: 1141–1142. doi:10.2307/2318556. JSTOR 2318556.
- Kemeny, John G.; Snell, J. Laurie; Thompson, Gerald (1957). 《Introduction to Finite Mathematics》 Fir판.
- Klamkin, M.; Newman, D. (1967). “Extensions of the Birthday Surprise”. 《Journal of Combinatorial Theory》 3: 279–282. doi:10.1016/s0021-9800(67)80075-9.
- McKinney, E. H. (1966). “Generalized Birthday Problem”. 《American Mathematical Monthly》 73: 385–387. doi:10.2307/2315408.
- Schneps, Leila; Colmez, Coralie (2013). 〈Math error number 5. The case of Diana Sylvester: cold hit analysis〉. 《Math on Trial. How Numbers Get Used and Abused in the Courtroom》. Basic Books. ISBN 978-0-465-03292-1.
- Sy M. Blinder (2013). 《Guide to Essential Math: A Review for Physics, Chemistry and Engineering Students》. Elsevier. 5–6쪽. ISBN 978-0-12-407163-6.
외부 링크
- The Birthday Paradox accounting for leap year birthdays
- Weisstein, Eric Wolfgang. “Birthday Problem”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- A humorous article explaining the paradox
- SOCR EduMaterials activities birthday experiment
- Understanding the Birthday Problem (Better Explained)
- Eurobirthdays 2012. A birthday problem. A practical football example of the birthday paradox.
- Grime, James. “23: Birthday Probability”. 《Numberphile》. Brady Haran.
- Computing the probabilities of the Birthday Problem at WolframAlpha