
Date: Tue, 18 Apr 2023 17:57:51 +0200 From: magnum <magnumripper@...hmail.com> To: johndev@...ts.openwall.com 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 bitmap? 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 googlefu has deteriorated or the search engines have become too bloated to be of use anymore. I recall Solar mentioned somewhere (at some time in the last, say, 12 years, lol) that "given n random DEScrypt hashes, we can expect x unique salts" and I believe that's the exact same math. Cheers, magnum
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.