Botan  2.4.0
Crypto and TLS for C++11
reducer.cpp
Go to the documentation of this file.
1 /*
2 * Modular Reducer
3 * (C) 1999-2011 Jack Lloyd
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7 
8 #include <botan/reducer.h>
9 #include <botan/internal/mp_core.h>
10 
11 namespace Botan {
12 
13 /*
14 * Modular_Reducer Constructor
15 */
17  {
18  if(mod <= 0)
19  throw Invalid_Argument("Modular_Reducer: modulus must be positive");
20 
21  m_modulus = mod;
22  m_mod_words = m_modulus.sig_words();
23 
24  m_modulus_2 = Botan::square(m_modulus);
25 
26  m_mu = BigInt::power_of_2(2 * MP_WORD_BITS * m_mod_words) / m_modulus;
27  }
28 
29 /*
30 * Barrett Reduction
31 */
33  {
34  if(m_mod_words == 0)
35  throw Invalid_State("Modular_Reducer: Never initalized");
36 
37  if(x.cmp(m_modulus, false) < 0)
38  {
39  if(x.is_negative())
40  return x + m_modulus; // make positive
41  return x;
42  }
43  else if(x.cmp(m_modulus_2, false) < 0)
44  {
45  BigInt t1 = x;
47  t1 >>= (MP_WORD_BITS * (m_mod_words - 1));
48  t1 *= m_mu;
49 
50  t1 >>= (MP_WORD_BITS * (m_mod_words + 1));
51  t1 *= m_modulus;
52 
53  t1.mask_bits(MP_WORD_BITS * (m_mod_words + 1));
54 
55  BigInt t2 = x;
57  t2.mask_bits(MP_WORD_BITS * (m_mod_words + 1));
58 
59  t2 -= t1;
60 
61  if(t2.is_negative())
62  {
63  t2 += BigInt::power_of_2(MP_WORD_BITS * (m_mod_words + 1));
64  }
65 
66  while(t2 >= m_modulus)
67  t2 -= m_modulus;
68 
69  if(x.is_positive())
70  return t2;
71  else
72  return (m_modulus - t2);
73  }
74  else
75  {
76  // too big, fall back to normal division
77  return (x % m_modulus);
78  }
79  }
80 
81 }
bool is_negative() const
Definition: bigint.h:353
int32_t cmp(const BigInt &n, bool check_signs=true) const
Definition: bigint.cpp:97
void mask_bits(size_t n)
Definition: bigint.h:281
BigInt square(const BigInt &x)
Definition: mp_numth.cpp:19
static BigInt power_of_2(size_t n)
Definition: bigint.h:499
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:398
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:32
void set_sign(Sign sign)
Definition: bigint.cpp:214
bool is_positive() const
Definition: bigint.h:359
const size_t MP_WORD_BITS
Definition: mp_core.h:22