Author rhettinger
Recipients mark.dickinson, pablogsal, rhettinger, skrah, tim.peters
Date 2019-02-18.20:10:59
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1550520659.43.0.126744170658.issue36027@roundup.psfhosted.org>
In-reply-to
Content
Having gcd() in the math module has been nice.  Here is another number theory basic that I've needed every now and then:


    def multinv(modulus, value):
        '''Multiplicative inverse in a given modulus

            >>> multinv(191, 138)
            18
            >>> 18 * 138 % 191
            1

            >>> multinv(191, 38)
            186
            >>> 186 * 38 % 191
            1

            >>> multinv(120, 23)
            47
            >>> 47 * 23 % 120
            1

        '''
        # https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
        # http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
        x, lastx = 0, 1
        a, b = modulus, value
        while b:
            a, q, b = b, a // b, a % b
            x, lastx = lastx - q * x, x
        result = (1 - lastx * modulus) // value
        if result < 0:
            result += modulus
        assert 0 <= result < modulus and value * result % modulus == 1
        return result
History
Date User Action Args
2019-02-18 20:10:59rhettingersetrecipients: + rhettinger, tim.peters, mark.dickinson, skrah, pablogsal
2019-02-18 20:10:59rhettingersetmessageid: <1550520659.43.0.126744170658.issue36027@roundup.psfhosted.org>
2019-02-18 20:10:59rhettingerlinkissue36027 messages
2019-02-18 20:10:59rhettingercreate