Irreducibility testing and factorization of polynomials

Leonard M. Adlcman, Andrew M. Odlyzko

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


It is shown that under certain hypotheses, irreducibility testing and factorization of polynomials with integer coefficients are polynomial time reducible to primality testing and factorization of integers, respectively. Combined with recently discovered fast primality tests, this yields an almost polynomial time irreducibility algorithm. The assertions of irreducibility produced by this algorithm are always certain and yield short proofs of irreducibility.

Original languageEnglish (US)
Pages (from-to)699-709
Number of pages11
JournalMathematics of Computation
Issue number164
StatePublished - Oct 1983


Dive into the research topics of 'Irreducibility testing and factorization of polynomials'. Together they form a unique fingerprint.

Cite this