Let K = ℚ(a₁,a₂,…,a_m) be a number field with m > 0 field extensions. Let f₁ and f₂ be polynomials in K[x₁,x₂,…,x_n] and let g = GCD(f₁,f₂) be the greatest common divisor of f₁ and f₂. In this talk I will outline an algorithm for computing g, present my Magma implementation of this algorithm and compare my code with the built-in Gcd operation in Magma.

The reason for my interest in this problem is because I believe it is the one of the most important and difficult computational problems in a general purpose computer algebra system to get right; my timings will give some indication as to why this is the case but I will seek to give general reasons to justify this.

I would like also to present for dicussion three problems that I encountered when writing the Magma code and possible solutions that Allan, Claus and I have “mulled over” for more general discussion.