×

Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time. (English) Zbl 0596.12022

Translation from Zap. Nauchn. Semin. Leningr. Otd. Mat. Inst. Steklova 137, 124–188 (Russian) (1984; Zbl 0561.12010).

MSC:

12Y05 Computational aspects of field theory and polynomials (MSC2010)
11Y05 Factorization
11T06 Polynomials over finite fields
68W30 Symbolic computation and algebraic computation
14A10 Varieties and morphisms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. L. Van Der Waerden, Modern Algebra [Russian translation], Parts 1 and 2, ONTI, Moscow-Leningrad (1937).
[2] D. Yu. Girogor’ev, ?Two reductions of isomorphism of graphs to problems on polynomials,? J. Sov. Math.,20, No. 4 (1982).
[3] O. Zariski and P. Samuel, Commutative Algebra [Russian translation], Vols. 1 and 2, IL, Moscow (1963). · Zbl 0121.27901
[4] D. Yu. Grigor’ev, ?Factorization of polynomials over a finite field and solution of systems of algebraic equations,? J. Sov. Math.,34, No. 4 (1986).
[5] D. Knuth, The Art of Computer Programming, Vol. 2, Addison-Wesley (1969). · Zbl 0191.18001
[6] S. Lang, Algebra [Russian translation], Mir, Moscow (1968).
[7] I. R. Shafarevich, Basic Algebraic Geometry [in Russian], Nauka, Moscow (1972).
[8] 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).
[9] A. L. Chistov and D. Yu. Grigor’ev, ?Subexponential-time solving systems of algebraic equations. I,? LOMI Preprint E-9-83, Leningrad (1983).
[10] A. L. Chistov and D. Yu. Grigor’ev, ?Subexponential-time solving systems of algebraic equations, II,? LOMI Preprint E-10-83, Leningrad (1983).
[11] G. Collins, ?Subresultants and reduced polynomial remainder sequences?, J. ACM,14, No. 1, 128?142 (1967). · Zbl 0152.35403 · doi:10.1145/321371.321381
[12] D. Yu. Grigor’ev, ?Some new bounds on tensor rank,? LOMI Preprint E-2-78, Leningrad (1978).
[13] D. Yu. Grigor’ev, ?Multiplicative complexity of a bilinear form over a commutative ring,? Lect. Notes Comput. Sci.,118, 281?286 (1981). · doi:10.1007/3-540-10856-4_94
[14] J. Heintz, ?Definability and fast quantifier elimination in algebraically closed field,? Preprint Univ. Frankfurt, West Germany, December (1981).
[15] 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.
[16] E. Kaltofen, ?A polynomial time-reduction from bivariate to univariate integral polynomial factorization,? in: Proc. 23rd Ann. Symp. Found. Comp. Sci., N.Y., October, 1982.
[17] D. Lazard, ?Algebre linéaire sur k [X1,...,Xn] et élimination,? Bull. Soc. Math. France,105, 165?190 (1977). · Zbl 0447.13008 · doi:10.24033/bsmf.1848
[18] D. Lazard, ?Résolutions des systèmes d’équations algébriques,? Theor. Comput. Sci.,15, 77?110 (1981). · Zbl 0459.68013 · doi:10.1016/0304-3975(81)90064-5
[19] D. Lazard, ?Commutative algebra and computer algebra,? Lect. Notes Comput. Sci.,144, 40?48 (1983). · Zbl 0552.68047 · doi:10.1007/3-540-11607-9_5
[20] A. K. Lenstra, H. W. Lenstra, and L. Lovasz, ?Factoring polynomials with rational coefficients,? Preprint Math. Centrum Amsterdam IW 195/82 (1982).
[21] M. T. McClellan, ?The exact solution of systems of linear equations with polynomial coefficients,? J. ACM,20, No. 4, 563?588 (1973). · Zbl 0273.65030 · doi:10.1145/321784.321787
[22] A. Seidenberg, ?Constructions in a polynomial ring over the ring of integers,? Am. J. Math.,100, No. 4, 685?704 (1978). · Zbl 0416.13013 · doi:10.2307/2373905
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.