From mboxrd@z Thu Jan  1 00:00:00 1970
From: andrey mirtchovski <mirtchov@cpsc.ucalgary.ca>
To: 9fans@cse.psu.edu
Subject: Re: [9fans] compare-by-hash
In-Reply-To: <Pine.SUN.3.90.1030731132027.10772A-100000@magnum.cooper.edu>
Message-ID: <Pine.LNX.4.44.0307311134140.3892-100000@fbsd.cpsc.ucalgary.ca>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=ISO-8859-1
Date: Thu, 31 Jul 2003 11:50:51 -0600
Content-Transfer-Encoding: quoted-printable
Topicbox-Message-UUID: 0d16658e-eacc-11e9-9e20-41e7f4b1d025

Solution: increase the hash size to 320 bits to achieve approx 1 collisio=
n after
2^160 entries :P

Theorem:
                                       =E2=94=8C=E2=94=80=E2=94=80=E2=94=80=
=E2=94=90
Applying a random mapping =CE=B2: =CA=83 =E2=87=92 =CA=83 to  =E2=8E=B7|=CA=
=83|  values is expected to produce about=20
1 collision.=20

andrey

ps: you may need the 10646 fonts to see the unicode typesetting above in
its full glory ;)

On Thu, 31 Jul 2003, Joel Salomon wrote:

> This is a bit late, but...
> A 160-bit hash (assuming "strong" hashing) has a 50% probabilty of=20
> collisions after 2^80 entries. Google "birthday paradox" for the math.
>=20
> --Joel
>=20