Sylow subgroups in parallel

Sylow subgroups are fundamental in the design of asymptotically efficient g roup-theoretic algorithms, just as they have been in the study of the struc ture of finite groups. We present efficient parallel (NC) algorithms for fi nding and conjugating Sylow subgroups of permutation groups, as well as for related problems. Polynomial-time solutions to these problems were obtaine d more than a dozen years ago, exploiting a well-developed polynomial-time library. We replace some of those highly sequential procedures with ones th at work through a polylog-length normal series that is a by-product of NC m embership-testing. As in previous investigations, we reduce to the base cas e of simple groups, and handle this by a case-by-case analysis that depends heavily upon the classification of finite simple groups. (C) 1999 Academic Press.