For a given integer $n>0$, can we efficiently determine whether an integer $y$ exist such that $n+y^2$ is a perfect square?

Question

I am trying to implement an efficient algorithm which must determine whether for a given integer $n>0$ another integer $y$ exist such that $n+y^2$ is a perfect square.

Based on some properties of $n$, can we make a statement about the existence of such a $y$ efficiently? Or reverse, is it possible for this $n$ to determine that there will be definitely no such $y$?

What I found out so far:

I found in the literature that a diophantine equation of the form:

$$x^2-Dy^2=n$$

is a so-called "Norm-Form Equation". Hence in our case, we have the special case $D=1$. However, as simple as the equation looks, it does not appear to be. For example Richard A. Mollin involves in his Theorem 6.2.2 the divisor function which is not a very efficient operation:

It wold be great if there exist an efficient way to determine wheher for an positive integer $n$ exist another integer $y$ such that $n+y^2$ is a perfect square.

Additional note: Even if the check routine generates some false positives in favor of efficiency, that would be absolutely ok. Being able to rule out that for a given natural $n$, no such $y$ exists would also be extremely helpful.

Answer 1

Summarizing the comments; your question can be rephrased as:

Can we efficiently determine whether a given positive integer $n$ is of the form $n=x^2-y^2$, for some integer $x$ and $y$?

The answer is yes; a positive integer $n$ is of this form if and only if $n\not\equiv2\pmod{4}$. This has been asked here before, e.g. this question.