Computing primitive elements of extension fields (Q911775): Difference between revisions

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.