Subject: Re: RelCache (aka ELF prebinding) news
To: None <email@example.com, firstname.lastname@example.org>
From: der Mouse <mouse@Rodents.Montreal.QC.CA>
Date: 12/03/2002 19:59:21
>> How many random numbers do you have to generate from a selection of
>> N possibilities before it becomes a decent bet that you've got the
>> same number twice? Roughly sqrt(N).
> for actual birthdays, you need 23 people to get a greater than 50%
> chance of a collision, not sqrt(365), which is 19
That's why I said "roughly" and "decent bet" rather than "" and "50%
chance". I think it's something like asymptotically 1.18 sqrt(N);
a description of the math. (Yes, despite the .no and "Forelesninger",
the page is in English.)
> for a prefectly random 32 bit number, you need 77164 samples to
> get greater than 50% chance of a collision.
Yup. .5000001094826516449854984717+ chance of no collision at 77163,
.4999911265252065576437+ at 77164.
>  a 32 bit crc is most decidedly *not* a random 32 bit number.
Well, no, but the structure of CRCs is sufficiently orthogonal to the
structure of ELF files that I think it can mostly be considered one for
purposes of this discussion. The exact chance of a collision doesn't
actually matter anyway; the only question is qualitative - "is it high
enough to worry about".
/~\ The ASCII der Mouse
\ / Ribbon Campaign
X Against HTML email@example.com
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B