def legendre_symbol(a, p) ->int:
    """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).
    It returns 1 if a has a square root modulo p, -1 otherwise.

    https://codereview.stackexchange.com/questions/43210/tonelli-shanks-algorithm-implementation-of-prime-modular-square-root/43267
    """
    ls = pow(a, p >> 1, p)
    return -1 if ls == p - 1 else ls
