[REBOL] Re: Question about checksum/secure
From: lmecir:mbox:vol:cz at: 19-Nov-2001 17:38
> I hope this isn't a silly question.
> Can the result of checksum/secure be used like a GUID, is it guaranteed to
> be unique?
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).
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.