# 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?

-
Is $f$ total or partial not? –  user2468 Apr 1 '12 at 16:28
$f$ is a total function. –  Norman Apr 1 '12 at 16:30

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).