FAST MONTE-CARLO ALGORITHMS FOR PERMUTATION-GROUPS

We introduce new, elementary Monte Carlo methods to speed up and great ly simplify the manipulation of permutation groups (given by a list of generators). The methods are of a combinatorial character, using only elementary group theory. The key idea is that under certain condition s, ''random subproducts'' of the generators successfully emulate truly random elements of a group. We achieve a nearly optimal O(n(3) log(c) n) asymptotic running time for membership testing, where n is the siz e of the permutation domain. This is an improvement of two orders of m agnitude compared to known elementary algorithms and one order of magn itude compared to algorithms which depend on heavy use of group theory . An even greater asymptotic speedup is achieved for normal closures, a key ingredient in group-theoretic computation, now constructible in Monte Carlo time O(n(2) log(c) n), i.e., essentially linear time (as a function of the input length). Some of the new techniques are suffici ently general to allow polynomial-time implementations in the very gen eral model of ''black box groups'' (group operations are performed by an oracle). In particular, the normal closure algorithm has a number o f applications to matrix-group computation. It should be stressed that our randomized algorithms are not heuristic: the probability of error is guaranteed not to exceed a bound epsilon > 0, prescribed by the us er, The cost of this requirement is a factor of \log epsilon\ in the r unning time. (C) 1995 Academic Press, Inc.