Irreducibility testing and factorization of polynomials

Adleman, Leonard M.; Odlyzko, Andrew M.

doi:10.1090/S0025-5718-1983-0717715-6

Irreducibility testing and factorization of polynomials
HTML articles powered by AMS MathViewer

by Leonard M. Adleman and Andrew M. Odlyzko PDF

Math. Comp. 41 (1983), 699-709 Request permission

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

On Distinguishing Prime Numbers from Composite Numbers

Irreducibility Testing and Factorization of Polynomials

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, DOI 10.2307/2006975
Paul T. Bateman and Roger A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp. 16 (1962), 363–367. MR 148632, DOI 10.1090/S0025-5718-1962-0148632-7
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

Mem. Acad. Sci. St. Petersberg

John Brillhart, Note on irreducibility testing, Math. Comp. 35 (1980), no. 152, 1379–1381. MR 583515, DOI 10.1090/S0025-5718-1980-0583515-0
John Brillhart, Michael Filaseta, and Andrew Odlyzko, On an irreducibility theorem of A. Cohn, Canadian J. Math. 33 (1981), no. 5, 1055–1059. MR 638365, DOI 10.4153/CJM-1981-080-0
W. S. Brown and R. L. Graham, An irreducibility criterion for polynomials over the integers, Amer. Math. Monthly 76 (1969), 795–797. MR 249407, DOI 10.2307/2317870
David G. Cantor, Irreducible polynomials with integral coefficients have succinct certificates, J. Algorithms 2 (1981), no. 4, 385–392. MR 640521, DOI 10.1016/0196-6774(81)90036-5

Acta Arith.

Edgar Dehn, Algebraic equations: An introduction to the theories of Lagrange and Galois, Dover Publications, Inc., New York, 1960. MR 0115991
John D. Dixon, Asymptotically fast factorization of integers, Math. Comp. 36 (1981), no. 153, 255–260. MR 595059, DOI 10.1090/S0025-5718-1981-0595059-1
H. Halberstam and H.-E. Richert, Sieve methods, London Mathematical Society Monographs, No. 4, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1974. MR 0424730
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, DOI 10.2307/2301633
Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR 0447191
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, DOI 10.1007/BF01457454
Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI 10.1016/S0022-0000(76)80043-8
Robert T. Moenck, On the efficiency of algorithms for polynomial factoring, Math. Comp. 31 (1977), no. 137, 235–250. MR 422193, DOI 10.1090/S0025-5718-1977-0422193-8
Michael A. Morrison and John Brillhart, A method of factoring and the factorization of $F_{7}$, Math. Comp. 29 (1975), 183–205. MR 371800, DOI 10.1090/S0025-5718-1975-0371800-5
David R. Musser, On the efficiency of a polynomial irreducibility test, J. Assoc. Comput. Mach. 25 (1978), no. 2, 271–282. MR 488309, DOI 10.1145/322063.322071
Władysław Narkiewicz, Elementary and analytic theory of algebraic numbers, Monografie Matematyczne, Tom 57, PWN—Polish Scientific Publishers, Warsaw, 1974. MR 0347767
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

Symbolic Integration of Elementary Functions

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 106202, DOI 10.4064/aa-4-3-185-208
A. Schinzel, Remarks on the paper “Sur certaines hypothèses concernant les nombres premiers”, Acta Arith. 7 (1961/62), 1–8. MR 130203, DOI 10.4064/aa-7-1-1-8
Daniel Shanks, On maximal gaps between successive primes, Math. Comp. 18 (1964), 646–651. MR 167472, DOI 10.1090/S0025-5718-1964-0167472-8
P. J. Weinberger, Finding the number of factors of a polynomial, J. Algorithms 5 (1984), no. 2, 180–186. MR 744488, DOI 10.1016/0196-6774(84)90025-7
Hans Zassenhaus, On Hensel factorization. I, J. Number Theory 1 (1969), 291–311. MR 242793, DOI 10.1016/0022-314X(69)90047-X
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