생일 문제

(생일문제에서 넘어옴)

1 개요[ | ]

birthday problem, birthday paradox
生日 問題, 生日 逆說
생일 문제, 생일 역설
  • 사람이 임의로 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률을 구하는 문제
  • 생일이 같은 사람이 두 사람 이상 존재할 확률이 충분히 높아지게 하기 위해서 최소한 몇 명 이상의 사람이 모여야 하는지를 알아보는 확률론의 문제
  • 생일의 가능한 가짓수는 366개이므로 366명 이상의 사람이 모인다면 비둘기집 원리에 따라 생일이 같은 두 명이 반드시 존재하며, 23명 이상이 모인다면 그 중 두 명이 생일이 같은 확률은 1/2를 넘는다.
  • 얼핏 생각하기에는 생일이 366가지이므로 임의의 두 사람의 생일이 같을 확률은 1/366이고, 따라서 366명쯤은 모여야 생일이 같은 경우가 있을 것이라고 생각하기 쉽다.
  • 그러나 실제로는 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%를 넘고, 57명이 모이면 99%를 넘어간다.
  • 생일이 같은 두 사람을 찾는 것과 비슷하게, 암호학적 해시 결과가 같은(해시 충돌) 두 입력값을 찾는 것 역시 모든 입력값을 계산하지 않아도 충분히 높은 확률로 해시 충돌을 찾을 수 있다.
  • 이러한 암호 공격을 생일 공격(birthday attack)이라고 부른다.

Birthday Paradox.svg

2 같이 보기[ | ]

3 참고[ | ]

문서 댓글 ({{ doc_comments.length }})
{{ comment.name }} {{ comment.created | snstime }}