---

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

def gf_mul(x, y):
    z = 0
    v = x & MASK
    for i in range(128):
        if (y >> i) & 1:
            z ^= v
        msb = (v >> 127) & 1
        v = (v << 1) & MASK
        if msb:
            v ^= R
    return z & MASK

def invert_matrix_gf2(H_k):
    """Строит обратную матрицу для умножения на H_k над GF(2)."""
    # M[i] — столбец: H_k * (1 << i)
    cols = [gf_mul(H_k, 1 << i) for i in range(128)]
    # Строим расширенную матрицу [M | I] по строкам
    # Строка j — это биты (cols[0][j], cols[1][j], ..., cols[127][j], I[j])
    rows = []
    for j in range(128):
        row = 0
        for i in range(128):
            if (cols[i] >> j) & 1:
                row |= (1 << i)
        # Единичная матрица справа
        row |= (1 << (128 + j))
        rows.append(row)
    # Гаусс-Жордан
    for col in range(128):
        pivot = -1
        for r in range(col, 128):
            if (rows[r] >> col) & 1:
                pivot = r
                break
        if pivot == -1:
            return None
        rows[col], rows[pivot] = rows[pivot], rows[col]
        for r in range(128):
            if r != col and ((rows[r] >> col) & 1):
                rows[r] ^= rows[col]
    # Правая часть — обратная матрица
    inv_cols = [rows[i] >> 128 for i in range(128)]
    def apply(D):
        X = 0
        for i in range(128):
            if (D >> i) & 1:
                X ^= inv_cols[i]
        return X
    return apply

# Тест
H_k = 0x6483f1ed6ad11f379d4e92ad1f96a1e9

print("=== Проверка матрицы ===")
apply_inv = invert_matrix_gf2(H_k)
if apply_inv is None:
    print("Матрица не обратима!")
else:
    # Проверим на случайных X
    for test_X in [0x123456789abcdef0123456789abcdef0, 1, 2, 0x80]:
        D = gf_mul(test_X, H_k)
        X = apply_inv(D)
        print(f"test_X = {test_X:032x}")
        print(f"  X*H^5 = {D:032x}")
        print(f"  apply(D) = {X:032x}")
        print(f"  совпадает: {X == test_X}")
    # Ищем inv(H^5)
    print()
    inv_H_k = apply_inv(1)
    print(f"inv(H^5) = {inv_H_k:032x}")
    print(f"H^5 * inv(H^5) = {gf_mul(H_k, inv_H_k):032x} (должно быть 1)")
    if gf_mul(H_k, inv_H_k) == 1:
        print("*** УСПЕХ! ***")