New submission from Raymond Hettinger <[email protected]>:
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 <[email protected]>
<https://bugs.python.org/issue36027>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
