Computing in solvable matrix groups
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 111-120
- https://doi.org/10.1109/sfcs.1992.267813
Abstract
The author announces methods for efficient management of solvable matrix groups over finite fields. He shows that solvability and nilpotence can be tested in polynomial-time. Such efficiency seems unlikely for membership-testing, which subsumes the discrete-log problem. However, assuming that the primes in mod G mod (other than the field characteristic) are polynomially-bounded, membership-testing and many other computational problems are in polynomial time. These problems include finding stabilizers of vectors and of subspaces and finding centralizers and intersections of subgroups. An application to solvable permutation groups puts the problem of finding normalizers of subgroups into polynomial time. Some of the results carry over directly to finite matrix groups over algebraic number fields; thus, testing solvability is in polynomial time, as is testing membership and finding Sylow subgroups.Keywords
This publication has 15 references indexed in Scilit:
- Fast Monte Carlo algorithms for permutation groupsPublished by Association for Computing Machinery (ACM) ,1991
- Finding Sylow normalizers in polynomial timeJournal of Algorithms, 1990
- Number-Theoretic AlgorithmsAnnual Review of Computer Science, 1990
- Computing in quotient groupsPublished by Association for Computing Machinery (ACM) ,1990
- Parallel algorithms for solvable permutation groupsJournal of Computer and System Sciences, 1988
- Permutation groups in NCPublished by Association for Computing Machinery (ACM) ,1987
- Parallel algorithms for permutation groups and graph isomorphismPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Sylow's theorem in polynomial timeJournal of Computer and System Sciences, 1985
- Isomorphism of graphs of bounded valence can be tested in polynomial timeJournal of Computer and System Sciences, 1982
- Polynomial-time algorithms for permutation groupsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980