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

DOI:
https://doi.org/10.1090/S0025-5718-1983-0717715-6

MathSciNet review:
717715

Full-text PDF

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.

**[1]**L. M. Adleman,*On Distinguishing Prime Numbers from Composite Numbers*, Proc. 21st Annual IEEE Found. Comp. Sci. Conference, IEEE, 1980, pp. 387-406.**[2]**L. M. Adleman & A. M. Odlyzko,*Irreducibility Testing and Factorization of Polynomials*, (extended abstract), Proc. 22nd Annual IEEE Found. Comp. Sci. Conference, IEEE, 1981, pp. 409-418.**[3]**Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely,*On distinguishing prime numbers from composite numbers*, Ann. of Math. (2)**117**(1983), no. 1, 173–206. MR**683806**, https://doi.org/10.2307/2006975**[4]**Paul T. Bateman and Roger A. Horn,*A heuristic asymptotic formula concerning the distribution of prime numbers*, Math. Comp.**16**(1962), 363–367. MR**0148632**, https://doi.org/10.1090/S0025-5718-1962-0148632-7**[5]**Paul T. Bateman and Roger A. Horn,*Primes represented by irreducible polynomials in one variable*, Proc. Sympos. Pure Math., Vol. VIII, Amer. Math. Soc., Providence, R.I., 1965, pp. 119–132. MR**0176966****[6]**V. Bouniakowsky, "Sur les diviseurs numériques invariables des fonctions rationelles entières,"*Mem. Acad. Sci. St. Petersberg*, v. 6, 1857,, pp. 305-329.**[7]**John Brillhart,*Note on irreducibility testing*, Math. Comp.**35**(1980), no. 152, 1379–1381. MR**583515**, https://doi.org/10.1090/S0025-5718-1980-0583515-0**[8]**John Brillhart, Michael Filaseta, and Andrew Odlyzko,*On an irreducibility theorem of A. Cohn*, Canad. J. Math.**33**(1981), no. 5, 1055–1059. MR**638365**, https://doi.org/10.4153/CJM-1981-080-0**[9]**W. S. Brown and R. L. Graham,*An irreducibility criterion for polynomials over the integers*, Amer. Math. Monthly**76**(1969), 795–797. MR**0249407**, https://doi.org/10.2307/2317870**[10]**David G. Cantor,*Irreducible polynomials with integral coefficients have succinct certificates*, J. Algorithms**2**(1981), no. 4, 385–392. MR**640521**, https://doi.org/10.1016/0196-6774(81)90036-5**[11]**H. Cramér, "On the order of magnitude of the difference between consecutive prime numbers,"*Acta Arith.*, v. 2, 1937, pp. 23-46.**[12]**Edgar Dehn,*Algebraic equations: An introduction to the theories of Lagrange and Galois*, Dover Publications, Inc., New York, 1960. MR**0115991****[13]**John D. Dixon,*Asymptotically fast factorization of integers*, Math. Comp.**36**(1981), no. 153, 255–260. MR**595059**, https://doi.org/10.1090/S0025-5718-1981-0595059-1**[14]**H. Halberstam and H.-E. Richert,*Sieve methods*, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], London-New York, 1974. London Mathematical Society Monographs, No. 4. MR**0424730****[15]**B. A. Hausmann,*A New Simplification of Kronecker’s Method of Factorization of Polynomials*, Amer. Math. Monthly**44**(1937), no. 9, 574–576. MR**1524088**, https://doi.org/10.2307/2301633**[16]**Donald E. Knuth,*The art of computer programming*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**0378456****[17]**J. C. Lagarias and A. M. Odlyzko,*Effective versions of the Chebotarev density theorem*, Algebraic number fields: 𝐿-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR**0447191****[18]**A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász,*Factoring polynomials with rational coefficients*, Math. Ann.**261**(1982), no. 4, 515–534. MR**682664**, https://doi.org/10.1007/BF01457454**[19]**Gary L. Miller,*Riemann’s hypothesis and tests for primality*, J. Comput. System Sci.**13**(1976), no. 3, 300–317. Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N.M., 1975). MR**0480295**, https://doi.org/10.1016/S0022-0000(76)80043-8**[20]**Robert T. Moenck,*On the efficiency of algorithms for polynomial factoring*, Math. Comp.**31**(1977), no. 137, 235–250. MR**0422193**, https://doi.org/10.1090/S0025-5718-1977-0422193-8**[21]**Michael A. Morrison and John Brillhart,*A method of factoring and the factorization of 𝐹₇*, Math. Comp.**29**(1975), 183–205. Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday. MR**0371800**, https://doi.org/10.1090/S0025-5718-1975-0371800-5**[22]**David R. Musser,*On the efficiency of a polynomial irreducibility test*, J. Assoc. Comput. Mach.**25**(1978), no. 2, 271–282. MR**488309**, https://doi.org/10.1145/322063.322071**[23]**Władysław Narkiewicz,*Elementary and analytic theory of algebraic numbers*, PWN—Polish Scientific Publishers, Warsaw, 1974. Monografie Matematyczne, Tom 57. MR**0347767****[24]**C. Pomerance,*Analysis and comparison of some integer factoring algorithms*, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 89–139. MR**700260****[25]**R. Risch,*Symbolic Integration of Elementary Functions*, Proc. 1968 IBM Summer Inst. on Symbolic and Algebraic Manipulation (R. Tobey, ed.), pp. 133-148.**[26]**A. Schinzel and W. Sierpiński,*Sur certaines hypothèses concernant les nombres premiers*, Acta Arith.**4**(1958), 185–208; erratum 5 (1958), 259 (French). MR**0106202**, https://doi.org/10.4064/aa-4-3-185-208**[27]**A. Schinzel,*Remarks on the paper “Sur certaines hypothèses concernant les nombres premiers”*, Acta Arith.**7**(1961/1962), 1–8. MR**0130203**, https://doi.org/10.4064/aa-7-1-1-8**[28]**Daniel Shanks,*On maximal gaps between successive primes*, Math. Comp.**18**(1964), 646–651. MR**0167472**, https://doi.org/10.1090/S0025-5718-1964-0167472-8**[29]**P. J. Weinberger,*Finding the number of factors of a polynomial*, J. Algorithms**5**(1984), no. 2, 180–186. MR**744488**, https://doi.org/10.1016/0196-6774(84)90025-7**[30]**Hans Zassenhaus,*On Hensel factorization. I*, J. Number Theory**1**(1969), 291–311. MR**0242793**, https://doi.org/10.1016/0022-314X(69)90047-X**[31]**Richard Zippel,*Probabilistic algorithms for sparse polynomials*, Symbolic and algebraic computation (EUROSAM ’79, Internat. Sympos., Marseille, 1979) Lecture Notes in Comput. Sci., vol. 72, Springer, Berlin-New York, 1979, pp. 216–226. MR**575692**

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

DOI:
https://doi.org/10.1090/S0025-5718-1983-0717715-6

Article copyright:
© Copyright 1983
American Mathematical Society