Algorithm for calculating the roots of polynomials with coefficients in the ring of polynomials over an arbitrary integral domain. (English. Russian original) Zbl 1173.13318

Maevskii, A. É.

Math. Notes 85, No. 1, 68-81 (2009); translation from Mat. Zametki 85, No. 1, 73-88 (2009).

Summary: A deterministic algorithm for calculating the roots of polynomials in one variable with coefficients in the ring of polynomials in several variables over an arbitrary integral domain is constructed. An estimate for the arithmetic complexity of the algorithm in the worst case is obtained.

MSC:

13P05	Polynomials, factorization in commutative rings
14G50	Applications to coding theory and cryptography of arithmetic geometry

Keywords:

root of a polynomial; deterministic algorithm; integral domain; polynomial ring; arithmetic complexity; algebraic-geometric code; principal prime ideal

References:

[1]	R. M. Roth and G. Ruckenstein, ”Efficient decoding of Reed-Solomon codes beyond half the minimum distance,” IEEE Trans. Inform. Theory 46(1), 246–257 (2000). · Zbl 1001.94046 · doi:10.1109/18.817522
[2]	H. Cohen, A Course in Computational Algebraic Number Theory, in Grad. Texts in Math. (Springer-Verlag, Berlin, 1996), Vol. 138.
[3]	V. Guruswami, List Decoding of Error-Correcting Codes, in Lecture Notes in Comput. Sci., Winning thesis of the 2002 ACM Doctoral Dissertation Competition (Springer-Verlag, Berlin, 2004), Vol. 3282 · Zbl 1075.94001
[4]	A. É. Maevskii, ”An algorithm of list decoding for a class of algebraic-geometric codes on projective curves,” in Integral and Differential Equations (Don State Technical University, Rostov-on-Don, 2007), pp. 1–1 [in Russian].
[5]	E. Kaltofen, ”Factorization of polynomials,” in Computer Algebra. Symbolic and Algebraic Computation 2nd ed., Ed. by B. Buchberger, G. E. Collins, R. Loos, and R. Albrecht (Springer-Verlag, Vienna, 1983), pp. 95–113 (Mir, Moscow, 1986), pp. 127–150.
[6]	T. W. Hungerford, Algebra, in Grad. Texts in Math. (Springer-Verlag, New York-Berlin, 1980), Vol. 73.
[7]	L. Bernardin, ”On square-free factorization of multivariate polynomials over a finite fields,” Theoret. Comput. Sci. 187(1–2), 105–116 (1997). · Zbl 1036.11524 · doi:10.1016/S0304-3975(97)00059-5
[8]	D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (Addison-Wesley Publishing Co., Reading, Mass.-London-DonMills, Ont, 1969; Mir, Moscow, 1977). · Zbl 0191.18001
[9]	G. E. Collins, M. Mignotte and F. Winkler, ”Arithmetic in basic algebraic domains,” in Computer Algebra. Symbolic and Algebraic Computation 2nd ed., Ed. by B. Buchberger, G. E. Collins, R. Loos, and R. Albrecht (Springer-Verlag, Vienna, 1983), pp. 189–220 (Mir, Moscow, 1986), pp. 237–276. · Zbl 0533.68039
[10]	M. Shaw and J. F. Traub, ”On the number of multiplications for the evaluation of a polynomial and some of its derivatives,” J. Assoc. Comput. Mach. 21(1), 161–167 (1974). · Zbl 0271.68040 · doi:10.1145/321796.321810
[11]	E. Kaltofen and V. Shoup, ”Subquadratic-time factoring of polynomials over finite fields,” Math. Comp. 67(223), 1179–1197 (1998). · Zbl 0902.11053 · doi:10.1090/S0025-5718-98-00944-2