Steinberg presentations of black box classical groups in small characteristics

Abstract

The main component of (constructive) recognition algorithms for black box groups of Lie type in computational group theory is the construction of unipotent elements. In the existing algorithms unipotent elements are found by random search and therefore the running time of these algorithms is polynomial in the underlying field sizeqwhich makes them unfeasible for most practical applications [27]. Meanwhile, the input size of recogni- tion algorithms involves only logq. The present paper introduces a new approach to construction of unipotent elements in which the running time of the algorithm is quadratic in characteristicpof the underlying field and is polynomial in logq; for small values ofp(which make a vast and practically important class of problems), the complexity of these algorithms is polynomial in the input size.For PSL2(q),q≡1 mod 4, we present a Monte-Carlo algorithm which constructs a root subgroupU, the maximal torusTnormalizingUand a Weyl group elementwwhich conjugatesUto its opposite. Moreover, we extend this result and construct Steinberg generators for the black box untwisted classical groups defined over a field of odd sizeq=pkwhereq≡1 mod 4. Our algorithms run in time quadratic in characteristicpof the underlying field and polynomial in logqand the Lie ranknof the group.The caseq≡ −1 mod 4 requires the use of additional tools and is treated separately in our next paper [9]. Further, and much stronger results can be found in [6, 7].