# Random Permutation polynomial

I need to know, please:

(1) Is there anyway to pick uniformly at random permutation polynomial in a field of prime order?

(2) Are there many permutation polynomials in a field?

(3) In a finite field of q elements how many bijective polynomials exist whose degree are smaller than d ?

***Indeed has the permutation polynomial used in this way in cryptography to generate uniformly random value? If yes, where?

## 1 Answer

Are there many permutation polynomials in a field?

For a field $F$ of order $q$, every function from $F$ to $F$ is expressable (uniquely) as a polynomial of order $q-1$. $q!$ of these will represent permutation polynomials.

Is there anyway to pick uniformly at random permutation polynomial in a field of prime order?

Given a function from $f$ with $f(x_i) = y_i$, it's not difficult to write the polynomial that generates it. It's just a sum of terms like $(x y_0/x_0)(x-x_1)(x-x_2)(x-x_3)... + (x - x_0)(xy_1/x_1)(x-x_2)(x-x_3)...$. If you are generating the permutation on the fly, you can compose simpler permutation polynomials. I don't know if there are more efficient methods.

• Could you please give me a reference proving that q! is the number of permutation polynomial in a field. – user153465 Nov 7 '14 at 18:03
• @user153465: There are $q!$ permutations on a set of $q$ elements; for each permutation, there is an unique order $q-1$ (or shorter) polynomial where the output of the polynimial is the input permutated by that permutation; QED – poncho Nov 7 '14 at 18:57
• Right, the $q!$ part is just counting the permutations. Proving it fully does require the fact that all functions are expressible as polynomials. This follows from the construction I gave, though there are better proofs (that escape me right now). Note that the limit on the order of the polynomial comes from $x^q = x$. – bmm6o Nov 7 '14 at 21:22
• I'd like extent the above question to below and have your answers: In a finite field of q elements how many permutation polynomials exist whose degree are smaller than d ? – user153465 Nov 11 '14 at 14:17
• 1) That's different enough that you should probably ask separately 2) I don't know 3) it doesn't really sound like a crypto question anymore, mathoverflow.net might get you better answers. – bmm6o Nov 11 '14 at 16:49