Perfect squares

I am seeking the most efficient method to determine if:

N+a^2 is a perfect square. Here N and "a" are large integers.

It is more important that a false be determined in the most efficient
maner, while a true may take longer to determine.

thank you for your help.

.