For prime p, the Legendre symbol (2/p) equals 1 iff:
p ≡ 1 (mod 4)
p ≡ 1 or 7 (mod 8)
p ≡ 1 (mod 8)
p ≡ 3 (mod 8)