aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorlloyd <[email protected]>2012-06-17 16:09:31 +0000
committerlloyd <[email protected]>2012-06-17 16:09:31 +0000
commit49e7fb8b07a0ae100b49a49561b3a0687f183d20 (patch)
tree4df7a7fef4ca88268bbfcd29844aaeb0c8a8fff9 /src
parent4505f66b6bda36d17c6c2163f47750e3399ff5e0 (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.cpp52
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;