The circuit complexity of checking polynomiality for functions over residue ring modulo a composite number is linear

It is proved that for each fixed composite number k, the circuit complexity of the problem which is to check if an arbitrary function f(x ₁, ..., x _n ) over a residue ring modulo k given by its value vector with length N = k ⁿ and, if so, to construct its polynomial representation is linear.