---

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 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("gf128_mul(1,1) =", hex(gf128_mul(1, 1)), "(должно 0x1)")
print("gf128_mul(1,2) =", hex(gf128_mul(1, 2)), "(должно 0x2)")
print("gf128_mul(2,2) =", hex(gf128_mul(2, 2)), "(должно 0x4)")
print("gf128_mul(0x80...,2) =", hex(gf128_mul(0x80000000000000000000000000000000, 2)), "(должно", hex(R), ")")

# Инверсия
x = 0x123456789abcdef0123456789abcdef0
inv_x = gf128_inv(x)
prod = gf128_mul(x, inv_x)
print()
print("x     =", hex(x))
print("inv_x =", hex(inv_x))
print("x*inv =", hex(prod), "(должно 0x1)")
print("OK" if prod == 1 else "FAIL")

# Ещё тесты
for t in [1, 2, 3, 0x80, 0x123456789abcdef0123456789abcdef0, 0xffffffffffffffffffffffffffffffff]:
    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'}")