Botan
1.11.15
|
00001 /* 00002 * Fixed Window Exponentiation 00003 * (C) 1999-2007 Jack Lloyd 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 */ 00007 00008 #include <botan/internal/def_powm.h> 00009 #include <botan/numthry.h> 00010 #include <vector> 00011 00012 namespace Botan { 00013 00014 /* 00015 * Set the exponent 00016 */ 00017 void Fixed_Window_Exponentiator::set_exponent(const BigInt& e) 00018 { 00019 exp = e; 00020 } 00021 00022 /* 00023 * Set the base 00024 */ 00025 void Fixed_Window_Exponentiator::set_base(const BigInt& base) 00026 { 00027 window_bits = Power_Mod::window_bits(exp.bits(), base.bits(), hints); 00028 00029 g.resize((1 << window_bits)); 00030 g[0] = 1; 00031 g[1] = base; 00032 00033 for(size_t i = 2; i != g.size(); ++i) 00034 g[i] = reducer.multiply(g[i-1], g[0]); 00035 } 00036 00037 /* 00038 * Compute the result 00039 */ 00040 BigInt Fixed_Window_Exponentiator::execute() const 00041 { 00042 const size_t exp_nibbles = (exp.bits() + window_bits - 1) / window_bits; 00043 00044 BigInt x = 1; 00045 00046 for(size_t i = exp_nibbles; i > 0; --i) 00047 { 00048 for(size_t j = 0; j != window_bits; ++j) 00049 x = reducer.square(x); 00050 00051 const u32bit nibble = exp.get_substring(window_bits*(i-1), window_bits); 00052 00053 x = reducer.multiply(x, g[nibble]); 00054 } 00055 return x; 00056 } 00057 00058 /* 00059 * Fixed_Window_Exponentiator Constructor 00060 */ 00061 Fixed_Window_Exponentiator::Fixed_Window_Exponentiator(const BigInt& n, 00062 Power_Mod::Usage_Hints hints) 00063 { 00064 reducer = Modular_Reducer(n); 00065 this->hints = hints; 00066 window_bits = 0; 00067 } 00068 00069 }