Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/math/powermod/powermod.h
Go to the documentation of this file.
00001 #ifndef H_MATH_POWERMOD
00002 #define H_MATH_POWERMOD
00003 
00007 #include "utils/static_assert/static_assert.h"
00008 #include "utils/preconditions/preconditions.h"
00009 #include <limits>
00010 #include "multmod_simple.h"
00011 #include "multmod_extended.h"
00012 
00013 namespace math {
00014 namespace powermod {
00015 
00016 # pragma GCC diagnostic ignored "-Wtype-limits"
00017 template <class MultModImpl>
00018 class Powermod_ {
00019   public:
00020   template <typename T>
00021     static T powermod(T base, T power, T modulo) {
00022     Preconditions::check(modulo > 0, "Modulo should be positive.");
00023     Preconditions::check(power >= 0, "We don't support modular inverses.");
00024     Preconditions::checkRange(base, modulo);
00025     const T max = MultModImpl::max_argument((T) 0); 
00026     Preconditions::check(modulo <= max, "Too big argument for powermod");
00027     // Beware of special case power==0 && modulo==1 (result is 0 not 1)
00028     if (modulo == 1) {
00029       return 0;
00030     }
00031     T result = 1;
00032     T current = base;
00033     while (power > 0) {
00034       if (power % 2) {
00035         result = MultModImpl::multmod(result, current, modulo);
00036       }
00037       current = MultModImpl::multmod(current, current, modulo);
00038       power /= 2;
00039     }
00040     return result;
00041   }
00042 
00043   template <typename T>
00044   static T multmod(T a, T b, T modulo) {
00045     Preconditions::check(modulo > 0, "Modulo should be positive.");
00046     Preconditions::checkRange(a, modulo);
00047     Preconditions::checkRange(b, modulo);
00048     const T max = MultModImpl::max_argument((T) 0);
00049     Preconditions::check(modulo <= max, "Too big argument for multmod");
00050 
00051     return MultModImpl::multmod(a, b, modulo);
00052   }
00053 };
00054 
00055 typedef Powermod_<MultmodSimple> PowermodSimple;
00056 typedef Powermod_<MultmodExtendedOpt> PowermodExtended;
00057 
00058 } // namespace powermod
00059 } // namespace math
00060 
00061 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines