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

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20081201 (12:53) 
From:  Martin Jambon <martin.jambon@e...> 
Subject:  Re: [Camllist] 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 > equiprobability of every hash.) > > The brute force approach is simply to enumerate the noncollision > probability for k different hashes, and compute until it becomes lower > than 1. This probability is (writing N for 2 ^ 128): > N * (N1) * (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 * (Nk)!), 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 socalled 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/