The inverse of an automorphism in polynomial time
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.
- Algorithms for calculating the inverse of a given \(R\)-automorphism of \(R[x]\)
- Automorphisms of the \(k\)-algebra \(k[X_1, \ldots, X_m]\)
- Automorphisms of polynomial and power series rings
- scientific article; zbMATH DE number 4200410
- A criterion to decide if a polynomial map is invertible and to compute the inverse
- An inversion formula for two polynomials in two variables
- Automorphisms of polynomial and power series rings
- Factoring sparse multivariate polynomials
- Fast computation of discrete Fourier transforms using polynomial transforms
- Functional decomposition of polynomials: the tame case
- Functional decomposition of polynomials: the wild case
- scientific article; zbMATH DE number 3922806 (Why is no real title available?)
- scientific article; zbMATH DE number 3941661 (Why is no real title available?)
- scientific article; zbMATH DE number 3892457 (Why is no real title available?)
- New algorithms for the multidimensional discrete Fourier transform
- On the inversion formula for two polynomials in two variables
- Polynomial decomposition algorithms
- Polynomial decomposition algorithms
- The Jacobian conjecture: Reduction of degree and formal expansion of the inverse
- Using Gröbner bases to determine algebra membership, split surjective algebra homomorphisms determine birational equivalence
- Reversible polynomial automorphisms of the plane: the involutory case
- An application of algebraic geometry to encryption: tame transformation method
- A public key system with signature and master key functions
- scientific article; zbMATH DE number 1497344 (Why is no real title available?)
- CRYPTANALYSIS OF AN IMPLEMENTATION SCHEME OF THE TAMED TRANSFORMATION METHOD CRYPTOSYSTEM
- Algorithms for calculating the inverse of a given \(R\)-automorphism of \(R[x]\)
- Automorphisms of the \(k\)-algebra \(k[X_1, \ldots, X_m]\)
- On the arithmetic of endomorphism ring \(\mathrm{End}(\mathbb{Z}_p \times \mathbb{Z}_{p^m})\)
- Signature of time-reversal symmetry in polynomial automorphisms over finite fields
- Detecting Fully Irreducible Automorphisms: A Polynomial Time Algorithm
- Polynomial ring automorphisms, rational \((w,\sigma )\)-canonical forms, and the assignment problem
This page was built for publication: The inverse of an automorphism in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1190750)
