Question about checksum/secure

No, hashing is a many-to-one operation, mapping from an infinite space (arbitrarily long string series) to a finite space (string series of length 20), so there always has to be the chance of collisions. The chance of a collision is very small though, especially if you deal with a small number of values, say, less than a billion billion billion :-). For any two arbitrary strings to have the same checksum the chance is 1/(2^160). For at least one collision among n strings the chance is n/(2^160) (for n <= 2^160, obviously). -- Holger Kruse [holger--rebol--com]

Hm a billion billion billion, guess it will be a while before my hardward threatens that, however I suppose some rarely used collision detection is in order. Next (and hopefully last) question then is, is the checksum/secure method something that could change? I was thinking of using it for example to generate a filename by doing checksum/secure on the content of a text file, but I think the question is useful for understanding encryption keys as well. Many thanks. Brett.

<</Brett>> <<Holger>> No, hashing is a many-to-one operation, mapping from an infinite space (arbitrarily long string series) to a finite space (string series of length 20), so there always has to be the chance of collisions. The chance of a collision is very small though, especially if you deal with a small number of values, say, less than a billion billion billion :-). For any two arbitrary strings to have the same checksum the chance is 1/(2^160). For at least one collision among n strings the chance is n/(2^160) (for n <= 2^160, obviously). -- Holger Kruse [holger--rebol--com] <</Holger>> Your second formula is incorrect for any n except for (n = 2 ** 160). Especially it is incorrect for (n = 2), where it yields twice as much as it should. OTOH for higher n, (2 < n) and (n < (2 ** 160)), the probability of a collision may be much higher than your formula yields. The correct formula should be: m: 2 ** 160 q: 1 * (1 - (1 / m)) * (1 - (2 / m)) * ... * (1 - (n - 1 / m)) p: 1 - q , where Q is the probability that no collision occurs.

Thanks, you are right. I was thinking about having m-i in the denominator, so most parts would conveniently cancel out, but it is really m all the time... So the chance for a collision among n elements seems to be 1 - (m! / ((m-n)! * m^n)) -- Holger Kruse [holger--rebol--com]

(...) So the chance for a collision among n elements seems to be 1 - (m! / ((m-n)! * m^n)) -- Holger Kruse [holger--rebol--com] If I use the formula correctly, the probability of a collision in a set of 1 M samples is somewhere around 2 ** -120.