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