[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Tue, 18 Apr 2023 17:57:51 +0200
From: magnum <magnumripper@...hmail.com>
To: john-dev@...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 google-fu 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 DES-crypt 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.
