Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
#include <modular_inverse_fermat.h>
Static Public Member Functions | |
template<typename T > | |
static T | getInverse (T i, T p) |
Compute modular inverses using Fermat's little theorem.
PowerModImpl | implementation of powermod |
checkPrimality | whether to check that the modulo is a prime number |
static T math::modular_inverse::ModularInverseFermat_< PowerModImpl, checkPrimality >::getInverse | ( | T | i, |
T | 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.
i | number for which the inverse should be calculated |
p | prime modulus |