Algorithm for Calculating the Roots of Polynomials with Coefficients in the Ring of Polynomials over an Arbitrary Integral Domain

A. Maevskiy

Southern Federal University, Faculty of Mathematics, Mechanics and Computer Sciences

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

UDC: 512.662

Received: 20.08.2007

DOI: 10.4213/mzm4034

 English version: Mathematical Notes, 2009, 85:1, 68–81

Bibliographic databases:

• 
• 
• 
•