Recognising simplicity of black-box groups by constructing involutions and their centralisers

We investigate the complexity of constructing involutions and their centralisers in groups of Lie type over finite fields of odd order, and discuss applications to the problem of deciding whether a matrix group, or a black-box group of known characteristic, is simple. We show that if the characteristic is odd, then simplicity can be recognised in Monte Carlo polynomial time. (C) 2010 Elsevier Inc. All rights reserved.