Commits

Anonymous committed 970a380

Add recipe for multiplicative inverse.

  • Participants
  • Parent commits b3c60d8

Comments (0)

Files changed (2)

File crypto/multiplicative_inverse.py

+def multinv(modulus, value):
+    '''Multiplicative inverse in a given modulus
+
+        >>> multinv(191, 138)
+        18
+        >>> multinv(191, 38)
+        186
+        >>> multinv(120, 23)
+        47
+
+    '''
+    # 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
+
+
+if __name__ == '__main__':
+    import doctest
+    print(doctest.testmod())

File timings/time_cmp_to_key.py

 
 if __name__=='__main__':
     from timeit import Timer
-    t = Timer("test()", "from __main__ import test")
+    t = Timer(test)
     print(min(t.repeat(7, 1000)))