The problem dealt with is as follows: given a finite ring ~R and a function f: R → R, decide if f can be represented by a polynomial ~p (that is, f(x) = p(x) for all x ϵ R), and if so, find such ~p. For a field ~R, it is well known that the answer is always positive and that p can be found by methods already shown by Newton, Lagrange, and others.

Recently an algorithmic solution has been found for the case R = Z_n by Guha and Dukkipati [1]. In the paper under review, this result is generalized to arbitrary finite commutative rings with unity. The problem is first reduced to the case of a local ring ~R, and it is assumed that R itself and certain data like the unique maximal ideal are known in advance and ring operations can be performed in constant time. Under these provisions, the algorithm developed has quasilinear complexity in terms of |R|, which corresponds to the size of the input.