Botan  1.11.15
src/lib/math/numbertheory/powm_fw.cpp
Go to the documentation of this file.
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 }