---

R = 0xE1000000000000000000000000000000
MASK128 = (1 << 128) - 1

# ПРАВИЛЬНЫЙ gf128_mul (как в сервере)
def gf128_mul(x, y):
    z = 0
    v = x & MASK128
    for i in range(128):
        if (y >> (127 - i)) & 1:   # СТАРШИЙ бит y
            z ^= v
        msb = (v >> 127) & 1
        v = (v << 1) & MASK128
        if msb:
            v ^= R
    return z & MASK128

# --- Тест 1: базовые ---
print("=== gf128_mul ===")
print(f"1*1 = {gf128_mul(1,1):x}")
print(f"1*2 = {gf128_mul(1,2):x}")
print(f"2*2 = {gf128_mul(2,2):x}")
print(f"0x80*2 = {gf128_mul(0x80000000000000000000000000000000, 2):x}")

# --- Тест 2: инверсия через степень ---
def gf128_inv(x):
    result = 1
    base = x
    exp = (1 << 128) - 2
    while exp:
        if exp & 1:
            result = gf128_mul(result, base)
        base = gf128_mul(base, base)
        exp >>= 1
    return result

print()
print("=== gf128_inv ===")
for t in [1, 2, 3, 0x80, 0x123456789abcdef0123456789abcdef0]:
    inv_t = gf128_inv(t)
    p = gf128_mul(t, inv_t)
    print(f"inv({t:032x}) * {t:032x} = {p:032x} {'OK' if p == 1 else 'FAIL'}")

# --- Тест 3: матрица H^5 обратима? ---
def is_invertible(H_k):
    cols = [gf128_mul(H_k, 1 << i) for i in range(128)]
    rows = []
    for j in range(128):
        row = 0
        for i in range(128):
            if (cols[i] >> j) & 1:
                row |= (1 << i)
        rows.append(row)
    pivot_row = 0
    for col in range(128):
        pivot = -1
        for r in range(pivot_row, 128):
            if (rows[r] >> col) & 1:
                pivot = r
                break
        if pivot == -1:
            continue
        rows[pivot_row], rows[pivot] = rows[pivot], rows[pivot_row]
        for r in range(128):
            if r != pivot_row and ((rows[r] >> col) & 1):
                rows[r] ^= rows[pivot_row]
        pivot_row += 1
    return pivot_row

H_k = 0x6483f1ed6ad11f379d4e92ad1f96a1e9
print()
print("=== Матрица H^5 ===")
rank = is_invertible(H_k)
print(f"Ранг = {rank} (должно 128)")