From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.1 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id 54118BBAF for ; Mon, 1 Dec 2008 13:53:20 +0100 (CET) X-IronPort-AV: E=Sophos;i="4.33,695,1220220000"; d="scan'208";a="19750524" Received: from concorde.inria.fr ([192.93.2.39]) by mail3-smtp-sop.national.inria.fr with ESMTP; 01 Dec 2008 13:53:19 +0100 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id mB1CrHTa002879 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Mon, 1 Dec 2008 13:53:19 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AjAAADhtM0lCbwQZkWdsb2JhbACTSwEBAQEJCwoHEQS7FYJ9 X-IronPort-AV: E=Sophos;i="4.33,695,1220220000"; d="scan'208";a="20599830" Received: from out1.smtp.messagingengine.com ([66.111.4.25]) by mail1-smtp-roc.national.inria.fr with ESMTP; 01 Dec 2008 13:53:17 +0100 Received: from compute1.internal (compute1.internal [10.202.2.41]) by out1.messagingengine.com (Postfix) with ESMTP id 82DA01C9F05; Mon, 1 Dec 2008 07:53:16 -0500 (EST) Received: from heartbeat2.messagingengine.com ([10.202.2.161]) by compute1.internal (MEProxy); Mon, 01 Dec 2008 07:53:16 -0500 X-Sasl-enc: vNCSkv9Ms1yoFp6t8Hq3WwPpj+toKeDzWOCukEN+5Vo1 1228135996 Received: from [192.168.1.10] (ALyon-157-1-112-167.w90-41.abo.wanadoo.fr [90.41.103.167]) by mail.messagingengine.com (Postfix) with ESMTPSA id DA6B4205AE; Mon, 1 Dec 2008 07:53:15 -0500 (EST) Message-ID: <4933DE26.2030705@ens-lyon.org> Date: Mon, 01 Dec 2008 13:52:54 +0100 From: Martin Jambon User-Agent: Thunderbird 2.0.0.17 (X11/20081008) MIME-Version: 1.0 To: Alan Schmitt Cc: caml-list@inria.fr Subject: Re: [Caml-list] Computing with big numbers? References: <1A5BFA46-376C-41BB-B357-8A7899C600C6@polytechnique.org> In-Reply-To: <1A5BFA46-376C-41BB-B357-8A7899C600C6@polytechnique.org> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 4933DE3D.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ens-lyon:01 schmitt:01 hashes:01 hashes:01 hash:01 bignum:01 ocaml:01 ocaml's:01 ocaml:01 wikipedia:01 wikipedia:01 wiki:01 wrote:01 caml-list:01 probability:01 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/