差异逆()，Python中的%

Question

我不知道python中inverse()和%的区别。比如

inverse(a, q)

、

a%q

，结果是一样的不是吗？ （Inverse() 是属于 Crypto.Util.number 的函数。）

如果您能告诉我其中的区别，我将不胜感激。

Answer 1

不，这显然不一样。

123%45
# 33

inverse(123, 45)
# 41

您可以查看inverse

的

来源（python 2代码）：

def inverse(u, v):
    """inverse(u:long, v:long):long
    Return the inverse of u mod v.
    """
    u3, v3 = long(u), long(v)
    u1, v1 = 1L, 0L
    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

如果您检查最新替换库的源中的等效函数

pycrytodome

，有一个明确的解释表明该操作正在计算多项式最大公约数：

    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)