#!/usr/bin/env python3
"""155-element magma satisfying eq677, non-right-cancellative, and eq255."""

# Parameters: Z_31 x Z_5 with c=15, fiber=(a0,b0,a_qr,b_qr,a_nqr,b_nqr)=(2,4,0,1,4,4)
P, Q, C = 31, 5, 15
A0, B0, A_QR, B_QR, A_NQR, B_NQR = 2, 4, 0, 1, 4, 4
SIZE = P * Q

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

def op(i, j):
    """Magma operation: (x,s) o (y,t) = (x + c(y-x), alpha*s + beta*t)"""
    x, s = i // Q, i % Q
    y, t = j // Q, j % Q
    xy = (x + C * (y - x)) % P
    diff = (y - x) % P
    if diff == 0:
        alpha, beta = A0, B0
    elif diff in QR:
        alpha, beta = A_QR, B_QR
    else:
        alpha, beta = A_NQR, B_NQR
    st = (alpha * s + beta * t) % Q
    return Q * 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} (Z_{P} x Z_{Q})")
    print(f"Parameters: c={C}, fiber=({A0},{B0},{A_QR},{B_QR},{A_NQR},{B_NQR})")
    print(f"Satisfies eq677: {check_677()}")
    print(f"Non-right-cancellative: {check_non_right_cancellative()}")
    print(f"Satisfies eq255: {check_255()}")
    write_table('magma_155.txt')
    print("Table written to magma_155.txt")