On the efficiency of algorithms for polynomial factoring
Author:
Robert T. Moenck
Journal:
Math. Comp. 31 (1977), 235250
MSC:
Primary 1204; Secondary 68A10, 68A20
MathSciNet review:
0422193
Fulltext 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. 133148.
 [2]
B. F. CAVINESS, On Canonical Forms and Simplification, Ph.D. Thesis, CarnegieMellon 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, McGrawHill Book Co.,
New York, 1968. MR 0238597
(38 #6873)
 [9]
E.
R. Berlekamp, Factoring polynomials over large
finite fields, Math. Comp. 24 (1970), 713–735. MR 0276200
(43 #1948), http://dx.doi.org/10.1090/S0025571819700276200X
 [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
(39 #3676), http://dx.doi.org/10.1090/S00255718196902423455
 [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, AddisonWesley Publishing Co., Reading, Mass.LondonDon
Mills, Ont, 1969. MR 0286318
(44 #3531)
 [14]
J. V. USPENSKY, The Theory of Equations, Chap. 11, McGrawHill, New York, 1948.
 [15]
George
E. Collins, The calculation of multivariate polynomial
resultants, J. Assoc. Comput. Mach. 18 (1971),
515–532. MR 0298921
(45 #7970)
 [16]
A.
Adrian Albert, Fundamental concepts of higher algebra, The
University of Chicago Press, Chicago, Ill., 1958. MR 0098735
(20 #5190)
 [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
(40 #2223)
 [19]
S. GOLOMB, L. WELCH & A. HALES, "On the factorization of trinomials over ," JPL Memo 20189 (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
(48 #3296)
 [21]
Serge
Lang, Algebra, AddisonWesley Publishing Co., Inc., Reading,
Mass., 1965. MR
0197234 (33 #5416)
 [22]
G. E. COLLINS, The SAC1 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. 1416.
 [25]
G. E. COLLINS, D. R. MUSSER & M. ROTHSTEIN, "SAC1 solution of problem #7," SIGSAM Bull., v. 8, No. 2, ACM, New York, May 1974, pp. 1719.
 [1]
 R. H. RISCH, Symbolic Integration of Elementary Functions, Proc. 1968 IBM Summer Inst. on Symbolic and Algebraic Manipulation, IBM, R. Tobey (Editor), pp. 133148.
 [2]
 B. F. CAVINESS, On Canonical Forms and Simplification, Ph.D. Thesis, CarnegieMellon 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, McGrawHill, 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. 713735. 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. 197200. 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, AddisonWesley, Reading, Mass., 1969. MR 44 #3531. MR 0286318 (44:3531)
 [14]
 J. V. USPENSKY, The Theory of Equations, Chap. 11, McGrawHill, New York, 1948.
 [15]
 G. E. COLLINS, "The calculation of multivariate polynomial resultants," J. Assoc. Comput. Mach., v. 18, 1971, pp. 515532. 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. 354356. MR 40 #2223. MR 0248973 (40:2223)
 [19]
 S. GOLOMB, L. WELCH & A. HALES, "On the factorization of trinomials over ," JPL Memo 20189 (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. 238251. MR 48 #3296. MR 0324947 (48:3296)
 [21]
 S. LANG, Algebra, AddisonWesley, Reading, Mass., 1968. MR 33 #5416. MR 0197234 (33:5416)
 [22]
 G. E. COLLINS, The SAC1 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. 1416.
 [25]
 G. E. COLLINS, D. R. MUSSER & M. ROTHSTEIN, "SAC1 solution of problem #7," SIGSAM Bull., v. 8, No. 2, ACM, New York, May 1974, pp. 1719.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
1204,
68A10,
68A20
Retrieve articles in all journals
with MSC:
1204,
68A10,
68A20
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197704221938
PII:
S 00255718(1977)04221938
Keywords:
Algebraic manipulation,
polynomial factoring,
roots in finite fields,
analysis of algorithms
Article copyright:
© Copyright 1977 American Mathematical Society
