**Subject:** Re: RelCache (aka ELF prebinding) news

**To:** None *<tech-kern@netbsd.org, tech-userlevel@netbsd.org>*

**From:** der Mouse *<mouse@Rodents.Montreal.QC.CA>*

**List:** tech-userlevel

**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);
http://www.ii.uib.no/~oyvind/I248/Forelesninger/LectureNotes8.html has
a description of the math. (Yes, despite the .no and "Forelesninger",
the page is in English.)
> for a prefectly random 32 bit number[1], you need 77164 samples to
> get greater than 50% chance of a collision.
Yup. .5000001094826516449854984717+ chance of no collision at 77163,
.4999911265252065576437+ at 77164.
> [1] 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 mouse@rodents.montreal.qc.ca
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B