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

#include <modular_inverse_precomputed.h>

List of all members.

Public Member Functions

template<typename T >
void initialize (T t_size)
template<typename T >
SizeType getInverse (T t_pos)

Private Types

typedef std::vector< bool >
::size_type 
SizeType

Private Attributes

std::vector< SizeTypeinverses

Detailed Description

template<class PowerModImpl>
class math::modular_inverse::ModularInversePrecomputed_< PowerModImpl >

Calculate the modular inverses of all numbers modulo prime p in O(p) time and 2*p space.

The initialization is in O(p), query is in O(1). The implementation is thus useful for medium-sized p (limited memory), for which you will ask for many different inverses. If you will ask only limited number of questions, but the p is big, it is probably better to use ModularInverseGcd class


Member Typedef Documentation

template<class PowerModImpl >
typedef std::vector<bool>::size_type math::modular_inverse::ModularInversePrecomputed_< PowerModImpl >::SizeType [private]

Member Function Documentation

template<class PowerModImpl >
template<typename T >
SizeType math::modular_inverse::ModularInversePrecomputed_< PowerModImpl >::getInverse ( t_pos) [inline]

Return inverse of number pos

template<class PowerModImpl >
template<typename T >
void math::modular_inverse::ModularInversePrecomputed_< PowerModImpl >::initialize ( t_size) [inline]

Member Data Documentation

template<class PowerModImpl >
std::vector<SizeType> math::modular_inverse::ModularInversePrecomputed_< PowerModImpl >::inverses [private]

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