Here, I think the range can be reduced by noticing that,
`(p - r)**2 = p**2 - 2*p*r + r*2 = r**2 (mod p)`, so searching in `range(p // 2 + 1)`
would be enough.