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:

1 2 3 |
R.<x> = GF(q) S.<t> = PolynomialRing(R) f = 1 + x*t^2 |

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 |
def isPermutationPolynomial(f, q): R.<x> = GF(q) S.<t> = PolynomialRing(R) f = S(f) image = [] for i in R: temp = f(i) if not temp in image: image.append(temp) if len(image) == q: return(True) else: return(False) |

(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:

1 2 3 4 5 6 |
q = 4 R.<x> = GF(q) S.<t> = PolynomialRing(R) for f in S.polynomials(of_degree=2): if isPermutationPolynomial(f, q): print( f ) |

This gives the output:

1 2 3 4 5 6 7 8 9 10 11 12 |
x*t^2 x*t^2 + x x*t^2 + x + 1 x*t^2 + 1 (x + 1)*t^2 (x + 1)*t^2 + x (x + 1)*t^2 + x + 1 (x + 1)*t^2 + 1 t^2 t^2 + x t^2 + x + 1 t^2 + 1 |

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

## 4 Comments

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!

If you can give some examples, it will be perfect.

I did give an example in the post. Is there some specific type of example you would like to see?