diff options
author | lloyd <[email protected]> | 2012-06-17 16:09:31 +0000 |
---|---|---|
committer | lloyd <[email protected]> | 2012-06-17 16:09:31 +0000 |
commit | 49e7fb8b07a0ae100b49a49561b3a0687f183d20 (patch) | |
tree | 4df7a7fef4ca88268bbfcd29844aaeb0c8a8fff9 /src | |
parent | 4505f66b6bda36d17c6c2163f47750e3399ff5e0 (diff) |
Use a special case for odd moduli in inverse_mod with close to double
performance.
Diffstat (limited to 'src')
-rw-r--r-- | src/math/numbertheory/numthry.cpp | 52 |
1 files changed, 51 insertions, 1 deletions
diff --git a/src/math/numbertheory/numthry.cpp b/src/math/numbertheory/numthry.cpp index 5a87b4466..58275fb4f 100644 --- a/src/math/numbertheory/numthry.cpp +++ b/src/math/numbertheory/numthry.cpp @@ -198,6 +198,54 @@ BigInt lcm(const BigInt& a, const BigInt& b) return ((a * b) / gcd(a, b)); } +namespace { + +/* +* If the modulus is odd, then we can avoid computing A and C. This is +* a critical path algorithm in some instances and an odd modulus is +* the common case for crypto, so worth special casing. See note 14.64 +* in Handbook of Applied Cryptography for more details. +*/ +BigInt inverse_mod_odd_modulus(const BigInt& n, const BigInt& mod) + { + BigInt u = mod, v = n; + BigInt B = 0, D = 1; + + while(u.is_nonzero()) + { + const size_t u_zero_bits = low_zero_bits(u); + u >>= u_zero_bits; + for(size_t i = 0; i != u_zero_bits; ++i) + { + if(B.is_odd()) + { B -= mod; } + B >>= 1; + } + + const size_t v_zero_bits = low_zero_bits(v); + v >>= v_zero_bits; + for(size_t i = 0; i != v_zero_bits; ++i) + { + if(D.is_odd()) + { D -= mod; } + D >>= 1; + } + + if(u >= v) { u -= v; B -= D; } + else { v -= u; D -= B; } + } + + if(v != 1) + return 0; // no modular inverse + + while(D.is_negative()) D += mod; + while(D >= mod) D -= mod; + + return D; + } + +} + /* * Find the Modular Inverse */ @@ -211,7 +259,9 @@ BigInt inverse_mod(const BigInt& n, const BigInt& mod) if(n.is_zero() || (n.is_even() && mod.is_even())) return 0; // fast fail checks - //const BigInt x = mod, y = n; + if(mod.is_odd()) + return inverse_mod_odd_modulus(n, mod); + BigInt u = mod, v = n; BigInt A = 1, B = 0, C = 0, D = 1; |