Быстрый алгоритм построения для $k$-значных функций полиномов по модулю $k$ при составных $k$

Рассматриваются полиномиальные задания $k$-значных функций полиномами по модулю $k$ при составных $k$. Вводится новый канонический вид полиномиальных $k$-значных функций при составных $k$. Предложен алгоритм, который по вектору значений $k$-значной функции, где $k$ – составное число, определяет, задается ли она полиномом по модулю $k$, и в случае положительного ответа находит вектор коэффициентов ее канонического полинома со сложностью $O(N)$ битовых операций, где $N=k^n$ есть длина вектора значений функции.
Работа выполнена при поддержке Федеральной целевой программы “Научные и научно-педагогические кадры инновационной России” на 2009–2013 годы, ГК П-784.