# Random Permutation polynomial

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

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. Commented Nov 7, 2014 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 Commented Nov 7, 2014 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$. Commented Nov 7, 2014 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 ? Commented Nov 11, 2014 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. Commented Nov 11, 2014 at 16:49