Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Could you please give me a reference proving that q! is the number of permutation polynomial in a field. –  user153465 Nov 7 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 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 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 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 at 16:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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