Hard to Detect Factors of Univariate Integer Polynomials

Alberto Dennunzio (), Enrico Formenti () and Luciano Margara ()
Additional contact information
Alberto Dennunzio: Department of Informatics, Systems and Communication, University of Milano-Bicocca, 20100 Milan, Italy
Enrico Formenti: CNRS, I3S, Université Côte d’Azur, France
Luciano Margara: Department of Computer Science and Engineering, Via dell’Universitá 50, 47521 Cesena, Italy

Mathematics, 2023, vol. 11, issue 16, 1-9

Abstract: We investigate the computational complexity of deciding whether a given univariate integer polynomial p ( x ) has a factor q ( x ) satisfying specific additional constraints. When the only constraint imposed on q ( x ) is to have a degree smaller than the degree of p ( x ) and greater than zero, the problem is equivalent to testing the irreducibility of p ( x ) and then it is solvable in polynomial time. We prove that deciding whether a given monic univariate integer polynomial has factors satisfying additional properties is NP-complete in the strong sense. In particular, given any constant value k ∈ Z , we prove that it is NP-complete in the strong sense to detect the existence of a factor that returns a prescribed value when evaluated at x = k (Theorem 1) or to detect the existence of a pair of factors—whose product is equal to the original polynomial—that return the same value when evaluated at x = k (Theorem 2). The list of all the properties we have investigated in this paper is reported at the end of Section Introduction.

Keywords: computational complexity; polynomials; factorization; NP-completeness; semirings (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/16/3602/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/16/3602/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:16:p:3602-:d:1221053

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().