"""GF(2^m) multiplication tensor for the frozen moduli of the tcount / andcount boards."""

# Frozen moduli: exponents with coefficient 1.
MODULI = {
    2: (2, 1, 0), 3: (3, 1, 0), 4: (4, 1, 0), 5: (5, 2, 0), 6: (6, 1, 0), 7: (7, 1, 0),
    8: (8, 4, 3, 1, 0), 9: (9, 4, 0), 10: (10, 3, 0), 16: (16, 5, 3, 1, 0), 32: (32, 7, 3, 2, 0),
}


def poly(m):
    return sum(1 << e for e in MODULI[m])


def pmod(a, p):
    dp = p.bit_length() - 1
    while a and a.bit_length() - 1 >= dp:
        a ^= p << (a.bit_length() - 1 - dp)
    return a


def pmul(a, b):
    r = 0
    while b:
        if b & 1:
            r ^= a
        a <<= 1
        b >>= 1
    return r


def is_irreducible(p):
    """Rabin's test over GF(2): x^(2^d) = x mod p and gcd(x^(2^(d/q)) - x, p) = 1 for every prime q | d."""
    d = p.bit_length() - 1

    def xpow2k(k):  # x^(2^k) mod p
        r = 2
        for _ in range(k):
            r = pmod(pmul(r, r), p)
        return r

    def pgcd(a, b):
        while b:
            a, b = b, pmod(a, b)
        return a

    if xpow2k(d) != 2:
        return False
    q, n, primes = 2, d, []
    while q * q <= n:
        if n % q == 0:
            primes.append(q)
            while n % q == 0:
                n //= q
        q += 1
    if n > 1:
        primes.append(n)
    for q in primes:
        if pgcd(xpow2k(d // q) ^ 2, p) != 1:
            return False
    return True


def tensor(m):
    """Set of (i, j, l) with coefficient 1: coefficient of x^l in x^(i+j) mod P_m."""
    p = poly(m)
    assert is_irreducible(p), m
    xe = [pmod(1 << e, p) for e in range(2 * m - 1)]
    return {(i, j, l) for i in range(m) for j in range(m) for l in range(m) if xe[i + j] >> l & 1}