This dissertation investigates deterministic polynomial-time computation in matrix groups over finite fields. Of particular interest are matrix-group problems that resemble testing graph isomorphism. The main results are instances where the problems admit polynomial-time solutions and methods that enable such efficiency.

A permutation-group problem that generalizes graph-isomorphism testing is the problem of finding stabilizers of sets. For an integer constant d > 0, let Γ_d denote the class of finite groups all of whose nonabelian composition factors lie in S_d. A result of Luks asserts that in Γ_d one can find set-stabilizers in polynomial time. The set-stabilizer problem has important generalizations in matrix groups. Let G be a matrix group on a vector space V over a finite field. The vector-stabilizer problem asks: given v ∈ V, find the subgroup of G stabilizing v. The subspace-stabilizer problem asks: given W ⊂ V, find the subgroup of G stabilizing W.

A critical foundation for group computation is the ability to perform testing membership of an element in a group. In matrix groups, a polynomial-time method seems unlikely since membership-testing already subsumes the discrete-log problem. Nevertheless, assuming a polynomial bound on the primes in |G| other than the field characteristic, Luks has found polynomial-time solutions for testing membership and also for finding stabilizers of vectors and subspaces in solvable groups.

The main theme of this dissertation is the generalization of the solvable-matrix-group algorithms to algorithms for matrix groups in Γ_d.

Assuming the same bound on these primes, we establish polynomial-time membership-testing in a broader class than Γ_d: matrix groups all of whose nonabelian composition factors have polynomially bounded orders.

Now assume a polynomial bound on the primes in |G| and the field charac­teristic. Based on the membership-testing algorithm, we then develop a divide-and-conquer paradigm for finding stabilizers of vectors and subspaces in polynomial time for G ∈ Γ_d. This result exploits Babai, Cameron, and Pálfy's theorem on the polynomial orders of primitive groups in Γ_d and Róyai's algorithm for finding irreducible subspaces.