We study discrete logarithms in the setting of group actions. Suppose that G is a group that acts on a set S. When r and s are elements of S, a solution 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 subsets A and B of S n , such that every permutation in S n  can be written as a product ab of elements from A and B. Our deterministic procedure is close to optimal, in the sense that A and B can be computed efficiently and |A| and |B| are not too far from sqrt(n!) in size. We also analyze randomized "collision" algorithms for the same problem.
['Eric Bach', 'Bryce Sandlund']
Baby-Step Giant-Step Algorithms for the Symmetric Group