Find $a$ in $a^2 \equiv 1 \pmod b$ given $b$ where $a < b-1$

Question

Given the equivalence $a^2 \equiv 1 \pmod b$ (where $b$ is known) is there an efficient way to determine if an answer other than $a = 1$ exists? Is there an efficient way to find the answer(s), especially the greatest possible value of $a$? The only constraint is $1 < a < b - 1$.