This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author rhettinger mark.dickinson, pablogsal, rhettinger, skrah, tim.peters 2019-02-18.20:10:59 -1.0 Yes <1550520659.43.0.126744170658.issue36027@roundup.psfhosted.org>
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>