Message335862
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 |
|
Date |
User |
Action |
Args |
2019-02-18 20:10:59 | rhettinger | set | recipients:
+ rhettinger, tim.peters, mark.dickinson, skrah, pablogsal |
2019-02-18 20:10:59 | rhettinger | set | messageid: <1550520659.43.0.126744170658.issue36027@roundup.psfhosted.org> |
2019-02-18 20:10:59 | rhettinger | link | issue36027 messages |
2019-02-18 20:10:59 | rhettinger | create | |
|