วันพฤหัสบดีที่ 1 ธันวาคม พ.ศ. 2554

Birthday paradox

หากคุณไปงานเลี้ยง แล้วเดินถามวันเกิด (เอาเฉพาะวันกับเดือน) ของคนที่คุณคุยด้วย คุณจะพบว่าใน 23 คนที่คุณถามวันเกิด จะมีโอกาสสูงที่คนที่เกิดวันเดียวกันอยู่ 1 คน

ใน 1 ปีหนึ่งมีตั้ง 365 วัน แต่ถามแค่ 23 คน กลับเจอคนที่เกิดวันเดียวกันคนเดียว

สรุปตามหลักสถิติ
sample 2^n จะมีโอกาสเกิด collision ที่ 2^n/2

365 = 2^8.51 => collision ที่ 2^8.51/2 = 19.104 ใกล้เคียงกับความจริงคือ 23 มากเลย

เพื่อป้องการปัญหาการ collision ของ hash function ควรจะ hash ที่ 160 bits

ไม่มีความคิดเห็น: