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]**L. M. Adleman, C. Pomerance & R. Rumely, "On distinguishing prime numbers from composite numbers,"*Ann. of Math.*, v. 117, 1983, pp. 173-206. MR**683806 (84e:10008)****[4]**P. Bateman & R. Horn, "A heuristic asymptotic formula concerning the distribution of prime numbers,"*Math. Comp.*, v. 16, 1962, pp. 363-367. MR**0148632 (26:6139)****[5]**P. Bateman & R. Horn,*Primes Represented by Irreducible Polynomials in One Variable*, Proc. Sympos. Pure Math., vol. 8, 1965, pp. 119-135. MR**0176966 (31:1234)****[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]**J. Brillhart, "Note on irreducibility testing,"*Math. Comp.*, v. 35, 1980, pp. 1379-1381. MR**583515 (83g:12002)****[8]**J Brillhart, M. Filaseta & A. Odlyzko, "On an irreducibility theorem of A. Cohn,"*Canad. J. Math*, v. 33, 1981, pp. 1055-1059. MR**638365 (83c:12003)****[9]**W. S. Brown & R. L. Graham, "An irreducibility criterion for polynomials over the integers,"*Amer. Math. Monthly*, v. 76, 1969, pp. 795-797. MR**0249407 (40:2652)****[10]**D. G. Cantor, "Irreducible polynomials with integral coefficients have succinct certificates,"*J. Algorithms*, v. 2, 1981, pp. 385-392. MR**640521 (83a:12003)****[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]**E. Dehn,*Algebraic Equations*, Dover reprint, 1960. MR**0115991 (22:6788)****[13]**J. D. Dixon, "Asymptotically fast factorization of integers,"*Math. Comp.*, v. 36, 1981, pp. 255-260. MR**595059 (82a:10010)****[14]**H. Halbertstam & H. E. Richert,*Sieve Methods*, Academic Press, New York, 1974. MR**0424730 (54:12689)****[15]**B. A. Hausmann, "A new simplification of Kronecker's method of factorization of polynomials,"*Amer. Math. Monthly*, v. 44, 1937, pp. 574-576. MR**1524088****[16]**D. E. Knuth,*The Art of Computer Programming*, Vol. 2, 2nd ed., Addison-Wesley, Reading, Mass., 1981, [Section 4.6.2]. MR**0378456 (51:14624)****[17]**J. C. Lagarias & A. M. Odlyzko, "Effective versions of the Chebotarev density theorem,"*Algebraic Number Fields*(A. Fröhlich, ed.), (Proc. 1975 Durham Symposium), Academic Press, New York, 1977, pp. 409-464. MR**0447191 (56:5506)****[18]**A. K. Lenstra, H. W. Lenstra, Jr. & L. Lovasz, "Factoring polynomials with rational coefficients,"*Math. Ann.*, v. 261, 1982, pp. 515-534. MR**682664 (84a:12002)****[19]**G. L. Miller, "Riemann's hypothesis and tests for primality,"*J. Comput. System Sci.*, v. 13, 1976, pp. 300-317. MR**0480295 (58:470a)****[20]**R. Moenck, "On the efficiency of algorithms for polynomial factorization,"*Math. Comp.*, v. 31, 1977, pp. 235-250. MR**0422193 (54:10185)****[21]**M. A. Morrison & J. Brillhart, "A method of factoring and the factorization of ,"*Math. Comp.*v. 29, 1975, pp. 183-206. MR**0371800 (51:8017)****[22]**D. Musser, "On the efficiency of a polynomial irreducibility test,"*J. Assoc. Comput. Mach.*, v. 25, 1978, pp. 271-282. MR**488309 (80m:68040)****[23]**W. Narkiewicz,*On the Elementary and Analytic Theory of Algebraic Numbers*, Polish Scientific Publishers, Warsaw, 1974. MR**0347767 (50:268)****[24]**C. Pomerance, "Analysis and comparison of some integer factoring algorithms," pp. 89-139 in*Computational Methods in Number Theory*, Part 1 (H. W. Lenstra, Jr. and r. Tijdeman, eds.), MC Tract # 154, Mathematical Center, Amsterdam, 1982. MR**700260 (84i:10005)****[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 & W. Sierpinski, "Sur certaines hypotheses concernant les nombres premiers,"*Acta Arith.*, v. 4, 1958, pp. 185-208; erratum, v. 5, 1959, p. 259. MR**0106202 (21:4936)****[27]**A. Schinzel, "Remarks on the paper "Sur certaines hypotheses concernant les nombres premiers,""*Acta Arith.*, v. 7, 1961/1962, pp. 1-8. MR**0130203 (24:A70)****[28]**D. Shanks, "On maximal gaps between consecutive primes,"*Math. Comp.*, v. 18, 1964, pp. 646-651. MR**0167472 (29:4745)****[29]**P. J. Weinberger, "Finding the number of factors of a polynomial." (To appear.) MR**744488 (86h:11110)****[30]**H. Zassenhaus, "On Hensel factorization, Part I,"*J. Number Theory*, v. 1, 1969, pp. 291-311. MR**0242793 (39:4120)****[31]**R. Zippel,*Probabilistic Algorithms for Sparse Polynomials*, Ph.D. Thesis, Dept. of Electrical Eng. and Computer Science, MIT, Sept. 1979. MR**575692 (81g:68061)**

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