Title :
The inverse of an automorphism in polynomial time
Author :
Dickerson, Matthew
Author_Institution :
Cornell Univ., Ithaca, NY, USA
fDate :
30 Oct-1 Nov 1989
Abstract :
The first known polynomial-time algorithm for computing the inverse of a K-algebra automorphism is presented. The algorithm works over a commutative ring K and is based on a polynomial decomposition algorithm. A polynomial-time algorithm for computing the left composition factor of a multivariate decomposition is also presented. Two related open problems are stated
Keywords :
algebra; computational complexity; K-algebra automorphism; commutative ring; inverse; left composition factor; multivariate decomposition; polynomial decomposition algorithm; polynomial-time algorithm; Algebra; Modules (abstract algebra); Polynomials;
Conference_Titel :
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location :
Research Triangle Park, NC
Print_ISBN :
0-8186-1982-1
DOI :
10.1109/SFCS.1989.63459
