Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
Светлана Николаевна Селезнева · Lecture notes in computer science · 2012
We show how to check in linear time if a function \(f:{\mathbb Z}_k^n \to{\mathbb Z}_k\), where k = p m , p is a prime number, and m ≥ 2, specified by its values, can be represented by a polinomial in the ring ℤ k [x 1, …, x n ]. If so, our algorithm also constructs (in linear time) its canonical polynomial representation. We also show how to extend our techniques (with linear time) to the cases of an arbitrary composite number k.