Polynomiality characterizations are proposed for k-valued logic functions of one variable for a composite modulo k which is a power of a prime number. Based on these characterizations, for each prime number p, polynomiality checking algorithms are obtained for pm-valued logic functions of one variable, m > 1. In these algorithms, the calculations are performed in the residue ring modulo pm. In the case of the positive answer, the algorithms find the canonical polynomial of a input function. The complexity of the obtained algorithms are evaluated (with respect to number of operations from the field of p elements with possible constants).
