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.8 required=5.0 tests=AWL,SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 6DD00BBAF for ; Mon, 1 Dec 2008 13:36:53 +0100 (CET) X-IronPort-AV: E=Sophos;i="4.33,695,1220220000"; d="sig'?scan'208";a="32023383" Received: from discorde.inria.fr ([192.93.2.38]) by mail4-smtp-sop.national.inria.fr with ESMTP; 01 Dec 2008 13:36:53 +0100 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id mB1CaqQ1002935 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Mon, 1 Dec 2008 13:36:53 +0100 X-IronPort-AV: E=Sophos;i="4.33,695,1220220000"; d="sig'?scan'208";a="20598835" Received: from charm.inrialpes.fr ([194.199.25.104]) by mail1-relais-roc.national.inria.fr with ESMTP/TLS/AES128-SHA; 01 Dec 2008 13:36:52 +0100 Message-Id: <1A5BFA46-376C-41BB-B357-8A7899C600C6@polytechnique.org> From: Alan Schmitt To: caml-list@inria.fr Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha1; boundary="Apple-Mail-1-719707152" Content-Transfer-Encoding: 7bit Mime-Version: 1.0 (Apple Message framework v929.2) Subject: Computing with big numbers? Date: Mon, 1 Dec 2008 13:36:50 +0100 X-Pgp-Agent: GPGMail d55 (v55, Leopard) X-Mailer: Apple Mail (2.929.2) X-Miltered: at discorde with ID 4933DA64.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; schmitt:01 schmitt:01 hashes:01 hashes:01 hash:01 bignum:01 ocaml:01 ocaml's:01 ocaml:01 probability:01 enumerate:01 probability:01 alan:02 alan:02 floats:02 X-Attachments: type="application/pgp-signature" name="PGP.sig" name="PGP.sig" This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --Apple-Mail-1-719707152 Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit 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? Thanks, Alan --Apple-Mail-1-719707152 content-type: application/pgp-signature; x-mac-type=70674453; name=PGP.sig content-description: This is a digitally signed message part content-disposition: inline; filename=PGP.sig content-transfer-encoding: 7bit -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.8 (Darwin) iEYEARECAAYFAkkz2mIACgkQNIAqM4hFUWgO9ACgkGGE/+Dtxc/7Rekxn9w/VMMS a8oAmQGsCD3qCN8J+iD6o4x6424PB/js =XmQY -----END PGP SIGNATURE----- --Apple-Mail-1-719707152--