Computing primitive elements of extension fields
type: Item
instance of: scholarly article
title: Computing primitive elements of extension fields
zbMATH Open document ID: 0697.68054
DOI: 10.1016/S0747-7171(89)80061-6
author: Kazuhiro Yokoyama
author: Masayuki Noro
author: Taku Takeshima
published in: Journal of Symbolic Computation
publication date: 1989-01-01T00:00:00Z
review text: So-called ``trial methods'' for finding primitive elements and the corresponding minimal polynomials of finitely generated algebraic extensions of \({\mathbb{Q}}\) have been presented by \textit{B. M. Trager} [Symbolic and algebraic computation, Proc. ACM Symp. 1976, Yorktown Heights/N.Y., 219-226 (1976; Zbl 0498.12005)] and \textit{R. Loos} [Computer Algebra, Symbolic and algebraic computation, Comput. Suppl. 4, 173-187 (1982; Zbl 0576.12001)]. These methods are called trial methods because they choose a candidate and then test whether it is actually a primitive element. The basic theory used is that of polynomial resultants, and hence these algorithms apply only when the definition of the extension field is of ``separable-type''. The authors present a new trial method for finding primitive elements that applies to extension fields of ``mixed-type''. This method uses Gröbner bases to test for primitiveness and compute the minimal polynomials. It is shown that the number of trials needed (in any of these trial methods) is bounded by (t-1)N, where t is the number of algebraic elements adjoined to \({\mathbb{Q}}\) and N is the dimension of the resulting algebraic extension over \({\mathbb{Q}}.\) The authors then go on to discuss a (new) non-trial method which deterministically finds primitive elements in the ``separable-type'' case. This algorithm is faster, than any of the trial methods for finding the primitive element and its minimal polynomial. However, if one wants to express the adjoined elements in terms of the obtained primitive element, then a GCD computation is required and the total time complexity is not much different than previous algorithms. This non-trial method can be adapted to find a primitive element and its minimal polynomial for any splitting field of \({\mathbb{Q}}\). In this setting the time saved in comparison to trial methods seems to be greater, even if the representation stage is included.
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 12F05
zbMATH DE Number: 4143449
zbMATH Keywords: splitting field
zbMATH Keywords: algebraic extensions
zbMATH Keywords: primitive element
reviewed by: Gary L. Ebert
MaRDI profile type: Publication
cites work: The Calculation of Multivariate Polynomial Resultants
cites work: Q5551256
cites work: Parallel Algorithms for Algebraic Problems
cites work: Factoring Polynomials over Algebraic Number Fields
cites work: Q3326837
cites work: Q3697106
cites work: Q3963114
cites work: Q3963106
cites work: Factoring Polynomials Over Algebraic Number Fields
full work available at URL: s0747-7171(89)80061-6
OpenAlex ID: W1980515071
description: scientific article; zbMATH DE number 4143449