2
$\begingroup$

The Fisher-Yates shuffle can produce any permutation of a set of $n$ elements. Is there anything that can do the same for creating an involutive permutation of $n$ elements where $n$ is an even number? This could be used to create involutive S-boxes.

$\endgroup$
2
$\begingroup$

The Fischer-Yates shuffle can be used to generate random (i.e. uniformly distributed) permutations. As mentioned in the comments, generating "any" permutation is trivial. So I'll make the assumption that you want an algorithm to generate random involutions on $\{1, \ldots, n\}$, such that each involution has equal probability.

It is easy to see that any involution $\pi \in \mathrm{Sym}_n$ is the product of disjoint transpositions (i.e. all cycles have length at most two). This observation leads to the following simple strategy to generate random involutions: ($I_n$ below denotes the number of involutions on $n$ symbols)

Choose $1$ to be part of a one-cycle (with probability $I_{n-1} / I_n$) or a two-cycle (with probability $1 - I_{n-1}/I_n = (n-1)I_{n-2}/I_n$), i.e. $\pi(1) = 1$ or $\pi(1) = j$ such that $\pi(j) = 1$. In the former case, one can continue in tail-recursive manner by sampling an involution from $\mathrm{Sym}_{n - 1}$. In the latter case, choose $j \in \{2, \ldots, n\}$ uniformly at random and sample an involution from $\mathrm{Sym}_{n - 2}$ (again, recursively).

An important detail in the procedure above is how to sample with probability $I_{n - 1} / I_n$. It's probably best to precompute these probabilities and store them in a table.

I'm sure many references could be found for this simple method. For instance, the procedure above (with minor differences) can be found in Algorithm 9.4 of Jörg Arndt's thesis. An implementation in C++ can also be found there.

$\endgroup$

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.