def jacobi(n, m):
    """Compute the Jacobi symbol.

    The special case of this when m is prime is the Legendre symbol,
    which is 0 if n is congruent to 0 mod m; 1 if n is congruent to a
    non-zero square number mod m; -1 if n is not congruent to any
    square mod m.

    """
    assert m & 1
    acc = 1
    while True:
        n %= m
        if n == 0:
            return 0
        while not n & 1:
            n >>= 1
            if m & 7 not in {1, 7}:
                acc *= -1
        if n == 1:
            return acc
        if n & 3 == 3 and m & 3 == 3:
            acc *= -1
        n, m = m, n
