From: "David Schwartz" <davids@webmaster.com>
To: <jlnance@unity.ncsu.edu>, <root@mauve.demon.co.uk>
Cc: <linux-kernel@vger.kernel.org>
Subject: RE: Lockless file readingu
Date: Fri, 29 Aug 2003 04:55:39 -0700
Message-ID: <MDEHLPKNGKAHNMBLJOLKOEPOFMAA.davids@webmaster.com>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: 7bit
Importance: Normal
In-Reply-To: <20030829100011.GA663@ncsu.edu>
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 2126
Lines: 49


> On Fri, Aug 29, 2003 at 12:44:00AM +0100, root@mauve.demon.co.uk wrote:

> > Of course it dowesn't.
> > The probability gets rather smaller as numbers go down, and bigger as
> > they go up.
> > With 2^128 bits, the chance of a a collision between 2^64
> > randomly chosen
> > pictures is 50%.
> > At 2^54 pictures, it's about one in a million, and at 2^34 (enough for
> > several pictures of everyone alive) one in a billion billion.
> > At more common numbers of pictures (say 2^14) it becomes vanishingly
> > unlikely for anyone to have two matching pictures (even with
> > several billion
> > archives)

> Be careful.  I remember discussing in probability class the liklyhood that
> two people in a room with N people have the same birthday.  N
> does not have
> to be anywhere close to 365 for your probability of a collision
> to be greater
> than 50%.  I forget what the exact number is but its less than 30.  The
> image problem sounds similar, depending on exactly how you phrase it.

	He's saying that with 2^128 possible hash values, you get a collision with
50% probability with roughly 2^64 pictures. Analogously for the birthday
paradox, with 365 possible birthdays (about 2^8), you get a collision with
50% probability with less than 30 people (about 2^5).

	Now does 5 really seem to be that much less than 8? His math is right and
so is yours. With 2^N possible values, all equally likely, you get a
collision with 50% probability in roughly 2^((N+1)/2).

	You'll note that the birthday paradox doesn't seem so suprising in
exponential notation. In the case of MD5, with
340,282,366,920,938,463,463,374,607,431,768,211,456 possible hashes, you get
a 50% chance of a collision in roughly
12,912,720,851,596,686,131 hashes. So that could seem fairly surprising when
you take it out of exponential notation too. (Just compare the lengths of
the two numbers.)

	DS


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/