Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/math/modular_inverse/modular_inverse_precomputed.h
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines