Constructive recognition of classical groups in odd characteristic. (Q731248): Difference between revisions

Let \(G=\langle X\rangle\leq\text{GL}(d,F)\) be a classical group in its natural representation defined over a finite field \(F\) of odd characteristic. The authors consider a `straight-line program' (SLP) for \(g\in G=\langle X\rangle\) as an efficiently stored group word on \(X\) that evaluates to \(g\). They present Las Vegas algorithms to construct standard generators for \(G\) which permit people to write an element of \(G\) as a straight-line program in \(X\). The algorithms run in polynomial-time, subject to the existence of a discrete logarithm oracle for \(F\).