Mathematics Seminar with Dr. Michael Monagan

Computing isomorphisms between algebraic number fields.

Dr. Michael Monagan, Department of Mathematics, Simon Fraser University.

Let K = Q(a1,a2,...,ak) be an algebraic number field of degree d over Q and let A and B be polynomials in K[x].  To compute gcd(A,B), the modular GCD algorithm of van Hoeij and Monagan computes a sequence of gcds in R[x] where R = K mod p for some primes p. I will present timings comparing Pari, Magma, Maple and my own C code for computing a GCD in R[x] for K = Q(a1,a2,a3,a4) with d = 32.
I will also show how Pari and Maple represent elements of K and R.

Consider the following idea to get a speedup when k > 1. Pick integers c2, ..., cn and set gamma = a1 + c2 a2 + ... + cn until Q(gamma) mod p is isomorphic to K mod p. Let S = Q(gamma) mod p and compute an isomorphism phi:R -> S. Now, using phi, map the gcd(A,B) computation from R[x] into S[x]. We get a speedup because arithmetic in S where k=1 is faster than in R.

But how do we compute an isomorphism phi:R -> S?

And how fast can we compute phi as a function of d?

In the talk I will present three methods:

1. using Groebner bases,
2. using Linear Algebra, and
3. using iterated sub-resultants.

I will present some timing data for a C implementation of (2).

The most promising approach to get a fast method seems to be (3).