Cooperman, Gene; Finkelstein, Larry A random base change algorithm for permutation groups. (English) Zbl 0835.20007 J. Symb. Comput. 17, No. 6, 513-528 (1994). Summary: A new random base change algorithm is presented for a permutation group \(G\) acting on \(n\) points whose worst case asymptotic running time is better for groups with a small to moderate size base than any known deterministic algorithm. To achieve this time bound, the algorithm requires a random generator \(\text{Rand}(G)\) producing a random element of \(G\) with the uniform distribution and so that the time for each call to \(\text{Rand}(G)\) is bounded by some function \(f(n,G)\). The random base change algorithm has probability \(1-1/|G|\) of completing in time \(O(f(n,G)\log|G|)\) and outputting a data structure for representing the point stabilizer sequence relative to the new ordering. The algorithm requires \(O(n\log|G|)\) space and the data structure produced can be used to test group membership in time \(O(n\log|G|)\). Since the output of this algorithm is a data structure allowing generation of random group elements in time \(O(n\log|G|)\), repeated application of the random base change algorithms for different orderings of the permutation domain of \(G\) will always run in time \(O(n\log^2|G|)\). An earlier version of this work appeared [the authors, J. Symb. Comput. 12, 475-497 (1991; Zbl 0790.20006)]. Reviewer: M.Szalay (Budapest) Cited in 1 ReviewCited in 1 Document MSC: 20B40 Computational methods (permutation groups) (MSC2010) 20P05 Probabilistic methods in group theory 68W30 Symbolic computation and algebraic computation 20-04 Software, source code, etc. for problems pertaining to group theory 20F05 Generators, relations, and presentations of groups Keywords:random base change algorithms; permutation groups; asymptotic running times; random generators; random elements; point stabilizer sequences; group membership Citations:Zbl 0790.20006 Software:Cayley; GAP PDFBibTeX XMLCite \textit{G. Cooperman} and \textit{L. Finkelstein}, J. Symb. Comput. 17, No. 6, 513--528 (1994; Zbl 0835.20007) Full Text: DOI