I'm looking to find all the Involutory keys for the permutation cipher where m=4. A key where ek(x) = dk(x)
I notice that a Non-Involuntary Key for a permutation cipher in m=4 is a key where we have a 3 cycle. So for example the key (1,3,4,2)
While a Involutory key for a permutation cipher in m=4 is one that is composed of 2 cycles. For example (1,2,4,3)
So Basically where an element is swapped with only one other element. I have the following cases
(x1 -> x1) (x2 -> x2) (x3 -> x4)
i.e. Two numbers are fixed to themselves and one isn't
or
(x1->x2)(x2->x3)
i.e. Two numbers are swapped with one another
or
(x1 -> x1)(x2 -> x2)(x3 -> x3)(x4 -> x4)
i.e Each number is fixed to itself.
From these cases I'm confused how I would deduce the number of involutory keys. For example in the case if I have 4 choices for the first fixed number multiplied by 3 choices for the second fixed number and 1 choice for the last two fixed numbers I'd have 12 choices.
But combining that with the second case I'd already be at 24 different permutations which cant possibly be right.
Best Answer
A key for a permutation cipher is of course a permutation $\sigma \in S_n$.
It is self-inverse iff $\sigma^2 = e$, where $e$ is the identity permutation.
We can write any $\sigma \in S_n$ as a product of disjoint cycles in an essentially unique way (up to order of the cycles and leaving out or adding 1-cycles like $(x)$), and so we need all cycles of $\sigma$ to be self-inverse as well. So we can only use $2$-cycles and $1$-cycles. Of course $e$ itself (all $1$-cycles) is one solution. Then we have the cycle structure $2,1,1 $ of which we have $\binom{4}{2} = 6$ (we pick the two points in the $2$-cycle in an unordered way from the $4$ points. And finally we have cycle structure $2,2$, of which there are $\frac{4!}{2! 2! 2!} = \frac{24}{8} = 3$ (or by hand $(13)(24), (12)(34),(14)(23)$).
So we have $1 + 6 + 3 = 10$ many self-inverse keys.