An algorithm for solving the factorization problem in permutation groups
A stabilizer chain [\textit{C. Sims}, Comput. Probl. abstract Algebra, Proc. Conf. Oxford 1967, 169-183 (1970; Zbl 0215.10002)] can be used to express elements of a permutation group as words in (given) generators. The words obtained this way however can be very long. To overcome this problem, the author proposes to compute the transversal elements of the stabilizer chain not (as usually done) by an orbit algorithm, but by systematically computing short words in the generators until elements for all transversal positions have been found. This yields a larger strong generating set (SGS) whose elements however are short words in the generators. Thus the standard factorization algorithm using this SGS tends to produce shorter words. Such short words can be useful for practical purposes (like the evaluation of homomorphisms [\textit{C. R. Leedham-Green, C. E. Praeger} and \textit{L. H. Soicher}, J. Symb. Comput. 12, No. 4/5, 527-532 (1991; Zbl 0789.20001)]) even though they are not the shortest possible. The author gives explicit algorithms and lists performance times and word lengths for a couple of examples, using his implementation in the computer algebra system GAP. He notes that the main problem of the algorithm is a situation when long words are needed for some transversal positions as happens for \(S_n=\langle(1,2),(2,3),(3,4),\ldots,(n-1,n)\rangle\).
- scientific article; zbMATH DE number 3989617
- scientific article; zbMATH DE number 96388
- Fast Management of Permutation Groups I
- Efficient representation of perm groups
- scientific article; zbMATH DE number 4057754
- Fast Monte Carlo algorithms for permutation groups
- Computing the order of a solvable permutation group
- A data structure for a uniform approach to computations with finite groups
- scientific article; zbMATH DE number 3871623
- scientific article; zbMATH DE number 4081802
- An improvement to the centralizer algorithm for permutation groups
- scientific article; zbMATH DE number 1263311 (Why is no real title available?)
- Short expressions of permutations as products and cryptanalysis of the algebraic eraser
- Distance in cayley graphs on permutation groups generated by $k$ $m$-Cycles
- Applications of finite non-abelian simple groups to cryptography in the quantum era
This page was built for publication: An algorithm for solving the factorization problem in permutation groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1264436)
