×

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

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
Full Text: DOI

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
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.