Title: Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
Abstract: 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.More precisely, we prove that the circuit-size complexity of solving the problem, if a given function \(f:{\mathbb Z}_k^n \to{\mathbb Z}_k\), where k is a fixed composite number, specified by its values, is represented by a polynomial in the ring ℤ k [x 1, …, x n ] and, if so, finding its polynomial, is linear.
Publication Year: 2012
Publication Date: 2012-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 4
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot