Polynomial over finite field: permutation polynomial?

Let's assume you have a polynomial over a finite field $\F_q$, defined in Sage. How can you tell whether it's a permutation polynomial? That is, when is the corresponding function $\F_q\to\F_q$ bijective?

This is how you might have a polynomial over $\F_q$ defined in Sage:

Here, the variable $x$ refers the element $x$ in the isomorphism $\F_q \cong \F_p[x]/\alpha(x)$ and $t$ is the variable in the polynomial ring $\F_q[t]$. Is $f$ a permutation polynomial? That of course depends on what $q$ is.

Ideally, you could write something along the lines of "f.as_function().is_surjective()", but no such functions exist in Sage. So you have to write your own:

(Added 2018-03-22: check out Gerd Hübner's improvement in the comments!)

The function here is written so that it can also take integer polynomials, which could be useful if you want to consider a polynomial modulo a bunch of primes. Here, "S(f)" converts "f" to a polynomial with coefficients in "GF(q)". Basically, this function tests whether "f" as a function is surjective (and hence bijective). Now you can use this function to print out all permutation polynomials of a given degree over a given finite field. For example:

This gives the output:

Note: when this was posted, the title was wrong. It has now been corrected.


  • Gerd Hübner says:

    The code could be significantly enhanced:

Leave a comment

Fields marked with * are required. LaTeX snippets may be entered by surrounding them with single dollar signs. Use double dollar signs for display equations.