Geodesic
Algorithm for Calculating the Roots of Polynomials with Coefficients in the Ring of Polynomials over an Arbitrary Integral Domain
Matematičeskie zametki, Tome 85 (2009) no. 1, pp. 73-88 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: root of a polynomial, deterministic algorithm, integral domain, polynomial ring, arithmetic complexity, algebraic-geometric code, principal prime ideal. 
@article{MZM_2009_85_1_a6,
     author = {A. Maevskiy},
     title = {Algorithm for {Calculating} the {Roots} of {Polynomials} with {Coefficients} in the {Ring} of {Polynomials} over an {Arbitrary} {Integral} {Domain}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {73--88},
     year = {2009},
     volume = {85},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2009_85_1_a6/}
}
TY  - JOUR
AU  - A. Maevskiy
TI  - Algorithm for Calculating the Roots of Polynomials with Coefficients in the Ring of Polynomials over an Arbitrary Integral Domain
JO  - Matematičeskie zametki
PY  - 2009
SP  - 73
EP  - 88
VL  - 85
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MZM_2009_85_1_a6/
LA  - ru
ID  - MZM_2009_85_1_a6
ER  - 
%0 Journal Article
%A A. Maevskiy
%T Algorithm for Calculating the Roots of Polynomials with Coefficients in the Ring of Polynomials over an Arbitrary Integral Domain
%J Matematičeskie zametki
%D 2009
%P 73-88
%V 85
%N 1
%U http://geodesic.mathdoc.fr/item/MZM_2009_85_1_a6/
%G ru
%F MZM_2009_85_1_a6
A. Maevskiy. Algorithm for Calculating the Roots of Polynomials with Coefficients in the Ring of Polynomials over an Arbitrary Integral Domain. Matematičeskie zametki, Tome 85 (2009) no. 1, pp. 73-88. http://geodesic.mathdoc.fr/item/MZM_2009_85_1_a6/

[1] R. M. Roth, G. Ruckenstein, “Efficient decoding of Reed–Solomon codes beyond half the minimum distance”, IEEE Trans. Inform. Theory, 46:1 (2000), 246–257 | DOI | MR | Zbl

[2] H. Cohen, A Course in Computational Algebraic Number Theory, Grad. Texts in Math., 138, Springer-Verlag, Berlin, 1996 | MR | Zbl

[3] V. Guruswami, List Decoding of Error-Correcting Codes, Winning thesis of the 2002 ACM Doctoral Dissertation Competition, Lecture Notes in Comput. Sci., 3282, Springer-Verlag, Berlin, 2004 | Zbl

[4] A. E. Maevskii, “Algoritm spisochnogo dekodirovaniya odnogo klassa algebro-geometricheskikh kodov na proektivnykh krivykh”, Integralnye i differentsialnye uravneniya, DGTU, Rostov-na-Donu, 2007, 1–1

[5] E. Kaltofen, “Razlozhenie polinomov na mnozhiteli”, Kompyuternaya algebra: simvolnye i algebraicheskie vychisleniya, Mir, M., 1986, 127–150 | MR

[6] T. W. Hungerford, Algebra, Grad. Texts in Math., 73, Springer-Verlag, New York–Berlin, 1980 | MR | Zbl

[7] L. Bernardin, “On square-free factorization of multivariate polynomials over a finite fields”, Theoret. Comput. Sci., 187:1–2 (1997), 105–116 | DOI | MR | Zbl

[8] D. Knut, Iskusstvo programmirovaniya dlya EVM. T. 2: Poluchislennye algoritmy, Mir, M., 1977 | MR | Zbl

[9] Dzh. E. Kollinz, M. Minott, F. Uinkler, “Arifmetika v osnovnykh algebraicheskikh oblastyakh”, Kompyuternaya algebra: simvolnye i algebraicheskie vychisleniya, Mir, M., 1986, 237–276 | MR

[10] M. Shaw, 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 (1974), 161–167 | DOI | MR | Zbl

[11] E. Kaltofen, V. Shoup, “Subquadratic-time factoring of polynomials over finite fields”, Math. Comp., 67:223 (1998), 1179–1197 | DOI | MR | Zbl