Method inv

src/minisketch/tests/pyminisketch.py:119–137

Compute the inverse of x in GF(2^field_size).

(self, x)

        return self.mul(x, x)

    def inv(self, x):
        """Compute the inverse of x in GF(2^field_size)."""
        assert x != 0
        # Use the extended polynomial Euclidean GCD algorithm on (modulus, x), over GF(2).
        # See https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor.
        t1, t2 = 0, 1
        r1, r2 = self._modulus, x
        r1l, r2l = self.field_size + 1, r2.bit_length()
        while r2:
            q = r1l - r2l
            r1 ^= r2 << q
            t1 ^= t2 << q
            r1l = r1.bit_length()
            if r1 < r2:
                t1, t2 = t2, t1
                r1, r2 = r2, r1
                r1l, r2l = r2l, r1l
        assert r1 == 1
        return t1

class TestGF2Ops(unittest.TestCase):
    """Test class for basic arithmetic properties of GF2Ops."""