Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

On the efficiency of algorithms for polynomial factoring


Author: Robert T. Moenck
Journal: Math. Comp. 31 (1977), 235-250
MSC: Primary 12-04; Secondary 68A10, 68A20
DOI: https://doi.org/10.1090/S0025-5718-1977-0422193-8
MathSciNet review: 0422193
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Algorithms for factoring polynomials over finite fields are discussed. A construction is shown which reduces the final step of Berlekamp's algorithm to the problem of finding the roots of a polynomial in a finite field $ {Z_p}$.

It is shown that if the characteristic of the field is of the form $ p = L \cdot {2^l} + 1$, where $ l \simeq L$, then the roots of a polynomial of degree n may be found in $ O({n^2}\log p + n{\log ^2}p)$ steps.

As a result, a modification of Berlekamp's method can be performed in $ O({n^3} + {n^2}\log p + n{\log ^2}p)$ steps. If n is very large then an alternative method finds the factors of the polynomial in $ O({n^2}{\log ^2}n + {n^2}\log n\log p)$. Some consequences and empirical evidence are discussed.


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

  • [1] R. H. RISCH, Symbolic Integration of Elementary Functions, Proc. 1968 IBM Summer Inst. on Symbolic and Algebraic Manipulation, IBM, R. Tobey (Editor), pp. 133-148.
  • [2] B. F. CAVINESS, On Canonical Forms and Simplification, Ph.D. Thesis, Carnegie-Mellon Univ., 1967.
  • [3] D. Y. Y. YUN, "On algorithms for solving systems of polynomial equations," SIGSAM Bull., No. 27, ACM, New York, September 1973.
  • [4] B. L. VAN DER WAERDEN, Modern Algebra, Vol. 1, 2nd rev. ed., Springer, Berlin, 1937; English transl., Ungar, New York, 1949. MR 10, 587.
  • [5] D. JORDAN, R. KAIN & L. CLAPP, "Symbolic factoring of polynomials in several variables," Comm. ACM, v. 9, 1966.
  • [6] D. R. MUSSER, Algorithms for Polynomial Factorization, Ph.D. Thesis, Univ. of Wisconsin, 1971.
  • [7] P. S. WANG & L. P. ROTHSCHILD, "Factoring polynomials over the integers," SIGSAM Bull., No. 28, ACM, New York, December 1973.
  • [8] E. R. BERLEKAMP, Algebraic Coding Theory, Chap. 6, McGraw-Hill, New York, 1968. MR 38 #6873. MR 0238597 (38:6873)
  • [9] E. R. BERLEKAMP, "Factoring polynomials over large finite fields," Math. Comp., v. 24, 1970, pp. 713-735. MR 43 #1948. MR 0276200 (43:1948)
  • [10] J. D. LIPSON, Chinese Remainder and Interpolation Algorithms, Proc. 2nd SIGSAM Sympos., ACM, New York, 1971.
  • [11] G. E. COLLINS, "Computing multiplicative inverses in $ {\text{GF}}(p)$," Math. Comp., v. 23, 1969, pp. 197-200. MR 39 #3676. MR 0242345 (39:3676)
  • [12] G. E. COLLINS, Computing Time Analyses of Some Arithmetic and Algebraic Algorithms, Proc. 1968 IBM Summer Inst. on Symbolic and Algebraic Computation.
  • [13] D. E. KNUTH, The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, Addison-Wesley, Reading, Mass., 1969. MR 44 #3531. MR 0286318 (44:3531)
  • [14] J. V. USPENSKY, The Theory of Equations, Chap. 11, McGraw-Hill, New York, 1948.
  • [15] G. E. COLLINS, "The calculation of multivariate polynomial resultants," J. Assoc. Comput. Mach., v. 18, 1971, pp. 515-532. MR 45 #7970. MR 0298921 (45:7970)
  • [16] A. A. ALBERT, Fundamental Concepts of Higher Algebra, Univ. of Chicago Press, Chicago, 1958. MR 20 #5190. MR 0098735 (20:5190)
  • [17] R. T. MOENCK, Studies in Fast Algebraic Algorithms, Ph.D. Thesis, Univ. of Toronto, 1973.
  • [18] V. STRASSEN, "Gaussian elimination is not optimal," Numer. Math., v. 13, 1969, pp. 354-356. MR 40 #2223. MR 0248973 (40:2223)
  • [19] S. GOLOMB, L. WELCH & A. HALES, "On the factorization of trinomials over $ {\text{GF}}(2)$," JPL Memo 20-189 (July 1959)(as referred to in [13]).
  • [20] V. STRASSEN, "Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten," Numer. Math., v. 17, 1972/73, pp. 238-251. MR 48 #3296. MR 0324947 (48:3296)
  • [21] S. LANG, Algebra, Addison-Wesley, Reading, Mass., 1968. MR 33 #5416. MR 0197234 (33:5416)
  • [22] G. E. COLLINS, The SAC-1 System: An Introduction and Survey, Proc. 2nd SIGSAM Sympos., ACM, New York, 1971.
  • [23] S. C. JOHNSON & R. L. GRAHAM, "Problem #7," SIGSAM Bull., v. 8, No. 1, ACM, New York, February 1974, p. 4.
  • [24] R. FATEMAN, J. MOSES & P. WANG, "Solution to problem #7 using MACSYMA," SIGSAM Bull., v. 8, No. 2, ACM, New York, May 1974, pp. 14-16.
  • [25] G. E. COLLINS, D. R. MUSSER & M. ROTHSTEIN, "SAC-1 solution of problem #7," SIGSAM Bull., v. 8, No. 2, ACM, New York, May 1974, pp. 17-19.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 12-04, 68A10, 68A20

Retrieve articles in all journals with MSC: 12-04, 68A10, 68A20


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1977-0422193-8
Keywords: Algebraic manipulation, polynomial factoring, roots in finite fields, analysis of algorithms
Article copyright: © Copyright 1977 American Mathematical Society

American Mathematical Society