Abstract
An algorithm is constructed for factoring polynomials in several variables over a finite field
, which works in polynomial time in the size of the polynomial and q. Previously this result was known in the case of one variable. An algorithm is given for the solution (over the algebraic closure F of the field F) of systems of algebraic equations
, where
with working time of order
where L is the size of a representative of the original system, ℓ is the degree of transcendence of the field F over the prime subfield, q=char(F). Previously the estimate
was known for ℓ=0.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Literature cited
B. L. Van Der Waerden, Modern Algebra [Russian translation], Parts 1 and 2, ONTI, Moscow-Leningrad (1937).
D. Yu. Grigor'ev, “Two reductions of graph isomorphisms to polynomial problems,” J. Sov. Math.,20, No. 4 (1982).
O. Zariski and P. Samuel, Commutative Algebra [Russian translation], Vols. 1 and 2, IL, Moscow (1963).
A. L. Chistov, “Polynomial factoring algorithm for polynomials and finding components of varieties in subexponential time,” J. Sov. Math.,34, No. 4 (1986).
D. Knuth, The Art of Computer Programming, Vol. 2, Addison-Wesley (1969).
S. A. Lang, Algebra, Addison-Wesley (1965).
I. R. Shafarevich, Fundamentals of Algebraic Geometry [in Russian], Nauka, Moscow (1972).
A. L. Chistov and D. Yu. Grigor'ev, “Polynomial-time factoring of the multivariable polynomials over a global field,” LOMI Preprint E-5-82, Leningrad (1982).
A. L. Chistov and D. Yu. Grigor'ev, “Subexponential-time solving systems of algebraic equations. I.” LOMI Preprint E-9-83, Leningrad (1983).
A. L. Chistov and D. Yu. Grigor'ev, “Subexponential-time solving systems of algebraic Equations. II,” LOMI Preprint E-10-83, Leningrad (1983).
G. Collins, “Subresultants and reduced polynomial remainder sequences,” J. Assoc. Comput. Mach.,14, No. 1, 128–142 (1967).
D. Yu. Grigor'ev, “Some new bounds on tensor rank,” LOMI Prepring E-2-78, Leningrad (1978).
D. Yu. Grigor'ev, “Multiplicative complexity of a bilinear form over a commutative ring,” Lect. Notes Comput. Sci.,118, 281–286 (1981).
J. Heintz, “Definability and fast quantifier elimination in algebraically closed field,” Preprint Univ. Frankfurt, West Germany, December (1981).
E. Kaltofen, “A polynomial reduction from multivariate to bivariate integral polynomial factorization,” in: Proc. 14th ACM Symp. Th. Comput., May, 1982, N.Y., pp. 261–266.
E. Kaltofen, “A polynomial-time reduction from bivariate to univariate integral polynomial factorization,” in: Proc. 23rd Ann. Symp. Found. Comp. Sci., N.Y., Oct., 1982.
D. Lazard, “Algebre linéaire sur k[X1 ..., Xn] et elimination,” Bull. Soc. Math. France,105, 165–190 (1977).
D. Lazard, “Résolutions des systèmes d'équations algébriques,” Theor. Comput. Sci.,15, 77–110 (1981).
D. Lazard, “Commutative algebra and computer algebra,” Lect. Notes Commit. Sci.,144, 40–48 (1983).
A. K. Lenstra, H. W. Lenstra, and L. Lovasz, “Factoring polynomials with rational coefficients,” Preprint Math. Centrum Amsterdam IW 195/82 (1982).
M. T. McClellan, “The exact solution of systems of linear equations with polynomial coefficients,” JACM,20, No. 4, 563–588 (1973).
A. Seidenberg, “Constructions in a polynomial ring over the ring of integers,” Am. J. Math.,100, No. 4, 685–704 (1978).
Additional information
Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 137, pp. 20–79, 1984.
Rights and permissions
About this article
Cite this article
Grigor'ev, D.Y. Factorization of polynomials over a finite field and the solution of systems of algebraic equations. J Math Sci 34, 1762–1803 (1986). https://doi.org/10.1007/BF01095638
Issue Date:
DOI: https://doi.org/10.1007/BF01095638