The circuit complexity of checking polynomiality for functions over residue ring modulo a composite number is linear
Светлана Николаевна Селезнева · Moscow University Computational Mathematics and Cybernetics · 2013
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 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.