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