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__()
Diff to Previous Revision
--- revision 3 2009-05-03 17:03:41
+++ revision 4 2013-01-31 23:41:21
@@ -5,10 +5,7 @@
a * b == 1 mod p
'''
- r = a
- d = 1
- for count in xrange(p):
- d = ((p // r + 1) * d) % p
+ for d in xrange(1, p):
r = (d * a) % p
if r == 1:
break
@@ -21,4 +18,8 @@
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__()
