A Random Base Change Algorithm for Permutation Groups

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 Rand(G) producing a random element of G with the uniform distribution and so that the time for each call to 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 log2G). An earlier version of this work appeared in Cooperman and Finkelstein (1992b).