Subject: Re: Problem merging

From: "H. Peter Anvin" <[email-masked]>
Date: Sun, 27 Nov 2005 13:24:44 -0800

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