docs: def legendre_symbol(a, p):
      """ Compute the Legendre symbol a|p using
      Euler's criterion. p is a prime, a is
      relatively prime to p (if p divides
      a, then a|p = 0)
  
      Returns 1 if a has a square root modulo
      p, -1 otherwise.
      """
      ls = pow(a, (p - 1) / 2, p)
      return -1 if ls == p - 1 else ls