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:36) 
From:  Alan Schmitt <alan.schmitt@p...> 
Subject:  Computing with big numbers? 
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? Thanks, Alan