Hacker News new | past | comments | ask | show | jobs | submit login

The expected number of fixed points in a random permutation is 1. This is an application of linearity of expectation: for a random permutation f of size N and a given input X, the probability that f(X) = X is 1/N, i.e. the probability that X is a fix point is 1/N. There are N possible choices of X, and so by linearity of expectation the expected number of fix points is N * 1/N = 1.

This doesn't tell you anything about concentration bounds or whatever, but it's a neat fact nonetheless.




Great to know! Upvoted.

Unfortunately, it's a random mapping, not necessarily a random permutation. An ideal block cipher would be modeled as a random permutation. Though, in this particular case the domain and range are the same, so unless I'm missing something, the expected number of fixed points comes out to 1 by the same reasoning.


Indeed, the expected number of fix points is the same for both permutations and mappings. Quite curious when you think about it, because the distribution of fix points is obviously different! (Consider the case n = 2 for the simplest example: there are mappings with exactly 1 fix point, but every permutation has either 0 or 2 fix points).

Note though that a correct block cipher is necessarily a permutation, because it's invertible (by definition, a permutation is just an invertible mapping with domain and range equal). A hash function on the other hand needn't be a permutation even when you restrict the domain to inputs of the same bit length as the hash output.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: