Botan  1.11.15
src/lib/math/numbertheory/reducer.cpp
Go to the documentation of this file.
00001 /*
00002 * Modular Reducer
00003 * (C) 1999-2011 Jack Lloyd
00004 *
00005 * Botan is released under the Simplified BSD License (see license.txt)
00006 */
00007 
00008 #include <botan/reducer.h>
00009 #include <botan/internal/mp_core.h>
00010 
00011 namespace Botan {
00012 
00013 /*
00014 * Modular_Reducer Constructor
00015 */
00016 Modular_Reducer::Modular_Reducer(const BigInt& mod)
00017    {
00018    if(mod <= 0)
00019       throw Invalid_Argument("Modular_Reducer: modulus must be positive");
00020 
00021    modulus = mod;
00022    mod_words = modulus.sig_words();
00023 
00024    modulus_2 = Botan::square(modulus);
00025 
00026    mu = BigInt::power_of_2(2 * MP_WORD_BITS * mod_words) / modulus;
00027    }
00028 
00029 /*
00030 * Barrett Reduction
00031 */
00032 BigInt Modular_Reducer::reduce(const BigInt& x) const
00033    {
00034    if(mod_words == 0)
00035       throw Invalid_State("Modular_Reducer: Never initalized");
00036 
00037    if(x.cmp(modulus, false) < 0)
00038       {
00039       if(x.is_negative())
00040          return x + modulus; // make positive
00041       return x;
00042       }
00043    else if(x.cmp(modulus_2, false) < 0)
00044       {
00045       BigInt t1 = x;
00046       t1.set_sign(BigInt::Positive);
00047       t1 >>= (MP_WORD_BITS * (mod_words - 1));
00048       t1 *= mu;
00049 
00050       t1 >>= (MP_WORD_BITS * (mod_words + 1));
00051       t1 *= modulus;
00052 
00053       t1.mask_bits(MP_WORD_BITS * (mod_words + 1));
00054 
00055       BigInt t2 = x;
00056       t2.set_sign(BigInt::Positive);
00057       t2.mask_bits(MP_WORD_BITS * (mod_words + 1));
00058 
00059       t2 -= t1;
00060 
00061       if(t2.is_negative())
00062          {
00063          t2 += BigInt::power_of_2(MP_WORD_BITS * (mod_words + 1));
00064          }
00065 
00066       while(t2 >= modulus)
00067          t2 -= modulus;
00068 
00069       if(x.is_positive())
00070          return t2;
00071       else
00072          return (modulus - t2);
00073       }
00074    else
00075       {
00076       // too big, fall back to normal division
00077       return (x % modulus);
00078       }
00079    }
00080 
00081 }