Very rarely it is necessary to find the multiplicative inverse of a number in the ring of integers modulo p. Thie recipe handles those rare cases. That is, given x, an integer, and p the modulus, we seek a integer x^-1 such that x * x^-1 = 1 mod p. For example 38 is the inverse of 8 modulo 101 since 38 * 8 = 304 = 1 mod 101. The inverse only exists when a and p are relatively prime.
Python, 25 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | def invmodp(a, p):
'''
The multiplicitive inverse of a in the integers modulo p.
Return b s.t.
a * b == 1 mod p
'''
for d in xrange(1, p):
r = (d * a) % p
if r == 1:
break
else:
raise ValueError('%d has no inverse mod %d' % (a, p))
return d
def __invmodp__test__():
p = 101
for i in range(1, p):
iinv = invmodp(i, p)
assert (iinv * i) % p == 1
a = 3
p = 4
assert (a * invmodp(a, p)) % p == 1
__invmodp__test__()
|
In case p is also prime, you can use fermats little theorem and the build in pow method: pow(a, p-2, p).
Contrary to advertisement, this recipe does not work if p is not prime. Try a=3 and p=4 for example.
Thanks Daniel, fixed.