Botan  1.11.15
src/lib/math/numbertheory/pow_mod.cpp
Go to the documentation of this file.
00001 /*
00002 * Modular Exponentiation Proxy
00003 * (C) 1999-2007 Jack Lloyd
00004 *
00005 * Botan is released under the Simplified BSD License (see license.txt)
00006 */
00007 
00008 #include <botan/pow_mod.h>
00009 #include <botan/internal/def_powm.h>
00010 
00011 namespace Botan {
00012 
00013 /*
00014 * Power_Mod Constructor
00015 */
00016 Power_Mod::Power_Mod(const BigInt& n, Usage_Hints hints)
00017    {
00018    core = nullptr;
00019    set_modulus(n, hints);
00020    }
00021 
00022 /*
00023 * Power_Mod Copy Constructor
00024 */
00025 Power_Mod::Power_Mod(const Power_Mod& other)
00026    {
00027    core = nullptr;
00028    if(other.core)
00029       core = other.core->copy();
00030    }
00031 
00032 /*
00033 * Power_Mod Assignment Operator
00034 */
00035 Power_Mod& Power_Mod::operator=(const Power_Mod& other)
00036    {
00037    delete core;
00038    core = nullptr;
00039    if(other.core)
00040       core = other.core->copy();
00041    return (*this);
00042    }
00043 
00044 /*
00045 * Power_Mod Destructor
00046 */
00047 Power_Mod::~Power_Mod()
00048    {
00049    delete core;
00050    core = nullptr;
00051    }
00052 
00053 /*
00054 * Set the modulus
00055 */
00056 void Power_Mod::set_modulus(const BigInt& n, Usage_Hints hints) const
00057    {
00058    delete core;
00059 
00060    if(n.is_odd())
00061       core = new Montgomery_Exponentiator(n, hints);
00062    else if(n != 0)
00063       core = new Fixed_Window_Exponentiator(n, hints);
00064    }
00065 
00066 /*
00067 * Set the base
00068 */
00069 void Power_Mod::set_base(const BigInt& b) const
00070    {
00071    if(b.is_zero() || b.is_negative())
00072       throw Invalid_Argument("Power_Mod::set_base: arg must be > 0");
00073 
00074    if(!core)
00075       throw Internal_Error("Power_Mod::set_base: core was NULL");
00076    core->set_base(b);
00077    }
00078 
00079 /*
00080 * Set the exponent
00081 */
00082 void Power_Mod::set_exponent(const BigInt& e) const
00083    {
00084    if(e.is_negative())
00085       throw Invalid_Argument("Power_Mod::set_exponent: arg must be > 0");
00086 
00087    if(!core)
00088       throw Internal_Error("Power_Mod::set_exponent: core was NULL");
00089    core->set_exponent(e);
00090    }
00091 
00092 /*
00093 * Compute the result
00094 */
00095 BigInt Power_Mod::execute() const
00096    {
00097    if(!core)
00098       throw Internal_Error("Power_Mod::execute: core was NULL");
00099    return core->execute();
00100    }
00101 
00102 /*
00103 * Try to choose a good window size
00104 */
00105 size_t Power_Mod::window_bits(size_t exp_bits, size_t,
00106                               Power_Mod::Usage_Hints hints)
00107    {
00108    static const size_t wsize[][2] = {
00109       { 1434, 7 },
00110       {  539, 6 },
00111       {  197, 4 },
00112       {   70, 3 },
00113       {   25, 2 },
00114       {    0, 0 }
00115    };
00116 
00117    size_t window_bits = 1;
00118 
00119    if(exp_bits)
00120       {
00121       for(size_t j = 0; wsize[j][0]; ++j)
00122          {
00123          if(exp_bits >= wsize[j][0])
00124             {
00125             window_bits += wsize[j][1];
00126             break;
00127             }
00128          }
00129       }
00130 
00131    if(hints & Power_Mod::BASE_IS_FIXED)
00132       window_bits += 2;
00133    if(hints & Power_Mod::EXP_IS_LARGE)
00134       ++window_bits;
00135 
00136    return window_bits;
00137    }
00138 
00139 namespace {
00140 
00141 /*
00142 * Choose potentially useful hints
00143 */
00144 Power_Mod::Usage_Hints choose_base_hints(const BigInt& b, const BigInt& n)
00145    {
00146    if(b == 2)
00147       return Power_Mod::Usage_Hints(Power_Mod::BASE_IS_2 |
00148                                     Power_Mod::BASE_IS_SMALL);
00149 
00150    const size_t b_bits = b.bits();
00151    const size_t n_bits = n.bits();
00152 
00153    if(b_bits < n_bits / 32)
00154       return Power_Mod::BASE_IS_SMALL;
00155    if(b_bits > n_bits / 4)
00156       return Power_Mod::BASE_IS_LARGE;
00157 
00158    return Power_Mod::NO_HINTS;
00159    }
00160 
00161 /*
00162 * Choose potentially useful hints
00163 */
00164 Power_Mod::Usage_Hints choose_exp_hints(const BigInt& e, const BigInt& n)
00165    {
00166    const size_t e_bits = e.bits();
00167    const size_t n_bits = n.bits();
00168 
00169    if(e_bits < n_bits / 32)
00170       return Power_Mod::BASE_IS_SMALL;
00171    if(e_bits > n_bits / 4)
00172       return Power_Mod::BASE_IS_LARGE;
00173    return Power_Mod::NO_HINTS;
00174    }
00175 
00176 }
00177 
00178 /*
00179 * Fixed_Exponent_Power_Mod Constructor
00180 */
00181 Fixed_Exponent_Power_Mod::Fixed_Exponent_Power_Mod(const BigInt& e,
00182                                                    const BigInt& n,
00183                                                    Usage_Hints hints) :
00184    Power_Mod(n, Usage_Hints(hints | EXP_IS_FIXED | choose_exp_hints(e, n)))
00185    {
00186    set_exponent(e);
00187    }
00188 
00189 /*
00190 * Fixed_Base_Power_Mod Constructor
00191 */
00192 Fixed_Base_Power_Mod::Fixed_Base_Power_Mod(const BigInt& b, const BigInt& n,
00193                                            Usage_Hints hints) :
00194    Power_Mod(n, Usage_Hints(hints | BASE_IS_FIXED | choose_base_hints(b, n)))
00195    {
00196    set_base(b);
00197    }
00198 
00199 }