Matt Crawford wrote: >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)?
Vanishingly small, as you guessed. Fix x0 in S. Your probability is at most the probability that G has no two functions f1, f2 with f1(x0) = f2(x0). The latter is the same as the probability that a set of 2^128 randomly chosen 128-bit values contains no repeated elements, which is indeed vanishingly small (it is (2^128)! / (2^128)^(2^128), which is something like 1/e^(2^128)). --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
