Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Irreducibility testing and factorization of polynomials

Authors: Leonard M. Adleman and Andrew M. Odlyzko
Journal: Math. Comp. 41 (1983), 699-709
MSC: Primary 11Y05; Secondary 11R09, 12-04, 68Q40
MathSciNet review: 717715
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y05, 11R09, 12-04, 68Q40

Retrieve articles in all journals with MSC: 11Y05, 11R09, 12-04, 68Q40

Additional Information

Article copyright: © Copyright 1983 American Mathematical Society