Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_MATH_PRIMES_MODULAR_INVERSE_PRECOMPUTED 00002 #define H_MATH_PRIMES_MODULAR_INVERSE_PRECOMPUTED 00003 00008 #include <vector> 00009 #include <stack> 00010 #include <utils/preconditions/preconditions.h> 00011 #include <utils/assert/integer_overflow.h> 00012 #include <math/powermod/powermod.h> 00013 #include <math/primes/primes_basic.h> 00014 00015 namespace math { 00016 namespace modular_inverse { 00017 00028 template <class PowerModImpl> 00029 class ModularInversePrecomputed_ { 00030 typedef std::vector<bool>::size_type SizeType; 00031 public: 00032 template <typename T> 00033 void initialize(T t_size) { 00034 Preconditions::check(math::primes::PrimesBasic::isPrime(t_size), 00035 "ModularInverse needs prime to work!"); 00036 STATIC_ASSERT_CHECK_INTEGER_OVERFLOW<T, SizeType>(); 00037 SizeType p = (SizeType) t_size; 00038 // FIXME 00039 //Preconditions::check(p <= PowerModImpl::max_argument((SizeType) 0)); 00040 inverses.resize(p); 00041 00042 for (SizeType q = 0; q < p; q++) inverses[q] = 0; 00043 inverses[1] = 1; 00044 std::stack<SizeType> subgroup; 00045 00046 for (SizeType i = 2; i < p; i++) { 00047 if (inverses[i] != 0) continue; // we have already computed this 00048 SizeType current = i; 00049 // go over multiplicatevi subgroup of `current' 00050 while (inverses[current] == 0) { 00051 subgroup.push(current); 00052 current = PowerModImpl::multmod(current, i, p); 00053 } 00054 00055 // now go back 00056 SizeType t = PowerModImpl::multmod(i, inverses[current], p); 00057 while (!subgroup.empty()) { 00058 inverses[subgroup.top()] = t; 00059 subgroup.pop(); 00060 t = PowerModImpl::multmod(i, t, p); 00061 } 00062 } 00063 } 00064 00068 template <typename T> 00069 SizeType getInverse(T t_pos) { 00070 STATIC_ASSERT_CHECK_INTEGER_OVERFLOW<T, SizeType>(); 00071 SizeType pos = (SizeType) t_pos; 00072 Preconditions::checkRange(pos, inverses.size()); 00073 return inverses[pos]; 00074 } 00075 private: 00076 std::vector<SizeType> inverses; 00077 }; 00078 00079 typedef ModularInversePrecomputed_<math::powermod::PowermodSimple> ModularInversePrecomputed; 00080 00081 } // namespace modular_inverse 00082 } // namespace math 00083 #endif