difference inverse(), % in python

Question

I don't know the difference inverse() and % in python. For example inverse(a, q), a%q, the result is same, isn't it? (Inverse() is a function belonging to Crypto.Util.number.)

I'd appreciate it if you could tell me the difference.

Answer 1

No, it's clearly not the same.

123%45
# 33

inverse(123, 45)
# 41

You can check the source of inverse (python 2 code):

def inverse(u, v):
    """inverse(u:long, v:long):long
    Return the inverse of u mod v.
    """
    u3, v3 = long(u), long(v)  # python 3: u3, v3 = u, v
    u1, v1 = 1L, 0L            #           u1, v1 = 1, 0
    while v3 > 0:
        q=divmod(u3, v3)[0]
        u1, v1 = v1, u1 - v1*q
        u3, v3 = v3, u3 - v3*q
    while u1<0:
        u1 = u1 + v
    return u1

If you check the equivalent function in the source of the more recent replacement library pycrytodome there is a clear explanation that this is computing the polynomial greatest common divisor:

    def inverse(self):
        """Return the inverse of this element in GF(2^128)."""

        # We use the Extended GCD algorithm
        # http://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor

        if self._value == 0:
            raise ValueError("Inversion of zero")

        r0, r1 = self._value, self.irr_poly
        s0, s1 = 1, 0
        while r1 > 0:
            q = _div_gf2(r0, r1)[0]
            r0, r1 = r1, r0 ^ _mult_gf2(q, r1)
            s0, s1 = s1, s0 ^ _mult_gf2(q, s1)
        return _Element(s0)