Permutation Polynomial - Higher Degree Polynomials

Higher Degree Polynomials

Consider polynomial for the ring Z/pkZ. In the same way as for quadratic polynomials one can see:

Lemma: if and i>0, then polynomial g(x) defines a permutation for the elements of the ring Z/pkZ for k>1.

However contrary to the case of the quadratic polynomials the lemma is not if and only if. This can be seen from the following statement.

Lemma: consider finite field Z/pZ for some prime number p. The cubic polynomial defines a permutation if and only if for all it is true that, i.e. the Legendre symbol 
\left(\frac{-b/a}{p}\right)=-1.
.

Evaluation of the Legendre symbol can be achieved with the help of quadratic reciprocity law.

So one can see that the analysis of higher degree polynomials to define a permutation is a quite subtle question.

Read more about this topic:  Permutation Polynomial

Famous quotes containing the words higher and/or degree:

    We are conscious of an animal in us, which awakens in proportion as our higher nature slumbers. It is reptile and sensual, and perhaps cannot be wholly expelled; like the worms which, even in life and health, occupy our bodies. Possibly we may withdraw from it, but never change its nature. I fear that it may enjoy a certain health of its own; that we may be well, yet not pure.
    Henry David Thoreau (1817–1862)

    A new degree of intellectual power seems cheap at any price.
    Ralph Waldo Emerson (1803–1882)