Computing Polynomial Composition Factors and Inverses of Automorphisms in Polynomial Time
Loading...
No Access Until
Permanent Link(s)
Collections
Other Titles
Authors
Abstract
The problem of determining when an endomorphism on a polynomial ring is an automorphism and, when it is, the problem of computing its inverse are long standing problems which have received much attention both recently and in the past [BCW], [N], [NS], [SS]. There has also been much attention given recently to various problems relating to the functional decomposition of polynomials [AT], [BZ], [D], [G1], [G2], [GKL], [KL]. In this paper, we present the first polynomial time algorithm for computing the left composition factor of a multivariate polynomial decomposition and we use that result in the first polynomial time algorithm for computing the inverse of an automorphism on a polynomial ring. Finally, we show how these algorithms can be used to determine when an endomorphism is an automorphism.
Journal / Series
Volume & Issue
Description
Sponsorship
Date Issued
1988-12
Publisher
Cornell University
Keywords
computer science; technical report
Location
Effective Date
Expiration Date
Sector
Employer
Union
Union Local
NAICS
Number of Workers
Committee Chair
Committee Co-Chair
Committee Member
Degree Discipline
Degree Name
Degree Level
Related Version
Related DOI
Related To
Related Part
Based on Related Item
Has Other Format(s)
Part of Related Item
Related To
Related Publication(s)
Link(s) to Related Publication(s)
References
Link(s) to Reference(s)
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-955
Government Document
ISBN
ISMN
ISSN
Other Identifiers
Rights
Rights URI
Types
technical report