We present new algorithms for computation in permutation groups. These enable an order-of-magnitude improvement in the worst-case analysis af the basic permutation-group problems, including membership­ testing and computing the order of the group. For deeper questions about the group, including finding composition factors, we realize an improvement of up to four orders of magnitude. These and other essential investigations are all accomplished in O(n⁴ log^c n) time.

The new machinery is distinguished by its recognition and use of the intrinsic structure of the group at hand. Notably, this comes into play precisely when the routine divide-and-conquer of the set (i.e., orbits, imprimitivity blocks) bottoms out (at primitive groups). The struc­ture of large primitive groups allows an augmentation of the underlying set that readmits naive decomposition of the problem. As a result, the new base cases are restricted to "small" groups or full alternating groups Another advance is our handling of the latter where in addition to speeding up known methods by an order of magnitude, we eliminate yet an additional n² in a superfast Las Vegas algorithm for this frequent subcase.

Our timing analyses depend, in several ways and probably unavoidably, on consequences of the Classification of Finite Simple Groups.