2
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Could you please give me a reference proving that q! is the number of permutation polynomial in a field. $\endgroup$
    – user153465
    Commented Nov 7, 2014 at 18:03
  • $\begingroup$ @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 $\endgroup$
    – poncho
    Commented Nov 7, 2014 at 18:57
  • $\begingroup$ 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$. $\endgroup$
    – bmm6o
    Commented Nov 7, 2014 at 21:22
  • $\begingroup$ 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 ? $\endgroup$
    – user153465
    Commented Nov 11, 2014 at 14:17
  • $\begingroup$ 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. $\endgroup$
    – bmm6o
    Commented Nov 11, 2014 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.