Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_MATH_PRIMES_MODULAR_INVERSE_GCD 00002 #define H_MATH_PRIMES_MODULAR_INVERSE_GCD 00003 00010 #include "math/primes/primes_basic.h" 00011 #include "math/powermod/powermod.h" 00012 #include "math/gcd/extended_gcd.h" 00013 00014 namespace math { 00015 namespace modular_inverse { 00016 00026 class ModularInverseGcd { 00027 public: 00033 template <typename T> 00034 static T getInverse(T i, T p) { 00035 Preconditions::check(p > 1); 00036 Preconditions::checkRange(i, p); 00037 std::pair<T, T> tmp = math::gcd::ExtendedGCD::extended_gcd(i, p); 00038 // Note: the following statement may overflow during computation. But this is OK! 00039 // The overflows in subexpressions will cancel each other! 00040 T g = tmp.first * i + tmp.second * p; 00041 if (g == 1) { // the inverse exists 00042 assert(tmp.first < p); 00043 assert(tmp.second > -p); 00044 assert(tmp.first != 0); 00045 if (tmp.first >= 0) { 00046 return tmp.first; 00047 } else { 00048 return tmp.first + p; 00049 } 00050 } else { 00051 return 0; 00052 } 00053 } 00054 }; 00055 00056 } // namespace modular_inverse 00057 } // namespace math 00058 00059 #endif