diff options
| -rw-r--r-- | src/lib/math/numbertheory/numthry.cpp | 42 |
1 files changed, 23 insertions, 19 deletions
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp index 7af1d13df..a69028189 100644 --- a/src/lib/math/numbertheory/numthry.cpp +++ b/src/lib/math/numbertheory/numthry.cpp @@ -1,12 +1,11 @@ /* * Number Theory Functions -* (C) 1999-2011,2016,2018 Jack Lloyd +* (C) 1999-2011,2016,2018,2019 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) */ #include <botan/numthry.h> -#include <botan/pow_mod.h> #include <botan/reducer.h> #include <botan/monty.h> #include <botan/divide.h> @@ -427,29 +426,34 @@ BigInt power_mod(const BigInt& base, const BigInt& exp, const BigInt& mod) return 0; } - Power_Mod pow_mod(mod); + Modular_Reducer reduce_mod(mod); - /* - * Calling set_base before set_exponent means we end up using a - * minimal window. This makes sense given that here we know that any - * precomputation is wasted. - */ + const size_t exp_bits = exp.bits(); - if(base.is_negative()) + if(mod.is_odd()) { - pow_mod.set_base(-base); - pow_mod.set_exponent(exp); - if(exp.is_even()) - return pow_mod.execute(); - else - return (mod - pow_mod.execute()); + const size_t powm_window = 4; + + auto monty_mod = std::make_shared<Montgomery_Params>(mod, reduce_mod); + auto powm_base_mod = monty_precompute(monty_mod, reduce_mod.reduce(base), powm_window); + return monty_execute(*powm_base_mod, exp, exp_bits); } - else + + /* + Support for even modulus is just a convenience and not considered + cryptographically important, so this implementation is slow ... + */ + BigInt accum = 1; + BigInt g = reduce_mod.reduce(base); + BigInt t; + + for(size_t i = 0; i != exp_bits; ++i) { - pow_mod.set_base(base); - pow_mod.set_exponent(exp); - return pow_mod.execute(); + t = reduce_mod.multiply(g, accum); + g = reduce_mod.square(g); + accum.ct_cond_assign(exp.get_bit(i), t); } + return accum; } |