Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Tue, 18 Apr 2023 17:57:51 +0200
From: magnum <>
Subject: Birthday paradox

Hi folks,

Can anyone point me to a (approximation) formula for the birthday 
paradox, where for example we have a bitmap with 4096 bits and populate 
it with 1024 random bits. What is the expected number of bits set in the 

I think the answer is ~907, as that's what I'm seeing in my experiments 
- and also what this simple script shows:

$ perl -e '$n=0; $s=0; while ($n < 1000) { my %nums = undef; foreach 
(0..1023) { $nums{int(rand(4096))} = 1; } $n++; $s += scalar 
keys(%nums); print "Average ", int($s/$n), "\r"; } print "\n";'
Average 907

I settles at 907 in just 10 rounds. But what is a good formula for 
calculating this, given n=1024 and d=4096? Either my google-fu has 
deteriorated or the search engines have become too bloated to be of use 

I recall Solar mentioned somewhere (at some time in the last, say, 12 
years, lol) that "given n random DES-crypt hashes, we can expect x 
unique salts" and I believe that's the exact same math.


Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.