If we know any square root of 1 modulo N different from 1 and N-1, then we can find a nontrivial factor of N. So to find such a square root has a certain hardness.
In fact, if in general we ask to decide for given numbers a,b,N whether there exists a square root x of a (modulo N) with 0 < x < b, then this is an NP-complete problem, as shown in a paper by Adleman and Manders in 1978. Even if the prime factorization of N is given as part of the input.
How about if for given numbers b and N we ask whether there exists a square root x of 1 (modulo N) for which 1 < x < b ? Is it also NP-complete?