Paper detail

Steinberg presentations of black box classical groups in small characteristics

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 size $q$ which makes them unfeasible for most practical applications \cite{guralnick01.169}. Meanwhile, the input size of recognition algorithms involves only $\log q$. The present paper introduces a new approach to construction of unipotent elements in which the running time of the algorithm is quadratic in characteristic $p$ of the underlying field and is polynomial in $\log q$; for small values of $p$ (which make a vast and practically important class of problems), the complexity of these algorithms is polynomial in the input size. For $\psl_2(q)$, $\qpone$, we present a Monte-Carlo algorithm which constructs a root subgroup $U$, the maximal torus $T$ normalizing $U$ and a Weyl group element $w$ which conjugates $U$ to its opposite. Moreover, we extend this result and construct Steinberg generators for the black box untwisted classical groups defined over a field of odd size $q=p^k$ where $\qpone$. Our algorithms run in time quadratic in characteristic $p$ of the underlying field and polynomial in $\log q$ and the Lie rank $n$ of the group. The case $\qmone$ requires the use of additional tools and is treated separately in our next paper \cite{suko12B}. Further, and much stronger results can be found in \cite{suko12E,suko12F}.