I want to find a representation of an integer $N$ of the form $N = x^2 + ny^2$. Any single non-trivial representation (i.e. $x \gt 0, y \gt 0, n \ge 1$) suffices.
A naive algorithm that I have implemented checks for $x, n$ in the ranges
$$ \begin{align} 1 & \le x \le \sqrt N \\ 1 & \le n \le \sqrt N \end{align} $$
and checks if $Y = N - x^2$ is divisible by $n$ and if it is then checks if $Y/n = y^2$ is a perfect square. If yes, then we have a representation $N = x^2 + ny^2$. This gives a complexity of $O(N)$.
Is there a better algorithm?
Note: I know if factors of $N$ are known and both have representations of the form $a^2 + nb^2$, we could use the Brahmagupta identity. In this case factors of $N$ are unknown and I would like to avoid factoring.