We investigate the computational complexity of deciding whether a given univariate integer polynomial 𝑝(𝑥) has a factor 𝑞(𝑥) satisfying specific additional constraints. When the only constraint imposed on 𝑞(𝑥) is to have a degree smaller than the degree of 𝑝(𝑥) and greater than zero, the problem is equivalent to testing the irreducibility of 𝑝(𝑥) 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 𝑘∈ℤ, 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 𝑥=𝑘 (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 𝑥=𝑘 (Theorem 2). The list of all the properties we have investigated in this paper is reported at the end of Section Introduction.

Hard to Detect Factors of Univariate Integer Polynomials

Margara, Luciano
2023

Abstract

We investigate the computational complexity of deciding whether a given univariate integer polynomial 𝑝(𝑥) has a factor 𝑞(𝑥) satisfying specific additional constraints. When the only constraint imposed on 𝑞(𝑥) is to have a degree smaller than the degree of 𝑝(𝑥) and greater than zero, the problem is equivalent to testing the irreducibility of 𝑝(𝑥) 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 𝑘∈ℤ, 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 𝑥=𝑘 (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 𝑥=𝑘 (Theorem 2). The list of all the properties we have investigated in this paper is reported at the end of Section Introduction.
2023
Dennunzio, Alberto; Formenti, Enrico; Margara, Luciano
File in questo prodotto:
File Dimensione Formato  
mathematics-11-03602-v2.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione 261.38 kB
Formato Adobe PDF
261.38 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/939477
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
social impact