This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Computing with big numbers?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2008-12-01 (12:53) From: Martin Jambon Subject: Re: [Caml-list] Computing with big numbers?
Alan Schmitt wrote:
> Hello,
>
> In preparation for a talk I'm going to give, I wanted to estimate how
> good 128 bits MD5 hashes were: how many hashes must be taken before the
> probability for a collision become non negligible? (I'm assuming
> equi-probability of every hash.)
>
> The brute force approach is simply to enumerate the non-collision
> probability for k different hashes, and compute until it becomes lower
> than 1. This probability is (writing N for 2 ^ 128):
> N * (N-1) * (N - 2) * ... * (N - k)
> ---------------------------------------
> N^k
>
> I tried computing this using the bignum library that comes with OCaml,
> and it slows down to a crawl very fast (for k ~ 1000).
>
> So I tried to be more subtle and approximate the result (using
> Stirling's approximation of factorials), but OCaml's floats are not
> precise enough to yield anything significant. (I'm trying to compute the
> log of the approximation of N! / (N^k * (N-k)!), which is N (ln N) - N -
> (k (ln N) + (N - k)(ln (N - k)) - (N - k)).)
>
> Is there a library with better floating point precision than the OCaml one?

If I understand your problem correctly, this is the so-called birthday
problem with 2^128 days in a year. The Wikipedia article gives useful
approximations:

http://en.wikipedia.org/wiki/Birthday_problem

Martin

--
http://mjambon.com/