# zbMATH — the first resource for mathematics

Computing primitive elements of extension fields. (English) Zbl 0697.68054
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 B. M. Trager [Symbolic and algebraic computation, Proc. ACM Symp. 1976, Yorktown Heights/N.Y., 219-226 (1976; Zbl 0498.12005)] and 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.
Reviewer: G.L.Ebert

##### MSC:
 68W30 Symbolic computation and algebraic computation 12F05 Algebraic field extensions
##### MathOverflow Questions:
Find a generator of a field extension defined by an f-d algebra
##### Keywords:
splitting field; algebraic extensions; primitive element
Full Text:
##### References:
  Arnon, D.S.; Sederberg, T.W., Implicit equations for parametric surfaces by Gröbner basis, (), 431  Collins, G.E., The calculation of multivariate polynomial resultants, J. ACM, 19, 515-532, (1971) · Zbl 0226.65042  Feit, W., Characters of finite group, (1967), W. A. Benjamin Publ. New York · Zbl 0166.29002  von zur Gathen, J., Parallel algorithms for algebraic problems, SIAM J. comput., 13, 802-824, (1984) · Zbl 0553.68032  Gianni, P.; Trager, B.; Zacharias, G., Gröbner bases and primary decomposition of polynomial ideals, (1987), preprint  Landau, S., Factoring polynomials over algebraic number fields, SIAM J. comput., 14, 184-195, (1985) · Zbl 0565.12002  Lang, S., ()  Lenstra, A.K., Factoring polynomials over algebraic number fields computer algebra, (), 245-254  Loos, R., Generalized polynomial remainder sequence, (), 173-187  Loos, R., Computing in algebraic extensions, (), 173-187 · Zbl 0576.12001  Kobayashi, H. (1987). preprint (in Japanese).  Kobayashi, H.; Moritsugu, S.; Hogan, R.W., On solving systems of algebraic equations, (1988), preprint  Mignotte, M., Some useful bounds, (), 259-263 · Zbl 0498.12019  Trager, B.M., Algebraic factoring and rational integration, () · Zbl 0498.12005  van der Waerden, B.L., ()  Weinberger, P.J.; Rothschild, L.P., Factoring polynomials over algebraic number fields, ACM trans. math. softw., 2, 335-350, (1976) · Zbl 0352.12003  Yokoyama, K.; Noro, M.; Takeshima, T., Computing primitive elements for extension fields, Research report no. 80. IIAS-SIS, (1987)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.