Isomorphisms of algebraic number fields (Q713173)

This article is concerned with the following important problem in algebraic number theory: Decide whether or not two number fields are isomorphic. If yes, then an interesting computational problem is to determine an explicit isomorphism effectively. In this article, the authors provide an effective method to find all isomorphisms between two number fields. Their algorithm works best if there is only one such isomorphism. The authors give a detailed description of their algorithms together with a complexity analysis. They also provide a heuristic argument why their algorithm works best if there is only one isomorphism. In the end, numerical results are included in order to emphasize the efficiency of the new algorithm. Based on the book by \textit{H. Cohen} [A course in computational algebraic number theory. Berlin: Springer-Verlag (1993; Zbl 0786.11071)], the author consider two basic methods. Let \(\mathbb{Q}(\alpha)\) and \(\mathbb{Q}(\beta)\) be two algebraic number fields of degree \(n\), given by the minimal polynomials \(f\) and \(g\) of \(\alpha\) and \(\beta\) respectively. The first method uses polynomial factorization techniques by e.g. factoring \(g\) over \(\mathbb{Q}(\alpha)\) in order to find all roots (if any) of \(g\) over \(\mathbb{Q}(\alpha)\). The second method uses linear algebra methods by first finding the roots of \(f\) and \(g\) in \(\mathbb{Q}_p\) with an appropriate \(p\) and by then applying LLL-type techniques [\textit{A. K. Lenstra}, \textit{H. W. Lenstra} jun. and \textit{L. Lovász}, Math. Ann. 261, 515--534 (1982; Zbl 0488.12001)] in a clever way. The new method expands on the second basic method and even coincides with the second basic method in the Galois case. The contributions of this article are a slight improvement of the running time in some cases over the first two methods and a novel technique for making the computations effective. The main novel techniques are the use of sub-traces, the exploitation of using several suitable primes, and throughout the use of the rational representation basis \((1/f'(\alpha),\alpha/f'(\alpha),\dots,\alpha^{n-1}/f'(\alpha))\) instead of the power basis \((1,\alpha,\alpha^2,\dots,\alpha^{n-1})\).