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. If it was easy, then it would give away the second-lowest bit in both prime factors of such numbers; if we had enough information of this type we could recover the factors via Coppersmith's algorithm.
Practically, check the number mod 4 (once you remove trailing 0s) and see if it's 3, then trial divide by small primes.