compacted description
@@ -89,12 +89,9 @@ def mod_sqrt(a: int, p: int) -> int:
r = m
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.
+ """ 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
