From: H. Peter Anvin <hpa@zytor.com>
Date: Sun, 27 Nov 2005 21:24:44 GMT
Subject: Re: Problem merging
Message-ID: <438A241C.5010007@zytor.com>
In-Reply-To: <D8B7EF65-9D0C-4706-B248-4B7C118C16BF@hawaga.org.uk>

Ben Clifford wrote:
> On 24 Nov 2005, at 00:49, Johannes Schindelin wrote:
> 
>>
>> I think nobody is. Since there are infinitely many files having the  same
>> SHA1 (pigeon-hole principle),
> 
> hmm... pigeon-hole principle is just that there exists two files that  
> have the same SHA-1 as each other... doesn't say anything about *all*  
> SHA-1s, though?
> 

There are an infinite number of possible files (specifically, 
aleph-null.)  There are a finite number of possible SHA-1's 
(specifically, 1461501637330902918203684832716283019655932542976.) 
Therefore the pidgeon-hole principle tells you there must be at least 
one SHA-1 value that hashes an infinite number of files (aleph-null, again.)

Given that SHA-1 is believed to be uniformly distributed, it's quite 
likely *ALL* SHA-1's hash an infinite number of files, but the 
pigeon-hole principle can't tell you that.

	-hpa