Detect by means other than having enough values so that not having a collision is suspect? -----Original Message----- From: math-fun-bounces+cordwell=sandia.gov@mailman.xmission.com [mailto:math-fun-bounces+cordwell=sandia.gov@mailman.xmission.com] On Behalf Of Henry Baker Sent: Tuesday, February 25, 2014 12:17 PM To: math-fun@mailman.xmission.com Subject: [EXTERNAL] [math-fun] Stupid question about hash functions Suppose we have a hash function h(x)=y, x,y in universe U, n=|U|. (We have a simplified situation in which the domain = range.) "Collisions" in hash functions are really bad, due to the Birthday Paradox, so we want h to be 1-1, which in this case means a permutation of U. But permutations are a vanishingly small % of all the functions from U -> U; i.e., n! << n^n n!/n^n ~ sqrt(2 pi n)/exp(n) Shouldn't it get easier & easier to detect a non-random function from U -> U as n increases? Shouldn't this lack of randomness be exploitable? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun