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/(x_1 ..., x_n) over a residue ring modulo k given by its value vector with length N= k~n and, if so, to construct its polynomial representation is linear.