[New-bugs-announce] [issue36027] Consider adding modular multiplicative inverse to the math module

[Raymond Hettinger]

New submission from Raymond Hettinger <raymond.hettinger at gmail.com>:

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

----------
components: Library (Lib)
messages: 335862
nosy: mark.dickinson, pablogsal, rhettinger, skrah, tim.peters
priority: low
severity: normal
status: open
title: Consider adding modular multiplicative inverse to the math module
type: enhancement
versions: Python 3.8

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue36027>
_______________________________________