Commits

committed 970a380

• Participants
• Parent commits b3c60d8

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)))`
` `