|
I'm having trouble finding a good method for solving the following problem: If $n$ is a positive integer, let $S_n$ denote the group of permutations of the set $\{1,2,\dots, n\}$. For a permutation $\pi$ in $S_3$, let $e_\pi$ be the bit permutation of bit strings of length 3. For each $\pi \in S_3$ determine the number of collisions of the compression function $h(x) = e_\pi(x) \oplus x$. Does anyone have any advice on how to approach this? |
|||
|
|
This will be the same for all permutations in the same conjugacy class, so you only have to do it for $(12)$, $(123)$ and the identity. For the identity all bit strings are mapped to $000$. For $(12)$, a bit string is mapped to $000$ if bits $1$ and $2$ are the same, and $011$ if bits $1$ and $2$ are different (with four strings mapped to each of the strings). For $(123)$, a bit string is mapped to $000$ if it's constant, and to one of the strings $011$, $101$ and $110$ if it isn't (with two strings mapped to each of those strings). I'm not sure what exactly the "number of collisions" is, but if you know how it's defined you should be able to determine it from the above. |
|||||||||||
|
