A faster algorithm for testing polynomial representability of functions over finite integer rings

Given a function from ZnZn to itself one can determine its polynomial representability by using Kempner function. In this paper we present an alternative characterization of polynomial functions over ZnZn by constructing a generating set for the ZnZn-module of polynomial functions. This characterization results in an algorithm that is faster on average in deciding polynomial representability. We also extend the characterization to functions in several variables.