diff options
author | Sybren A. Stüvel <sybren@stuvel.eu> | 2011-08-10 13:51:40 +0200 |
---|---|---|
committer | Sybren A. Stüvel <sybren@stuvel.eu> | 2011-08-10 13:51:40 +0200 |
commit | 64f9e1d493d85a46956ff86677afec2692ebe49a (patch) | |
tree | 75817f9df370cfa23f88ea396749a4f626b07b41 /rsa/common.py | |
parent | 360d04285b64c981d8909c2f6393c60439370b3a (diff) | |
download | rsa-64f9e1d493d85a46956ff86677afec2692ebe49a.tar.gz |
Added basic Chinese Remainder theorem implementation, not yet used.
Diffstat (limited to 'rsa/common.py')
-rw-r--r-- | rsa/common.py | 74 |
1 files changed, 74 insertions, 0 deletions
diff --git a/rsa/common.py b/rsa/common.py index 5ae92f0..4d7698f 100644 --- a/rsa/common.py +++ b/rsa/common.py @@ -69,6 +69,80 @@ def byte_size(number): return int(math.ceil(bit_size(number) / 8.0)) + +def extended_gcd(a, b): + """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb + """ + # r = gcd(a,b) i = multiplicitive inverse of a mod b + # or j = multiplicitive inverse of b mod a + # Neg return values for i or j are made positive mod b or a respectively + # Iterateive Version is faster and uses much less stack space + x = 0 + y = 1 + lx = 1 + ly = 0 + oa = a #Remember original a/b to remove + ob = b #negative values from return results + while b != 0: + q = a // b + (a, b) = (b, a % b) + (x, lx) = ((lx - (q * x)),x) + (y, ly) = ((ly - (q * y)),y) + if (lx < 0): lx += ob #If neg wrap modulo orignal b + if (ly < 0): ly += oa #If neg wrap modulo orignal a + return (a, lx, ly) #Return only positive values + +def inverse(x, n): + '''Returns x^-1 (mod n) + + >>> inverse(7, 4) + 3 + >>> (inverse(143, 4) * 143) % 4 + 1 + ''' + + (divider, inv, _) = extended_gcd(x, n) + + if divider != 1: + raise ValueError("x (%d) and n (%d) are not relatively prime" % (x, n)) + + return inv + + +def crt(a_values, modulo_values): + '''Chinese Remainder Theorem. + + Calculates x such that x = a[i] (mod m[i]) for each i. + + :param a_values: the a-values of the above equation + :param modulo_values: the m-values of the above equation + :returns: x such that x = a[i] (mod m[i]) for each i + + + >>> crt([2, 3], [3, 5]) + 8 + + >>> crt([2, 3, 2], [3, 5, 7]) + 23 + + >>> crt([2, 3, 0], [7, 11, 15]) + 135 + ''' + + m = 1 + x = 0 + + for modulo in modulo_values: + m *= modulo + + for (m_i, a_i) in zip(modulo_values, a_values): + M_i = m // m_i + inv = inverse(M_i, m_i) + + x = (x + a_i * M_i * inv) % m + + return x + if __name__ == '__main__': import doctest doctest.testmod() |