---

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 rev128(y):
    r = 0
    for i in range(128):
        if (y >> i) & 1:
            r |= (1 << (127 - i))
    return r

def gf128_inv(x):
    if x == 0:
        raise ZeroDivisionError
    x_le = rev128(x)
    MOD = (1 << 128) | 0x87
    
    def deg(a):
        return a.bit_length() - 1 if a else -1
    
    def divmod_poly(a, b):
        q = 0
        while a and deg(a) >= deg(b):
            s = deg(a) - deg(b)
            q ^= (1 << s)
            a ^= (b << s)
        return q, a
    
    def mul_poly(a, b):
        r = 0
        while b:
            if b & 1:
                r ^= a
            a <<= 1
            b >>= 1
        return r
    
    def mod_poly(a, m):
        while a and deg(a) >= deg(m):
            s = deg(a) - deg(m)
            a ^= (m << s)
        return a
    
    r0, r1 = MOD, x_le
    s0, s1 = 0, 1
    steps = 0
    while r1:
        steps += 1
        if steps > 1000:
            raise RuntimeError("EGCD loop")
        q, r = divmod_poly(r0, r1)
        r0, r1 = r1, r
        s0, s1 = s1, s0 ^ mod_poly(mul_poly(q, s1), MOD)
    
    return rev128(s0 & MASK128)

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} (ожидается {R:x})")

print("\n=== Тесты gf128_inv (EGCD с разворотом) ===")
for t in [1, 2, 3, 0x80, 0x123456789abcdef0123456789abcdef0, MASK128]:
    try:
        inv_t = gf128_inv(t)
        p = gf128_mul(t, inv_t)
        print(f"inv({t:032x}) = {inv_t:032x}")
        print(f"   {t:032x} * inv = {p:032x} {'OK' if p == 1 else 'FAIL'}")
    except Exception as e:
        print(f"inv({t:032x}) -> ошибка: {e}")

print("\n=== Тест GF(2^4) для сравнения ===")
def gf4_mul(x, y, R=0x3, MASK=0xF):
    z = 0
    v = x & MASK
    for i in range(4):
        if (y >> i) & 1:
            z ^= v
        msb = (v >> 3) & 1
        v = (v << 1) & MASK
        if msb:
            v ^= R
    return z & MASK

def gf4_inv(x):
    result = 1
    base = x
    exp = (1 << 4) - 2
    while exp:
        if exp & 1:
            result = gf4_mul(result, base)
        base = gf4_mul(base, base)
        exp >>= 1
    return result

for t in [1, 2, 3, 4, 5, 6, 7]:
    inv_t = gf4_inv(t)
    p = gf4_mul(t, inv_t)
    print(f"inv({t}) = {inv_t}, {t} * inv = {p} {'OK' if p == 1 else 'FAIL'}")