If a sequence is generated by a $\mathbb{Q}$-polynomial passed mod $p$, can we find an appropriate polynomial over an extension of $\mathbb{F}_{p}$? If we have a polynomial that takes integer values for integer inputs, we can take its outputs at integer inputs and pass them $\text{mod }p$. However, my understanding is that the coefficients of the polynomial can't always be passed $\text{mod }p$.
Example. Let me give an example to make it clear. Consider the polynomial $f(x) = (x^{3} - 10x)/3$. I won't prove this (unless someone requests for a proof), but this polynomial takes on integer values for integer inputs.
Some values of the polynomial are as follows:
$$ f(0) = 0, \quad f(1) = -3, \quad f(2) = -4, \quad f(3) = -1, \quad f(4) = 8, \quad f(5) = 25. $$
In $\text{mod }3$ this sequence reduces to
$$0, 0, 2, 2, 2, 1, 1, 1, 0, 0, 0, 2, 2, 2, 1, 1, \ldots \qquad\qquad $$
where the first element is $f(0)\,(\text{mod }3)$ and each successive element is the polynomial evaluated $\text{mod }3$ at the next integer.
Now the interesting part here is that this sequence cannot be generated by a polynomial $f\in\mathbb{F}_{3}[x]$. The original $f\in\mathbb{Q}[x]$ has $3$'s in denominators of coefficients. Moreover, the $\text{mod }3$ sequence shown above is not periodic of period $3$, which it would have to be if it is generated by any $f\in\mathbb{F}_{3}[x]$. The last sentence actually proves that the sequence can't be generated by any $f\in\mathbb{F}_{3}[x]$.
Question
Even though the sequence can't be described by any polynomial with coefficients in $\mathbb{F}_{3}$, I am wondering if it can be described by a polynomial with coefficients in a finite extension of $\mathbb{F}_{3}$.
Given a polynomial $f\in\mathbb{Q}[x]$ that takes on integer values for integer inputs, we can generate a sequence of the form
$$ f(0)\,\text{mod }p,\; f(1)\,\text{mod }p,\; f(2)\,\text{mod }p,\; f(3)\,\text{mod }p,\; \ldots $$
for a prime $p$. My main question is, can we always write the sequence as the sequential output of a polynomial over an extension of $\mathbb{F}_{p}$? Can we write the sequence as $g(0), g(1), g(2), \ldots$ for some $g\in F[x]$ for some extension $F/\mathbb{F}_{p}$?
 A: No: such sequences are subject to the same "periodicity" barrier.
If $g\in F[x]$ for a field of characteristic $p$, then $g(x)=g(x+p)$, since $g(x+p)-g(x)$ can be expanded and every term will have a factor of $p$, and thus be $0$ in $F[x]$. This means that, if $f(0)\bmod p, f(1)\bmod p,\dots$ is representable as $g(0),g(1),\dots$, then $f(i)\equiv f(i+p)\pmod p$ for every $i$.
On the other hand, there are other ways to generalize "polynomial over $\mathbb F_p$" that don't involve extensions of $\mathbb F_p$. One is as linear combinations of) the functions $\mathbb Z\to \mathbb F_p$ defined by $n\mapsto \binom na\pmod p$ for each $a$, (these are still periodic, but not necessarily with period $p$). It turns out that these functions exactly represent all sequences $\{f(n)\bmod p\}_{n}$ where $f\in\mathbb Q[x]$ sends integers to integers, since every such polynomial $f\in\mathbb Q[x]$ can be written as
$$f(x)=\sum_{i=0}^d a_i\binom xi$$
for some $a_i\in\mathbb Z$, which is not too hard to prove by induction on the degree.
(In fact, I believe one can use these sorts of functions (along with $n\mapsto r^n$ for various $r\in\mathbb F_p$) to represent every sequence $b_1,b_2,\dots$ of elements of $\mathbb F_p$ satisfying a linear recurrence relation, echoing the fact that over $\mathbb C$ a sequence satisfying a linear recurrence relation can be written explicitly as a linear combination of functions $n\mapsto n^kr^n$ for $k\in\mathbb Z_{\geq 0}$ and $r\in\mathbb C$.)
