TY - GEN

T1 - Las Vegas algorithms for matrix groups

AU - Beals, Robert

AU - Babai, Laszlo

PY - 1993

Y1 - 1993

N2 - We consider algorithms in finite groups, given by a list of generators. We give polynomial time Las Vegas algorithms (randomized, with guaranteed correct output) for basic problems for finite matrix groups over the rationals (and over algebraic number fields): testing membership, determining the order, finding a presentation (generators and relations), and finding basic building blocks: center, composition factors, and Sylow subgroups. These results extend previous work on permutation groups into the potentially more significant domain of matrix groups. Such an extension has until recently been considered intractable. In case of matrix groups G of characteristic p, there are two basic types of obstacles to polynomial-time computation: number theoretic (factoring, discrete log) and large Lie-type simple groups of the same characteristic p involved in the group. The number theoretic obstacles are inherent and appear already in handling abelian groups. They can be handled by moderately efficient (subexponential) algorithms. We are able to locate all the nonabelian obstacles in a normal subgroup N and solve all problems listed above for G/N. Most results are even more general and apply (with some additional stipulations) to black-box groups (group elements are strings of uniform length, group operations are performed by an oracle). The algorithms build on a variety of recent randomization techniques, as well as a statistical analysis of various classes of finite simple groups. The classification of the finite simple groups is extensively used, even when the objective is merely to determine the order of the group.

AB - We consider algorithms in finite groups, given by a list of generators. We give polynomial time Las Vegas algorithms (randomized, with guaranteed correct output) for basic problems for finite matrix groups over the rationals (and over algebraic number fields): testing membership, determining the order, finding a presentation (generators and relations), and finding basic building blocks: center, composition factors, and Sylow subgroups. These results extend previous work on permutation groups into the potentially more significant domain of matrix groups. Such an extension has until recently been considered intractable. In case of matrix groups G of characteristic p, there are two basic types of obstacles to polynomial-time computation: number theoretic (factoring, discrete log) and large Lie-type simple groups of the same characteristic p involved in the group. The number theoretic obstacles are inherent and appear already in handling abelian groups. They can be handled by moderately efficient (subexponential) algorithms. We are able to locate all the nonabelian obstacles in a normal subgroup N and solve all problems listed above for G/N. Most results are even more general and apply (with some additional stipulations) to black-box groups (group elements are strings of uniform length, group operations are performed by an oracle). The algorithms build on a variety of recent randomization techniques, as well as a statistical analysis of various classes of finite simple groups. The classification of the finite simple groups is extensively used, even when the objective is merely to determine the order of the group.

UR - http://www.scopus.com/inward/record.url?scp=0027873264&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027873264&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027873264

SN - 0818643706

T3 - Annual Symposium on Foundatons of Computer Science (Proceedings)

SP - 427

EP - 436

BT - Annual Symposium on Foundatons of Computer Science (Proceedings)

A2 - Anon, null

PB - Publ by IEEE

T2 - Proceedings of the 34th Annual Symposium on Foundations of Computer Science

Y2 - 3 November 1993 through 5 November 1993

ER -