def legendre(a, m):
    """
    This function returns the Legendre symbol (a/m).
    If m is an odd composite then this is the Jacobi symbol.
    """
    a = a % m
    symbol = 1
    while a != 0:
        while a & 1 == 0:
            a >>= 1
            if m & 7 == 3 or m & 7 == 5:
                symbol = -symbol
        a, m = m, a
        if a & 3 == 3 and m & 3 == 3:
            symbol = -symbol
        a = a % m
    if m == 1:
        return symbol
    return 0