The inverse of an automorphism in polynomial time (Q1190750)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The inverse of an automorphism in polynomial time |
scientific article |
Statements
The inverse of an automorphism in polynomial time (English)
0 references
26 September 1992
0 references
A \(K\)-endomorphism of a polynomial ring \(K[\vec x]\) is a mapping of the polynomial ring to itself which preserves addition and multiplication and which fixes every element \(k\) of \(K\). Problem 1 (Endomorphism invertibility) Let \(\sigma : x_ i \mapsto h_ i (\vec x)\) for \(1 \leq i \leq d\) be an endomorphism over a polynomial ring \(K [\vec x]\) given by the coefficients of the polynomials \(h_ i \in K [\vec x]\). Determine if \(\sigma\) is invertible, and if it is compute its inverse. A subproblem of problem 1 is the following: Problem 2 (Inverse of an automorphism) Let \(\sigma : x_ i \mapsto h_ i (\vec x)\) for \(1 \leq i \leq d\) be an automorphism over a polynomial ring \(K[\vec x]\) given by the coefficients of the polynomials \(h_ i \in K [\vec x]\). Compute the inverse of \(\sigma\). In this paper we give a new solution to problem 2 which works over any commutative ring \(K\) and requires a number of arithmetic operations which is polynomial in the dense representation of the input and output polynomials. Our algorithm for problem 2 also leads to a new, exponential time solution to problem 1 in the case where \(K\) is a field.
0 references
endomorphism of a polynomial ring
0 references
endomorphism invertibility
0 references
inverse of an automorphism
0 references