Equivalent polynomials over a finite field

Question

Disclamer. I'm not good at math, and the last time I did it in school was 10 years ago, so I'm writing everything in my own words.

Suppose we are working with polynomials in the space of remainders from division by a prime number $p$ (I think they say polynomial over a finite field). Clearly, any polynomial is a mapping from $(0, 1, ..., p - 1)$ to $(a_0, a_1, ..., a_{p-1})$ where all $a_i$ belong to the field. Obviously, the number of such mappings is finite and equal to $p^p$. This means that all polynomials over a finite field can be partitioned into (?) equivalence classes.

My questions are.

1. Is this so? And if so, what is the name of such a partition
2. Starting at what degree will equivalent polynomials begin to occur? (I am not very happy if it is of the order of $p$)
3. Are there algorithms for determining such classes? Are there algorithms for determining that two polynomials are equivalent?
4. What other properties does such an classes have?

These are questions I asked myself after pondering whether working with polynomials over a finite field could be reduced to working with polynomials of lower degrees (something like a basis, the smallest polynomials in a class).

Answer 1

When looking at polynomials over $\Bbb F_p = \Bbb Z/p\Bbb Z$, there is a very nice explicit description of this equivalence between polynomials:

Two polynomials $f(x),g(x) \in \Bbb F_p[x]$ take the same values on all elements of $\Bbb F_p$ if and only if $f(x)-g(x)$ is a multiple of $x^p-x$ (when the polynomial coefficients are considered modulo $p$).

(In particular, note the consequence that the polynomials of degree at most $p-1$ form a complete set of representatives for the equivalence classes—very tidy!)

Outline of the proof:

• For each $a\in\Bbb F_p$, since $f(a)-g(a)=0$, we can show that the polynomial $f(x)-g(x)$ is divisible by $x-a$.
• Since $f(x)-g(x)$ is divisible by $x-a$ for each $a\in\Bbb F_p$, we can show that $f(x)-g(x)$ is divisible by $x(x-1)(x-2)\cdots(x-(p-1))$.
• We can show that $x(x-1)(x-2)\cdots(x-(p-1)) = x^p-x$ (as polynomials with coefficients being considered modulo $p$) using Fermat's little theorem.

In each step I've consciously written “we can show” because there's some nontrivial reasoning—these statements do not necessarily hold when $p$ is not prime.