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?

  • $\begingroup$ Anyone have any tips? Thanks! $\endgroup$ – willow Apr 22 '13 at 15:54

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.

  • $\begingroup$ Thanks for the response, joriki. Why is it that for the identity all bit strings are mapped to 000? For instance, one of the bit strings of length 3 is 111. Wouldn't the identity permutation map this to itself? I'm trying to figure out where exactly my confusion lies. Thanks again! $\endgroup$ – willow Apr 24 '13 at 16:06
  • $\begingroup$ @willow: Yes, the identity permutation maps this string to itself. But the value of the compression function isn't $e_\pi(111)=111$, but $e_\pi(111) \oplus 111=111\oplus111=000$. $\endgroup$ – joriki Apr 24 '13 at 16:16
  • $\begingroup$ Ah ok, yes, I hadn't taken that next step and computed the compression function yet. Thanks. $\endgroup$ – willow Apr 24 '13 at 16:27
  • $\begingroup$ Oh, and just to clarify what "number of collisions" is: it's when the compression function maps two different inputs to the same output, i.e. $h(x) = h(x')$ but $x \neq x'$. So, if $\pi$ is the identity permutation then there is a collision for $h(000)$ and $h(111)$ since $e_\pi(000) \oplus 000 = 000 \oplus 000 = 000 = 111 \oplus 111 = e_\pi(111) \oplus 111$. At least that's my understanding. Thanks again! $\endgroup$ – willow Apr 24 '13 at 16:34
  • $\begingroup$ @willow: I was aware what a collision is; I just wasn't sure what exactly the number of collisions is. If four strings are mapped to the same string, is that one collision (one multiply achieved result), or three collisions (three times when the strings are mapped one after the other that a string is mapped to a string that had already been obtained), or six collisions (six pairs of strings that are mapped to the same string)? $\endgroup$ – joriki Apr 24 '13 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.