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.9 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 mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id C93BBBBAF for ; Mon, 1 Dec 2008 15:29:23 +0100 (CET) X-IronPort-AV: E=Sophos;i="4.33,695,1220220000"; d="sig'?scan'208";a="20606759" Received: from concorde.inria.fr ([192.93.2.39]) by mail1-smtp-roc.national.inria.fr with ESMTP; 01 Dec 2008 15:29:23 +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 mB1ETIoD004925 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Mon, 1 Dec 2008 15:29:23 +0100 X-IronPort-AV: E=Sophos;i="4.33,695,1220220000"; d="sig'?scan'208";a="20606758" Received: from charm.inrialpes.fr ([194.199.25.104]) by mail1-relais-roc.national.inria.fr with ESMTP/TLS/AES128-SHA; 01 Dec 2008 15:29:23 +0100 Message-Id: <8BC5124F-270D-4A9E-B302-D366A8749001@polytechnique.org> From: Alan Schmitt To: caml-list@inria.fr In-Reply-To: <4933DE26.2030705@ens-lyon.org> Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha1; boundary="Apple-Mail-10-726458436" Content-Transfer-Encoding: 7bit Mime-Version: 1.0 (Apple Message framework v929.2) Subject: Re: [Caml-list] Computing with big numbers? Date: Mon, 1 Dec 2008 15:29:21 +0100 References: <1A5BFA46-376C-41BB-B357-8A7899C600C6@polytechnique.org> <4933DE26.2030705@ens-lyon.org> X-Pgp-Agent: GPGMail d55 (v55, Leopard) X-Mailer: Apple Mail (2.929.2) X-Miltered: at concorde with ID 4933F4BE.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; schmitt:01 schmitt:01 wikipedia:01 wikipedia:01 wiki:01 wiki:01 wrote:01 caml-list:01 probability:01 jambon:01 alan:02 alan:02 linking:02 outputs:04 correctly:04 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-10-726458436 Content-Type: text/plain; charset=ISO-8859-1; format=flowed; delsp=yes Content-Transfer-Encoding: quoted-printable On 1 d=E9c. 08, at 13:52, Martin Jambon wrote: > 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 Thank you for the link, this was very informative. And there is even a =20= table linking desired probability of collision to number of outputs in =20= this page: http://en.wikipedia.org/wiki/Birthday_attack Alan= --Apple-Mail-10-726458436 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) iEYEARECAAYFAkkz9MEACgkQNIAqM4hFUWhLqACfRD00a0Dlzpzjv4H265Jo03uS U1QAoIwjC9lTo1PSwO5Nn7uZI3dZT77X =X+dR -----END PGP SIGNATURE----- --Apple-Mail-10-726458436--