Computing primitive elements of extension fields.

*(English)*Zbl 0697.68054So-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.

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

PDF
BibTeX
XML
Cite

\textit{K. Yokoyama} et al., J. Symb. Comput. 8, No. 6, 553--580 (1989; Zbl 0697.68054)

Full Text:
DOI

##### References:

[1] | Arnon, D.S.; Sederberg, T.W., Implicit equations for parametric surfaces by Gröbner basis, (), 431 |

[2] | Collins, G.E., The calculation of multivariate polynomial resultants, J. ACM, 19, 515-532, (1971) · Zbl 0226.65042 |

[3] | Feit, W., Characters of finite group, (1967), W. A. Benjamin Publ. New York · Zbl 0166.29002 |

[4] | von zur Gathen, J., Parallel algorithms for algebraic problems, SIAM J. comput., 13, 802-824, (1984) · Zbl 0553.68032 |

[5] | Gianni, P.; Trager, B.; Zacharias, G., Gröbner bases and primary decomposition of polynomial ideals, (1987), preprint |

[6] | Landau, S., Factoring polynomials over algebraic number fields, SIAM J. comput., 14, 184-195, (1985) · Zbl 0565.12002 |

[7] | Lang, S., () |

[8] | Lenstra, A.K., Factoring polynomials over algebraic number fields computer algebra, (), 245-254 |

[9] | Loos, R., Generalized polynomial remainder sequence, (), 173-187 |

[10] | Loos, R., Computing in algebraic extensions, (), 173-187 · Zbl 0576.12001 |

[11] | Kobayashi, H. (1987). preprint (in Japanese). |

[12] | Kobayashi, H.; Moritsugu, S.; Hogan, R.W., On solving systems of algebraic equations, (1988), preprint |

[13] | Mignotte, M., Some useful bounds, (), 259-263 · Zbl 0498.12019 |

[14] | Trager, B.M., Algebraic factoring and rational integration, () · Zbl 0498.12005 |

[15] | van der Waerden, B.L., () |

[16] | Weinberger, P.J.; Rothschild, L.P., Factoring polynomials over algebraic number fields, ACM trans. math. softw., 2, 335-350, (1976) · Zbl 0352.12003 |

[17] | 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.