Checking the Polynomiality of Single-Variable Functions of \({k}\)-Valued Logic Composite Modulo \({k}\)

Polynomiality criteria are proposed for single-variable functions of \(k\) -valued logic with respect to composite modulus \(k\) equal to a power of a prime number. Based on these criteria, algorithms for checking the polynomiality of single-variable functions of \(p^{m}\) -valued logic are obtained for each prime \(p\) , \(m\geqslant 1\) . All calculations in these algorithms are made in residue ring modulo \(p^{m}\) . These algorithms find the canonical polynomial of the input function if the answer is positive. The complexity of the resulting algorithms is estimated (relative to the number of operations for the field of \(p\) elements with possible constants).