We study the problem of inverting a bijective polynomial map F: Fqn→ Fqnover a finite field Fq. Our interest mainly stems from the case where F encodes a permutation given by some cryptographic scheme. Given y(0)∈ Fqn, we are able to compute the value x(0)∈ Fqnfor which F(x(0)) = y(0)holds in time O(LnO(1)δ4) up to logarithmic terms. Here L is the cost of the evaluation of F and δ is a geometric invariant associated to the graph of the polynomial map F, called its degree.

We present a probabilistic seminumerical algorithm that computes the differential Hilbert function associated to a differential rational mapping. This algorithm explicitly determines the set of variables and derivatives which can be arbitrarily fixed in order to locally invert the differential mapping under consideration. The arithmetic complexity of this algorithm is polynomial in the input size.