An Algorithm for Solving the Factorization Problem in Permutation Groups

The factorization problem in permutation groups is to represent an elementgof some permutation groupGas a word over a given setSof generators ofG. For practical purposes, the word should be as short as possible, but must not be minimal. Like many other problems in computational group theory, the problem can be solved from a strong generating set (SGS) and a base ofG. Different algorithms to compute an SGS and a base have been published. The classical algorithm is the Schreier–Sims method. However, for factorization an SGS is needed that has all its elements represented as words overS. The existing methods are not suitable, because they lead to an exponential growth of word lengths. This article presents a simple algorithm to solve the factorization problem. It is based on computing an SGS with elements represented by relatively short words over the generators.