Baby-Step Giant-Step Algorithms for the Symmetric Group

Abstract

We study discrete logarithms in the setting of group actions. Suppose that $G$ is a group that acts on a set $S$. When $r,s\in S$, a solution $g\in G$ to $r^g=s$ can be thought of as a kind of logarithm. In this paper, we study the case where $G=S_n$, and develop analogs to the Shanks baby-step / giant-step procedure for ordinary discrete logarithms. Specifically, we compute two sets $A,B\subseteq S_n$ such that every permutation of $S_n$ can be written as a product $ab$ of elements $a\in A$ and $b\in B$. Our deterministic procedure is optimal up to constant factors, in the sense that $A$ and $B$ can be computed in optimal asymptotic complexity, and $|A|$ and $|B|$ are a small constant from $\sqrt{n!}$ in size. We also analyze randomized "collision" algorithms for the same problem.