Tentang paradoks ulang tahun | Pasangan, perhitungan, dan serangan ulang tahun

Paradoksnya

Tanyakan kepada orang-orang berapa banyak tamu yang dibutuhkan sebuah pesta agar kemungkinan besar dua di antaranya berulang tahun sama, dan kebanyakan akan menjawab sekitar 180, separuh dari 365. Jawaban sebenarnya adalah 23: saat itu peluangnya 50,7%. Dengan 57 tamu, peluangnya 99%. Ini disebut paradoks bukan karena bertentangan dengan dirinya sendiri, melainkan karena sangat berlawanan dengan intuisi kita.

Mengapa intuisi keliru

Di sebuah ruangan, tanpa sadar kita bernalar dari diri sendiri: berapa peluang ada orang yang berulang tahun sama dengan saya? Dengan 365 hari, peluang itu kecil. Namun paradoks ini menyangkut semua pasangan yang mungkin di ruangan itu, bukan kecocokan dengan satu orang tertentu: A dan B, B dan C, A dan C, dan seterusnya. Dengan 23 orang Anda dapat membentuk 253 pasangan berbeda, dan setiap pasangan bisa saja berulang tahun sama.

Pasangan tumbuh secara kuadrat

n orang membentuk n × (n − 1) / 2 pasangan: 10 orang membentuk 45 pasangan, 23 orang 253, 57 orang 1.596, dan 100 orang 4.950. Setiap pasangan berulang tahun sama dengan peluang 1/365, sehingga 253 pasangan rata-rata menghasilkan 253/365 ≈ 0,69 pasangan yang berulang tahun sama. Menggandakan kelompok kira-kira melipatempatkan banyaknya pasangan, dan karena itulah peluang ulang tahun yang sama melonjak.

Perhitungan langkah demi langkah

Cara termudah adalah menghitung peluang tidak ada seorang pun yang berulang tahun sama, lalu mengurangkannya dari 100%. Orang pertama mengambil hari apa saja. Orang kedua berpeluang 364/365 untuk tidak berulang tahun sama dengannya. Orang ketiga berpeluang 363/365 untuk berbeda dari dua orang pertama, dan seterusnya. Untuk 23 orang:

365/365 × 364/365 × 363/365 × … × 343/365 ≈ 49,3%

Karena peluang semua orang berulang tahun berbeda adalah 49,3%, kebalikannya, yaitu paling sedikit ada satu ulang tahun yang sama, berpeluang 100% − 49,3% = 50,7%.

Orang yang berulang tahun sama dengan Anda

Peluang ada orang yang berulang tahun sama dengan Anda adalah pertanyaan lain. Masing-masing dari n − 1 orang lainnya meleset dari ulang tahun Anda dengan peluang 364/365, sehingga peluang ada yang berulang tahun sama dengan Anda adalah 1 − (364/365)ⁿ⁻¹. Dengan 23 orang peluangnya hanya 5,9%, dan Anda membutuhkan 253 orang lain sebelum peluangnya melewati 50%. Hanya 22 dari 253 pasangan dalam kelompok 23 orang yang melibatkan Anda.

Aturan akar kuadrat dan serangan ulang tahun

Untuk N nilai yang sama mungkinnya, pengulangan menjadi mungkin setelah sekitar 1,2 × √N pengambilan: √365 ≈ 19, dan 1,2 × 19 ≈ 23. Hal ini sangat penting dalam keamanan komputer. Penyerang menggunakan serangan ulang tahun untuk menemukan dua input dengan hash kriptografis yang sama, yaitu tabrakan, misalnya untuk memalsukan tanda tangan digital. Berkat paradoks ulang tahun, mereka membutuhkan percobaan yang jauh lebih sedikit daripada yang diperkirakan intuisi: sekitar 2⁶⁴ untuk hash 128 bit, bukan 2¹²⁸. Itulah sebabnya hash modern seperti SHA-256 memiliki keluaran yang panjang.

Jelajahi di PictorX

Buka paradoks ulang tahun dan sebuah kelompok berisi 23 orang terbentuk di sebuah lingkaran, satu per satu. Setiap pendatang baru menambahkan garis ke setiap orang yang sudah ada, dan keterangan menghitung banyaknya pasangan. Ulang tahun mereka jatuh ke kalender, dan hari dengan dua ulang tahun atau lebih menyala. Di bawahnya, perhitungan untuk ukuran kelompok itu berdampingan dengan proporsi kelompok teruji yang memiliki ulang tahun yang sama, dan grafik menunjukkan peluang untuk setiap ukuran kelompok, baik untuk dua orang mana pun maupun untuk orang yang berulang tahun sama dengan Anda. Tambahkan orang satu per satu, pilih 2 hingga 366 orang, uji hingga 100.000 kelompok dengan kecepatan hingga 10.000 per detik, atau uji setiap ukuran kelompok dan lihat titik-titiknya membentuk kurva.

Pertanyaan yang sering diajukan

Apa itu paradoks ulang tahun?

Fakta mengejutkan bahwa dalam kelompok yang hanya terdiri dari 23 orang, peluang dua di antaranya berulang tahun sama lebih dari 50%: 50,7%.

Mengapa 23 orang sudah cukup?

Karena 23 orang membentuk 253 pasangan, dan setiap pasangan adalah kesempatan untuk ulang tahun yang sama. Kita cenderung hanya menghitung 22 pasangan yang melibatkan diri kita sendiri.

Berapa orang yang dibutuhkan untuk peluang 99%?

57. Dengan 70 orang peluangnya 99,9%, dan dengan 366 orang ulang tahun yang sama pasti terjadi, karena hanya ada 365 hari.

Apa itu serangan ulang tahun?

Serangan terhadap hash kriptografis yang memanfaatkan paradoks ulang tahun: di antara sekitar √N input acak, kemungkinan besar dua di antaranya memiliki nilai hash yang sama dari N kemungkinan nilai, sehingga tabrakan ditemukan jauh lebih cepat daripada dengan mencoba mencocokkan satu hash tertentu.

Apakah hasilnya berubah dengan ulang tahun sungguhan?

Hampir tidak. Ulang tahun sungguhan tidak tersebar benar-benar merata sepanjang tahun, dan sebaran yang tidak merata membuat ulang tahun yang sama sedikit lebih mungkin. 29 Februari, yang datang sekali setiap empat tahun, hampir tidak berpengaruh.