What is an algorithm to test whether a number field element has a square root in that number field?

Question

Let $K$ be a number field, such as $\mathbb{Q}(\sqrt{d})$ for $d$ a square-free integer. I am looking for an algorithm that outputs whether some $\alpha \in K$ has a square root in $K$, i.e. when there is $\beta \in K$ such that $\beta^2 = \alpha$. In the case of $\mathbb{Q}(\sqrt{d})$, testing whether $a + b \sqrt{d}$ has a square root is equivalent to finding $x,y \in \mathbb{Q}$ such that $$a + b \sqrt{d} = (x + y \sqrt{d})^2 = (x^2 + d y^2) + 2xy \sqrt{d}.$$ But I am unsure when the system $$a = x^2 + d y^2, b = 2xy$$ is solvable, nor what to do for a general number field.

Such an algorithm is the same as one that outputs whether the polynomial $x^2 - \alpha \in K[x]$ is irreducible. (While I'd be interested in learning about an irreducibility criterion for all polynomials in $K[x]$, for my purposes I only need the quadratic case.)

I've searched around for such irreducibility criteria, like Eisenstein's, but I didn't see one that works for polynomials defined over a number field.

Answer 1

There are algorithms which can factor polynomials in any number field. This immediately solves the problem.

For let $K$ be a number field such that $[K; \mathbb{Q}] = n$. Then consider some arbitrary $z \in K$. Note that $1, z, z^2, ..., z^n$ forms a sequence of $n+1$ elements of $K$; hence, there must be some polynomial that of degree $n$ or less that $z$ is a root of, since there must be a dependence relation $a_0 1 + a_1 z + ... + a_n z^n = 0$ where at least one of the $a_i$ is nonzero. Computing this dependence relation is basic linear algebra over $\mathbb{Q}$. This gives us a nonzero polynomial $P$ of which $z$ is a root.

Then consider that if $z = k^2$ in some field extension of $K$, then $Q(x) = P(x^2)$ is a polynomial of which $k$ is a root.

Now fully factor $Q$ within $K$ using the algorithm. This reveals what roots, if any, $Q$ has. Test each root of $Q$ to see if it's a square root of $z$.

Answer 2

For the quadratic case, there is no need of any complicated algorithm. Assume that $a=x^2+dy^2$ and $b=2xy$.

Then $4ax^2=4x^4+d(2xy)^2=4x^4+db^2$.

Hence $4z^2-4a z+db^2=0$, where $z=x^2$. A necessary condition for $x$ to be rational is that $x^2$ is, and thus that the reduced discriminant $(a^2-db^2)$ has to be a square. Then you need to check whether one of the numbers $\dfrac{a\pm \sqrt{a^2-db^2}}{2}$ is a square. Conversely, if these conditions are satisfied, we can find an rational $x$ (and then a rational $y$) such that $(x,y)$ is a solution of the system of equations.

Hence $a+b\sqrt{d}$ will be a square if and only if $a^2-db^2$ is a square and one of the rationals $\dfrac{a\pm \sqrt{a^2-db^2}}{2}$ is a square.