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]**Elwyn R. Berlekamp,*Algebraic coding theory*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR**0238597****[9]**E. R. Berlekamp,*Factoring polynomials over large finite fields*, Math. Comp.**24**(1970), 713–735. MR**0276200**, https://doi.org/10.1090/S0025-5718-1970-0276200-X**[10]**J. D. LIPSON,*Chinese Remainder and Interpolation Algorithms*, Proc. 2nd SIGSAM Sympos., ACM, New York, 1971.**[11]**George E. Collins,*Computing multiplicative inverses in 𝐺𝐹(𝑝)*, Math. Comp.**23**(1969), 197–200. MR**0242345**, https://doi.org/10.1090/S0025-5718-1969-0242345-5**[12]**G. E. COLLINS,*Computing Time Analyses of Some Arithmetic and Algebraic Algorithms*, Proc. 1968 IBM Summer Inst. on Symbolic and Algebraic Computation.**[13]**Donald E. Knuth,*The art of computer programming. Vol. 2: Seminumerical algorithms*, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969. MR**0286318****[14]**J. V. USPENSKY,*The Theory of Equations*, Chap. 11, McGraw-Hill, New York, 1948.**[15]**George E. Collins,*The calculation of multivariate polynomial resultants*, J. Assoc. Comput. Mach.**18**(1971), 515–532. MR**0298921**, https://doi.org/10.1145/321662.321666**[16]**A. Adrian Albert,*Fundamental concepts of higher algebra*, The University of Chicago Press, Chicago, Ill., 1958. MR**0098735****[17]**R. T. MOENCK,*Studies in Fast Algebraic Algorithms*, Ph.D. Thesis, Univ. of Toronto, 1973.**[18]**Volker Strassen,*Gaussian elimination is not optimal*, Numer. Math.**13**(1969), 354–356. MR**0248973**, https://doi.org/10.1007/BF02165411**[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]**Volker Strassen,*Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten*, Numer. Math.**20**(1972/73), 238–251 (German, with English summary). MR**0324947**, https://doi.org/10.1007/BF01436566**[21]**Serge Lang,*Algebra*, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. MR**0197234****[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