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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Niven, I., Warren, L.J.: A Generalization of Fermat’s Theorem. Proceedings of the American Mathematical Society 8(2), 306–313 (1957)
Carlitz, L.: Functions and Polynomials (mod pn). Acta Arithmetica 9, 66–78 (1964)
Aizenberg, N.N., Semyon, I.V., Tsitkin, F.I.: Cardinality of the Class of Functions of k-valued Logic in n Variables which Represented by Polynomials Modulo k. In: The Book: High Stability Elements and Their Applications. Sov. Radio, pp. 79–83 (1971) (in Russian); also transl.: Polynomial Representations of Logical Functions. Automatic Control and Computer Sciences 5, 5–11 (1971)
Anzenberg, N.N., Semyon, I.V.: Some Criterium for Representation of k-valued Logic Functions by Polynomials Modulo k. In: The Book: High Stability Elements and Their Applications. Sov. Radio, pp. 84–88 (1971) (in Russian)
Singmaster, D.: On Polynomial Functions \((\bmod\ m)\). Journal of Number Theory 6, 345–352 (1974)
Rosenberg, I.G.: Polynomial Functions over Finite Rings. Glasnik Matematiki 10(1), 25–33 (1975)
Remizov, A.B.: On a Superstructure of the Closed Class of Polynomials Modulo k. Discrete Mathematics 1(1), 3–15 (1989) (in Russian); in English: Discrete Mathematics and Applications 1(1), 9–22 (1991)
Meschaninov, D.G.: A Method of Constructing Polynomials for Functions of k-valued Logic. Discrete Mathematics 7(3), 48–60 (1995) (in Russian); in English: Discrete Mathematics and Applications 5(4), 333–346 (1995)
Selezneva, S.N.: Fast Algorithm of Construction Polynomials Modulo k for k-valued Functions if k is a Composite Number. Discrete Mathematics 23(3), 3–22 (2011) (in Russian)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Selezneva, S.N. (2012). Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time. In: Hirsch, E.A., Karhumäki, J., Lepistö, A., Prilutskii, M. (eds) Computer Science – Theory and Applications. CSR 2012. Lecture Notes in Computer Science, vol 7353. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30642-6_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-30642-6_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30641-9
Online ISBN: 978-3-642-30642-6
eBook Packages: Computer ScienceComputer Science (R0)