> ... We can ask what is the > probability of a collision between f and g, i.e. that there exists > some value, x, in S such that f(x) = g(x)?
But then you didn't answer your own question. You gave the expected number of collisions, but not the probability that at least one exists. That probability the sum over k from 1 to 2^128 of (-1)^(k+1)/k!, or about as close to 1-1/e as makes no difference. But here's the more interesting question. If S = Z/2^128 and F is the set of all bijections S->S, what is the probability that a set G of 2^128 randomly chosen members of F contains no two functions f1, f2 such that there exists x in S such that f1(x) = f2(x)? G is a relatively miniscule subset of F but I'm thinking that the fact that |G| = |S| makes the probability very, very small. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]