Posted by Jason Polak on 18. February 2018 · 2 comments · Categories: computer-science · Tags: , ,

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.

2 Comments

  1. Gerd Hübner

    The code could be significantly enhanced:

    • Thank you for your improvement! Yes, that obviates my cumbersome length testing. Great!

      I took the liberty of adding pre tags around it so that it would format with the indentation you provided!

Leave a Reply

Your email address will not be published. Required fields are marked *