diff options
author | lloyd <[email protected]> | 2014-01-10 03:41:59 +0000 |
---|---|---|
committer | lloyd <[email protected]> | 2014-01-10 03:41:59 +0000 |
commit | 6894dca64c04936d07048c0e8cbf7e25858548c3 (patch) | |
tree | 5d572bfde9fe667dab14e3f04b5285a85d8acd95 /src/lib/math/numbertheory/reducer.cpp | |
parent | 9efa3be92442afb3d0b69890a36c7f122df18eda (diff) |
Move lib into src
Diffstat (limited to 'src/lib/math/numbertheory/reducer.cpp')
-rw-r--r-- | src/lib/math/numbertheory/reducer.cpp | 81 |
1 files changed, 81 insertions, 0 deletions
diff --git a/src/lib/math/numbertheory/reducer.cpp b/src/lib/math/numbertheory/reducer.cpp new file mode 100644 index 000000000..8e8951c46 --- /dev/null +++ b/src/lib/math/numbertheory/reducer.cpp @@ -0,0 +1,81 @@ +/* +* Modular Reducer +* (C) 1999-2011 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include <botan/reducer.h> +#include <botan/internal/mp_core.h> + +namespace Botan { + +/* +* Modular_Reducer Constructor +*/ +Modular_Reducer::Modular_Reducer(const BigInt& mod) + { + if(mod <= 0) + throw Invalid_Argument("Modular_Reducer: modulus must be positive"); + + modulus = mod; + mod_words = modulus.sig_words(); + + modulus_2 = Botan::square(modulus); + + mu = BigInt::power_of_2(2 * MP_WORD_BITS * mod_words) / modulus; + } + +/* +* Barrett Reduction +*/ +BigInt Modular_Reducer::reduce(const BigInt& x) const + { + if(mod_words == 0) + throw Invalid_State("Modular_Reducer: Never initalized"); + + if(x.cmp(modulus, false) < 0) + { + if(x.is_negative()) + return x + modulus; // make positive + return x; + } + else if(x.cmp(modulus_2, false) < 0) + { + BigInt t1 = x; + t1.set_sign(BigInt::Positive); + t1 >>= (MP_WORD_BITS * (mod_words - 1)); + t1 *= mu; + + t1 >>= (MP_WORD_BITS * (mod_words + 1)); + t1 *= modulus; + + t1.mask_bits(MP_WORD_BITS * (mod_words + 1)); + + BigInt t2 = x; + t2.set_sign(BigInt::Positive); + t2.mask_bits(MP_WORD_BITS * (mod_words + 1)); + + t2 -= t1; + + if(t2.is_negative()) + { + t2 += BigInt::power_of_2(MP_WORD_BITS * (mod_words + 1)); + } + + while(t2 >= modulus) + t2 -= modulus; + + if(x.is_positive()) + return t2; + else + return (modulus - t2); + } + else + { + // too big, fall back to normal division + return (x % modulus); + } + } + +} |