def legendre_symbol(a, p):
    """
    Computes the Legendre symbol
    :param a: number
    :param p: prime number
    :return: Returns 1 if `a` has a square root modulo p, -1 otherwise.
    """

    ls = pow(a, (p - 1) // 2, p)
    if ls == p - 1:
        return -1
    return ls