Botan  1.11.12
powm_fw.cpp
Go to the documentation of this file.
1 /*
2 * Fixed Window Exponentiation
3 * (C) 1999-2007 Jack Lloyd
4 *
5 * Distributed under the terms of the Botan license
6 */
7 
8 #include <botan/internal/def_powm.h>
9 #include <botan/numthry.h>
10 #include <vector>
11 
12 namespace Botan {
13 
14 /*
15 * Set the exponent
16 */
18  {
19  exp = e;
20  }
21 
22 /*
23 * Set the base
24 */
26  {
27  window_bits = Power_Mod::window_bits(exp.bits(), base.bits(), hints);
28 
29  g.resize((1 << window_bits));
30  g[0] = 1;
31  g[1] = base;
32 
33  for(size_t i = 2; i != g.size(); ++i)
34  g[i] = reducer.multiply(g[i-1], g[0]);
35  }
36 
37 /*
38 * Compute the result
39 */
41  {
42  const size_t exp_nibbles = (exp.bits() + window_bits - 1) / window_bits;
43 
44  BigInt x = 1;
45 
46  for(size_t i = exp_nibbles; i > 0; --i)
47  {
48  for(size_t j = 0; j != window_bits; ++j)
49  x = reducer.square(x);
50 
51  const u32bit nibble = exp.get_substring(window_bits*(i-1), window_bits);
52 
53  x = reducer.multiply(x, g[nibble]);
54  }
55  return x;
56  }
57 
58 /*
59 * Fixed_Window_Exponentiator Constructor
60 */
63  {
64  reducer = Modular_Reducer(n);
65  this->hints = hints;
66  window_bits = 0;
67  }
68 
69 }
Fixed_Window_Exponentiator(const BigInt &, Power_Mod::Usage_Hints)
Definition: powm_fw.cpp:61
u32bit get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:150
size_t bits() const
Definition: bigint.cpp:233
uint32_t u32bit
Definition: types.h:32
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition: reducer.h:31
Definition: buf_comp.h:15
static size_t window_bits(size_t exp_bits, size_t base_bits, Power_Mod::Usage_Hints hints)
Definition: pow_mod.cpp:117
void set_base(const BigInt &)
Definition: powm_fw.cpp:25
void set_exponent(const BigInt &)
Definition: powm_fw.cpp:17
BigInt square(const BigInt &x) const
Definition: reducer.h:39