---

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

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

def solve_linear(H_k, D):
    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)
        if (D >> j) & 1:
            row |= (1 << 128)
        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
    X = 0
    for r in range(pivot_row):
        for col in range(128):
            if (rows[r] >> col) & 1:
                if (rows[r] >> 128) & 1:
                    X |= (1 << col)
                break
    check = 0
    for i in range(128):
        if (X >> i) & 1:
            check ^= cols[i]
    if check != D:
        return None
    return X

# ТЕСТ 1: ассоциативность
a = 0x123456789abcdef0123456789abcdef0
b = 0xfedcba9876543210fedcba9876543210
c = 0x11111111111111111111111111111111
left = gf128_mul(gf128_mul(a, b), c)
right = gf128_mul(a, gf128_mul(b, c))
print(f"assoc: {left == right}")

# ТЕСТ 2: solve_linear(1, D) == D?
D = 0x123456789abcdef0123456789abcdef0
X = solve_linear(1, D)
print(f"solve_linear(1, D): {'OK' if X == D else 'FAIL'}")

# ТЕСТ 3: solve_linear(2, 8)?
X = solve_linear(2, 8)
if X is not None:
    print(f"solve_linear(2, 8) = {X:x}, X*2 = {gf128_mul(X, 2):x}")
else:
    print("solve_linear(2, 8): None")