---

def invert_matrix_gf2(H_k):
    """Строит обратную матрицу для умножения на H_k над GF(2)."""
    # Матрица M: 128x128, где M[i][j] = бит j от (H_k * 2^i)
    # Мы хотим M^{-1}
    # Расширенная: [M | I]
    # M — строки, столбцы — биты результата
    
    # M[i][j]: результат умножения H_k на e_i, бит j
    # e_i = 1 << i
    M = []
    for i in range(128):
        col = gf128_mul(H_k, 1 << i)
        M.append(col)  # столбец i
    
    # M как строки: row[j] = биты M[0..127][j] (собранные из столбцов)
    rows = []
    for j in range(128):
        row = 0
        for i in range(128):
            if (M[i] >> j) & 1:
                row |= (1 << i)
        # Добавляем единичную матрицу справа: 128 бит identity
        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]
        # Обнуляем col во всех остальных строках
        for r in range(128):
            if r != col and ((rows[r] >> col) & 1):
                rows[r] ^= rows[col]
    
    # Теперь левая часть — единичная, правая — обратная
    # Обратная матрица: столбец i = (rows[i] >> 128)
    inv_cols = []
    for i in range(128):
        inv_cols.append(rows[i] >> 128)
    
    # Функция применения обратной матрицы: X = inv_M * D
    def apply_inv(D):
        X = 0
        for i in range(128):
            if (D >> i) & 1:
                X ^= inv_cols[i]
        return X
    
    return apply_inv

# Использование:
apply_inv = invert_matrix_gf2(H_k)
if apply_inv:
    inv_H_k = apply_inv(1)  # X * H^5 = 1 -> X = inv(H^5)
    print(f"inv(H^5) = {inv_H_k:032x}")
    print(f"H^5 * inv(H^5) = {gf128_mul(H_k, inv_H_k):032x}")