Solvability of norm equations over cyclic number fields of prime degree

Let $L={\mathbb {Q}} [\alpha ]$ be an abelian number field of prime degree $q$, and let $a$ be a nonzero rational number. We describe an algorithm which takes as input $a$ and the minimal polynomial of $\alpha$ over ${\mathbb {Q}}$, and determines if $a$ is a norm of an element of $L$. We show that, if we ignore the time needed to obtain a complete factorization of $a$ and a complete factorization of the discriminant of $\alpha$, then the algorithm runs in time polynomial in the size of the input. As an application, we give an algorithm to test if a cyclic algebra $A=( E, \sigma , a )$ over ${\mathbb {Q}}$ is a division algebra.