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