×

An efficient algorithm for zero-testing of a lacunary polynomial at the roots of unity. (English) Zbl 1188.68160

Diekert, Volker (ed.) et al., Computer science – theory and applications. Second international symposium on computer science in Russia, CSR 2007, Ekaterinburg, Russia, September 3–7, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74509-9/pbk). Lecture Notes in Computer Science 4649, 397-406 (2007).
Summary: We present a polynomial time algorithm for the following problem: to check whether a lacunary polynomial \(f(x)\) vanishes at a given primitive \(n\)th root of unity \(\zeta _{n }\). A priori \(f(\zeta _{n })\) may be nonzero and doubly exponentially small in the input size. Only exponential algorithms were known for this problem. The existence of an efficient procedure in the case of factored \(n\) was conjectured by D. A. Plaisted [“New NP-hard and NP-complete polynomial and integer divisibility problems”, Theor. Comput. Sci. 31, 125–138 (1984; Zbl 0572.68027)]. As a consequence we show that the problem of the divisibility testing of a lacunary polynomial by some cyclotomic polynomial belongs to the complexity class \(\mathcal{NP}\).
For the entire collection see [Zbl 1135.68001].

MSC:

68Q25 Analysis of algorithms and problem complexity
11Y16 Number-theoretic algorithms; complexity
12Y05 Computational aspects of field theory and polynomials (MSC2010)

Citations:

Zbl 0572.68027
PDFBibTeX XMLCite
Full Text: DOI