Elsevier

Journal of Algebra

Volume 322, Issue 3, 1 August 2009, Pages 833-881
Journal of Algebra

Constructive recognition of classical groups in odd characteristic

Dedicated to John Cannon and Derek Holt on the occasions of their significant birthdays, in recognition of distinguished contributions to mathematics
https://doi.org/10.1016/j.jalgebra.2009.04.028Get rights and content
Under an Elsevier user license
open archive

Abstract

Let G=XGL(d,F) be a classical group in its natural representation defined over a finite field F of odd characteristic. We present Las Vegas algorithms to construct standard generators for G which permit us 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.

Keywords

Classical groups
Constructive recognition

Cited by (0)

This work was supported in part by the Marsden Fund of New Zealand via grant UOA 721. We thank Peter Brooksbank and Cheryl Praeger for detailed commentary and discussion on various drafts of this paper. We thank John Bray, Bill Kantor, Frank Lübeck, Alice Niemeyer, and Robert Wilson for helpful discussions.