paradoks hari ulang tahun

paradoks hut merupakan salah satu paradoks yang muncul sebagai salah satu akibat olahan intelektual pada teori peluang. Paradoks ini sebenarnya merupakan teori yang muncul sebagai jawaban secara khusus masalah peluang kemunculan dua orang mempunyai hari lahir yang sama. Berdasarkan prinsip sarang burung merpati dalam kelompok 366 orang dan asumsi setahun ada 365 hari pasti ada minimal dua orang yang lahir pada hari yang sama. Prinsip ini jelas berbicara kepastian, tetapi dalam kehidupan nyata peristiwa alami erat hubungannya dengan ketidakpastian. Bagaimana jika kita menginginkan sejumlah orang dikumpulkan sehingga peluang dua orang berulang tahun sama paling tidak lima puluh persen. Jawabannya merupakan inti dari paradoks hut, yaitu cukup 23 orang dikumpulkan. Jawaban ini tentu saja tidak mengada-ada semuanya logis secara matematika. Teori inilah yang menjadi pendukung utama masalah pertukaran memori dan waktu sebagai salah satu metode kriptanalisis. Dengan batas kepercayaan yang cukup signifikan seperti ini kita dapat melakukan komputasi yang jauh lebih efisien dibandingkan jika kita melakukan brute-forcing secara menyeluruh (ups, bagaimanapun brute-forcing secara menyeluruh merupakan tindakan konyol). Melihat masalah diatas kita hanya perlu mencari dari 23 orang dibandingkan dengan 366 orang untuk mencari eksistensi dua orang berulang tahun sama.

 

Mari kita bergerak lebih dalam.

 

Untuk suatu fungsi f: X -> Y, dengan Y adalah himpunan n elemen, masalah secara umum yang akan kita bahas adalah:

 

Misalkan p adalah peluang suatu kejadian (0 < p < 1), cari nilai k sehingga untuk setiap k pasang xi, i = 1,2,…,k, anggota X yang berbeda dan perhitungan f(xi), i = 1,2,…,k memenuhi

P(f(xi) = f(xj)) ≥ p, untuk suatu i ≠ j.

Dengan kata lain, dalam paling banyak perhitungan fungsi k kali peluang terjadi tumbukan tidak kurang dari p.

 

Fungsi f harus memenuhi kriteria acak, yaitu memetakan nilai yang uniform di X ke nilai yang uniform di Y. Akibatnya perlu #X > #Y, jika tidak mungkin terjadi beberapa fungsi yang tidak terjadi tumbukan sama sekali.

 

Sebagai contoh, misalkan f marupakan fungsi pengambilan sebuah bola dari keranjang berisi n bola yang diwarnai berbeda satu sama lain, merekam warna bola yang terambil, dan mengembalikan bola ke keranjang. Berarti masalah sekarang adalah mencari k sehingga paling tidak satu kecocokan warna terjadi dengan peluan p.

 

Misalkan yi adalah warna bola pada pengambilan ke-i. Kita akan pertimbangkan peluang jika tumbukan tidak terjadi. Tidak ada masalah pada pengambilan pertama. Pada pengambilan kedua, agar y2 ≠ y1, peluangnya adalah 1 – 1/n. pada pengambilan ketiga untuk menghindari y3 ≠ y1, y3 ≠ y2, peluangnya adalah 1 – 2/n dan seterusnya. Peluang total setelah pengambilan k bola sehingga tidak terjadi tumbukan adalah

 

(1 – 1/n)( 1 – 2/n)…( 1 – (k-1)/n)

 

Untuk n cukup besar dan x relatif kecil, berlaku

 

(1 + x/n)n ≈ ex atau 1 + x/n ≈ ex/n

 

Jadi

 

(1 – 1/n)( 1 – 2/n)…( 1 – (k-1)/n) = ∏(1 + –i/n) ≈ ∏ei/n = e-k(k-1)/2n.

 

Kembali ke masalah awal, dengan menggunakan persamaan terakhir kita dapatkan bahwa peluang agar terjadi tumbukan adalah

 

1 – ek(k-1)/2n.

 

Karena kita menginginkan agar nilai diatas paling tidak p, maka kita samakan terlebih dahulu persamaan terakhir dengan p, yaitu

 

1 – ek(k-1)/2n ≈ p.

 

Selesaikan dalam k, diperoleh

 

k ≈ (2n log(1/(1-p)))1/2.

 

Untuk p = 0.5 dan n = 365, kita peroleh k ≈ 22.49 dan paradoks hut pun terpecahkan. Memang pada pandangan pertama hasil ini cukup bertentangan dengan intuisi, tapi pada kenyataannya tidak. Malah hasil ini memberi dampak signifikan dalam mendisain cryptosystem dan protokol cryptographic. Jika diberikan ciphertext kita dapat mencari plaintext dengan menghitung nilai-nilai fungsi acak untuk data-data yang juga acak sebanyak k perhitungan yang cukup kecil jika dibandingkan dengan mencacah semua kemungkinan data sebagai masukan. Penyerangan seperti ini dikenal sebagai serangan square-root (perhatikan akar n pada persamaan terakhir) atau serangan birthday.

2 pemikiran pada “paradoks hari ulang tahun

  1. Saya udah liat soal ini beberapa bulan lalu. Tapi saya ga pernah memikirkan untuk aproksimasi (1 + x/n)^n ≈ e^x. Saya pikir ini perlu kalkulator atau komputer.

    Thanks!

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s