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 .

It is shown that if the characteristic of the field is of the form , where , then the roots of a polynomial of degree *n* may be found in steps.

As a result, a modification of Berlekamp's method can be performed in steps. If *n* is very large then an alternative method finds the factors of the polynomial in . Some consequences and empirical evidence are discussed.

**[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 ,"*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 ," 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.

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