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


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

  • [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 $ {F_7}$," 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)

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

DOI: https://doi.org/10.1090/S0025-5718-1983-0717715-6
Article copyright: © Copyright 1983 American Mathematical Society

American Mathematical Society