A Faster Algorithm For Testing Polynomial Representability Of Functions Over Finite Integer Rings

Abstract

Given a function from ${\mathbb{Z}}_n$ to itself one can determine its polynomial representability by using Kempner function. In this paper we present an alternative characterization of polynomial functions over ${\mathbb{Z}}_n$ by constructing a generating set for the ${\mathbb{Z}}_n$-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.