Baby-step giant-step algorithms for the symmetric group. (March 2018)

• Record Type: Journal Article
• Authors: Bach, Eric; Sandlund, Bryce
• Is Part Of: Journal of symbolic computation. Volume 85(2018)
• Page Start: 55
• Page End: 71
• Publication Date: 2018-03
• Subjects: Symmetric group -- Group actions -- Discrete logarithm -- Collision algorithm -- Computational group theory; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2017.07.003
• Languages: English
• ISSNs: 0747-7171

Abstract

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 ∈ S, a solution g ∈ 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 Shanks' baby-step / giant-step procedure for ordinary discrete logarithms. Specifically, we compute two sets A, B ⊆ S n such that every permutation of S n can be written as a product ab of elements a ∈ A and b ∈ 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 n ! in size. We also analyze randomized "collision" algorithms for the same problem.