Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
math::modular_inverse::ModularInverseFermat_< PowerModImpl, checkPrimality > Class Template Reference

#include <modular_inverse_fermat.h>

List of all members.

Static Public Member Functions

template<typename T >
static T getInverse (T i, T p)

Detailed Description

template<typename PowerModImpl, bool checkPrimality = true>
class math::modular_inverse::ModularInverseFermat_< PowerModImpl, checkPrimality >

Compute modular inverses using Fermat's little theorem.

Precondition:
  • PowerModImpl contains static function powermod(base,exponent,modulo)
Parameters:
PowerModImplimplementation of powermod
checkPrimalitywhether to check that the modulo is a prime number

Member Function Documentation

template<typename PowerModImpl , bool checkPrimality = true>
template<typename T >
static T math::modular_inverse::ModularInverseFermat_< PowerModImpl, checkPrimality >::getInverse ( i,
p 
) [inline, static]

Compute modular inverse of number i over field Z_p.

The result is based on the fact, that a^(p-2) = a^(-1) mod p based on Fermat's little theorem.

Note: More general case is Euler's theorem: a^(fi(m)-1) = a^(-1) mod m but in this case, calculating fi(m) needs to factorize m and it is therefore inefficient. If you have good implementation of euler's fi, you may tweak this implementation. Anyway, consider using ModularInverseGcd for inverses for non-primes.

Parameters:
inumber for which the inverse should be calculated
pprime modulus
Returns:
inverse of the number, i.e. number such that (inverse * i) mod p == 1, or zero if such a number does not exists (case i==0)

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines