For a given $n$ is there a guaranteed way to construct any possible function from $\mathbb{Z}/n\mathbb{Z}$ to itself in terms of polynomials? Specifically, for $T = \mathbb{Z}/n\mathbb{Z}$ I'd like to use polynomials with $T$ coefficients to describe all functions $T \to T$.
My original hypothesis was that I could express functions $\mathbb{Z}/n\mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ as a polynomial of order $n$ or less with coefficients in $\mathbb{Z}/n\mathbb{Z}$. I determined that this was true for $n=1, 2, 3, 5, 7$ (using brute force) but that it was false for $n=4, 6$. My new hypothesis is that it may only be true for prime $n$ (but I can't use brute force to test $11$ or larger primes).
Is this true for all prime $n$? If so, is there a more general result I can use for composite $n$? If not, are there other approaches I could use? Is this impossible in general?
One idea I had for composite $n$ was to use the prime factorization of $n$ ($p_0^{k_0}p_1^{k_1}...$) to construct polynomials for all the factors and then combine them into a single multivariate polynomial. I was able to do this for $n=4$ ($2^2$) by constructing $axy + bx + cy + d$ for $x, y \in [0, 1]$ and $a, b, c, d \in [0, 3]$. But I wasn't able to adapt this approach to $n=6$.
I'm interested in programmatically generating an enumeration of all possible functions $T \to T$ in terms of a given enumeration of $T$. Since the cardinality of this set is $|T|^{|T|}$ I won't actually generate most of these functions. The important part is that I have a mapping from each $index$ to a distinct function, and that in principle there is an $index$ for every possible function (even if some indices are far too large to work with). I'm doing this in a software library that already contains enumeration strategies for many other data structures such as lists, tuples, sets, maps, and so on.
I have an existing solution that uses tables to map a subset of inputs to non-zero outputs (mapping all other inputs to zero). I can show that my enumeration constructs every possible table (eventually) so that in principle every function can be represented (although for data structures like 32-bit integers most interesting functions such as $f(x) = x + 1$ would have tables far too big to be useful). However most enumerations for small $index$ values are uninteresting (they produce zero for most inputs).
I was hoping to generate polynomials instead of tables, since even relatively simple polynomials would have more interesting behaviors. But I can't do this unless I know a way to construct a set of polynomials that represents each possible function exactly once.