#!/usr/bin/env python3
"""176-element magma (F_11 × GF(16)) satisfying eq677, non-right-cancellative, and eq255."""

# Parameters: F_11 × GF(16) with base op x ◇ y = 10x + 2y (mod 11)
# Fiber uses GF(16) = F_2[x]/(x^4 + x + 1) with roots of unity
P = 11
SIZE = P * 16  # 176

# Precompute quadratic residues mod P
QR = {a for a in range(1, P) if pow(a, (P - 1) // 2, P) == 1}

# Roots of unity in GF(16): zeta (5th root) = 8, omega (3rd root) = 6
ZETA, OMEGA = 8, 6

# Base operation coefficients
ALPHA_G, BETA_G = 10, 2  # x ◇ y = 10x + 2y (mod 11)

def gf16_mul(a, b):
    """Multiply in GF(16) using irreducible polynomial x^4 + x + 1."""
    result = 0
    for i in range(4):
        if (b >> i) & 1:
            result ^= (a << i)
    for i in range(7, 3, -1):
        if (result >> i) & 1:
            result ^= (0b10011 << (i - 4))
    return result & 0xF

def op(i, j):
    """Magma operation on F_11 × GF(16)."""
    x, s = i // 16, i % 16
    y, t = j // 16, j % 16

    # Base operation in F_11
    xy = (ALPHA_G * x + BETA_G * y) % P

    # Fiber operation in GF(16) depends on y - x
    diff = (y - x) % P
    if diff == 0:
        coeff1, coeff2 = 1 ^ ZETA, ZETA  # 9, 8
    elif diff in QR:
        coeff1, coeff2 = 0, 1  # identity: t
    else:
        coeff1, coeff2 = 1 ^ OMEGA, OMEGA  # 7, 6

    st = gf16_mul(coeff1, s) ^ gf16_mul(coeff2, t)
    return 16 * xy + st

def check_677():
    """eq677: x = y o (x o ((y o x) o y))"""
    for x in range(SIZE):
        for y in range(SIZE):
            if op(y, op(x, op(op(y, x), y))) != x:
                return False
    return True

def check_non_right_cancellative():
    """True if NOT right-cancellative (i.e., exists collision)."""
    for z in range(SIZE):
        if len({op(x, z) for x in range(SIZE)}) < SIZE:
            return True
    return False

def check_255():
    """eq255: x = ((x o x) o x) o x"""
    for x in range(SIZE):
        if op(op(op(x, x), x), x) != x:
            return False
    return True

def write_table(filename):
    """Write the Cayley table as a space-delimited matrix to a file."""
    with open(filename, 'w') as f:
        for i in range(SIZE):
            f.write(' '.join(str(op(i, j)) for j in range(SIZE)) + '\n')

if __name__ == '__main__':
    print(f"Magma size: {SIZE} (F_{P} x GF(16))")
    print(f"Base op: {ALPHA_G}x + {BETA_G}y (mod {P})")
    print(f"Roots of unity: zeta={ZETA}, omega={OMEGA}")
    print(f"Satisfies eq677: {check_677()}")
    print(f"Non-right-cancellative: {check_non_right_cancellative()}")
    print(f"Satisfies eq255: {check_255()}")
    write_table('magma_176.txt')
    print("Table written to magma_176.txt")