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 i n S

, a solution

g i n 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 s u b s e t e q S_{n}

such that every permutation of

S_{n}

can be written as a product

a b

of elements

a i n A

and

b i n 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

s q r t n!

in size. We also analyze randomized "collision" algorithms for the same problem.

Recommendations

Cited In (3)

This page was built for publication: Baby-step giant-step algorithms for the symmetric group