First of all it's always useful to post the source of the problem you need help with. It increases the chance of you getting any help, and also to make sure you didn't get it from an on going contest or whatever.

I searched a bit but I couldn't find a full solution that works in better than O(N), but here is what I have so far:

• Let $$$X = sqrt(N) - 1$$$, now we have $$$X^2$$$ as a candidate. All we need to do know is verify if there exists a better possible modulo than it, which is the range from $$$[X^2; N-1]$$$ which is $$$O(sqrt(N))$$$

• The problem now is; having $$$N,M$$$ does there exist an integer $$$X$$$ such that $$$X^2 = M (modulo N)$$$ or not

• This means finding out if $$$M$$$ is a quadratic residue modulo $$$N$$$.

• This can be found using the quadratic reciprocity which finds this for a prime $$$N$$$, but you can get around that using CRT on the prime factors of $$$N$$$.

• The last problem is that I read that this is only possible for $$$M$$$ coprime to $$$N$$$, although I didn't find it explicitly mentioned in the wikipedia article, it was in a stackexchange answer.

Maybe someone can shed a light on this?

Maybe I'm over-complicating it but this is my approach.

Let’s try to find largest $$$x$$$ such that there exists $$$a$$$ which satisfies $$$a^2 \equiv x \mod n$$$ (Also known as a quadratic residue mod n).

Let's iterate from $$$n-1$$$ to $$$0$$$. Check if $$$i$$$ is a quadratic residue by an extension of Euclid’s criterion. You can read about it on wikipedia https://en.wikipedia.org/wiki/Quadratic_residue. If it is then break.

Then after finding x, you can use the algorithm described here to find $$$a$$$ http://www.numbertheory.org/php/squareroot.html

The for loop will go through $$$O(\sqrt{n})$$$ values at most as that will be the gap between squares just below and above $$$n$$$, So that's a worst case upper bound.