Algorithms for deciding whether a function over a finite ring is polynomial or not? Let $R$ be a finite ring, and $f$ be a function from $R$ to $R.$
Suppose I want to know whether $f$ can be represented as a polynomial or not? Are there any good algorithms for finding this out?
 A: There is a criterion of Spira that a function on a finite commutative ring $R$ is representable by a polynomial if and only if all the iterated divided differences that can be formed by subsets of the arguments and the respective values are in $R$. The reference is R. Spira, Polynomial interpolation over commutative rings, Amer. Math. Monthly, 75 (1968), 638–640, MR0229625 (37 #5199). 
Also possibly of interest is Sophie Frisch, Polynomial functions on commutative rings, in D. E. Dobbs, M. Fontana, S.-E. Kabbaj (eds.), Advances in Commutative Ring Theory (Fes III Conf. 1997) Lecture Notes in Pure and Appl. Mathematics 205, Dekker 1999, pp 323–336, MR1767431 (2001d:13006), available at http://blah.math.tu-graz.ac.at/~frisch/wwwpdf/pfr.pdf
A: Another reference is
Jian Jun Jiang, Guo Hua Peng, Qi Sun, Qi Fan Zhang, ``On polynomial functions over finite commutative rings,'' Acta Math. Sinica, v. 22, issue 4, Springer, 2006, pp. 1047-1050.

Theorem 3 Let $R$ be a finite commutative local ring with a maximum ideal $\mathfrak{m}$ and let $N$ be
  the minimal positive integer such that $\mathfrak{m}^N = 0$. Assume $f$ is a function from $R$ to $R$. Then $f$
  is a polynomial function if and only if there exist $N$ functions $f_i$ ($i = 0, 1, \ldots , N - 1$) from $R$
  to $R$ such that
  $f(x + s) = f_0(x) + f_1(x)s + \cdots + f_{N-1}(x)s^{N-1}$
  holds for any $x\in R$ and any $s\in \mathfrak{m}$.

For example, if $R=\mathbb{Z}_{p^2}$, then $\mathfrak{m}=p\mathbb{Z}_{p^2}$ and N=2.  The theorem says that a function $f:R\rightarrow R$ is a polynomial function if and only if $f(x+kp)-f(x)=f_1(x)kp$ for some function $f_1$.  From the binomial theorem, if $f$ is a polynomial function then $f_1=f'\mod{p^2}$.
It suffices to check just for $k=1$, if you also check that $f_1(x+p)=f_1(x)\mod{p}$.  The latter condition is necessary for all polynomial functions.
