Botan
1.11.15
|
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 }