Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_MATH_PRIMES_MODULAR_INVERSE_FERMAT 00002 #define H_MATH_PRIMES_MODULAR_INVERSE_FERMAT 00003 00009 #include "math/primes/primes_basic.h" 00010 #include "math/powermod/powermod.h" 00011 00012 namespace math { 00013 namespace modular_inverse { 00014 00024 template <typename PowerModImpl, bool checkPrimality = true> 00025 class ModularInverseFermat_ { 00026 public: 00047 template <typename T> 00048 static T getInverse(T i, T p) { 00049 Preconditions::check(p > 1); 00050 Preconditions::checkRange(i, p); 00051 00052 // * This check is slowing down whole function! * 00053 // * If you are sure about primality of p, consider * 00054 // * using checkPrimality = false * 00055 if (checkPrimality) { 00056 Preconditions::check(math::primes::PrimesBasic::isPrime(p), 00057 "ModularInverseFermat needs prime to work!"); 00058 } 00059 00060 // Note: we can't ignore this check and be happy that powermod(0, p-2, p) == 0 00061 // as powemod(0, 0, 2) == 1 and that is wrong output in our case! 00062 if (i == 0) { 00063 return 0; 00064 } 00065 return PowerModImpl::powermod(i, p-2, p); 00066 } 00067 }; 00068 00069 typedef ModularInverseFermat_<math::powermod::PowermodSimple> ModularInverseFermat; 00070 00071 } // namespace modular_inverse 00072 } // namespace math 00073 00074 #endif