This problem is equivalent to detecting whether there is some prime $p\equiv3\pmod4$ dividing the number which is raised to an odd power. In the worst case, where the number is a large semiprime equivalent to 1 mod 4, this is almost surely as hard as FACTORIZATION.
Practically, check the number mod 4 (once you remove trailing 0s) and see if it's 3, then trial divide by small primes.