Solving norm equations in global function fields

We present two new algorithms for solving norm equations over global function fields with at least one infinite place of degree one. The first of these is a substantial improvement of a method due to Gaál and Pohst, while the second approach uses index calculus techniques and is significantly faster asymptotically and in practice. Both algorithms incorporate compact representations of field elements which results in a significant gain in performance compared to the Gaál–Pohst approach. We provide Magma implementations, analyze the complexity of all three algorithms under varying asymptotics on the field parameters, and provide empirical data on their performance.