Welcome, guest | Sign In | My Account | Store | Cart
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__()

History