ModEngine

Files CCore/inc/math/ModEngine.h CCore/src/math/ModEngine.cpp

ModEngine and related classes support modular arithmetic.

BitScanner

BitScanner performs the bit scanning of an unsigned integer from MSB to LSB.

template <class UInt>
class BitScanner : NoCopy
 {
   ....

  public:
 
   explicit BitScanner(UInt d);
   
   boolable operator + () const;
   
   boolable operator * () const;
   
   void operator ++ ();
 };

Constructor takes an unsigned integer value to be scanned as the argument. The type is determined by the template parameter. In each moment scanner "observes" some bit position or the past-the-last bit position. Initially it observes the most significant 1-bit position, if any. Otherwise it starts with the past-the-last bit position.

operator + returns true, if the scanner is at some bit position.

operator * returns the current bit. Scanner must be at a bit position.

operator ++ moves to the next bit position. Scanner must be at a bit position. If the current bit is the LSB, the scanner is moved to the past-the-last bit position.

IntegerBitScanner

IntegerBitScanner performs the bit scanning of the Integer from MSB to LSB. It works the same way as the BitScanner. The template parameter is the Integer type.

template <class Integer>
class IntegerBitScanner : NoCopy
 {
   ....

  public:
 
   explicit IntegerBitScanner(const Integer &d); // d >= 0
   
   ~IntegerBitScanner() {}
   
   boolable operator + () const;
   
   boolable operator * () const;
   
   void operator ++ ();
 };

Constructor takes an Integer to be scanned as the argument. The value must be >= 0. Other methods works the same way as the corespondent BitScanner methods.

UnitsPowInteger

This class builds an Integer with the unit representation {0,0,...,0,1}. In other words, with the value Bⁿ, where B is 2^UnitBits.

template <class Integer>
class UnitsPowInteger : public Integer
 {
   ....

  public:
  
   explicit UnitsPowInteger(ulen n); // creates B^n , B = 2^UnitBits

   ~UnitsPowInteger() {}
 };

ModEngine

ModEngine performs modular operations by the given module. Operation arguments and results lay in the range [0,M), where M is the module.

template <class Integer>
class ModEngine : NoCopy
 {
   ....

  public: 
   
   explicit ModEngine(const Integer &M); // M > 0
   
   ~ModEngine() {}

   const Integer & getModule() const { return M; }
   
   Integer prepare(const Integer &a) const; // a >= 0
   
   Integer mod(Integer a) const; // a >= 0 , a < M^2

   Integer mul(const Integer &a,const Integer &b) const; // a,b >= 0 , a,b < M
   
   Integer sq(const Integer &a) const; // a >= 0 , a < M
   
   Integer mac(const Integer &s,const Integer &a,const Integer &b) const; // s,a,b >= 0 , s,a,b < M
   
   Integer squac(const Integer &s,const Integer &a) const; // s,a >= 0 , s,a < M
   
   template <class UInt>
   Meta::EnableIf<Meta::IsUInt<UInt>::Ret,Integer> pow(const Integer &a,UInt d) const; // a >=0 , a < M , M > 1
   
   Integer pow(const Integer &a,const Integer &d) const; // a,d >=0 , a < M , M > 1
 };

The only constructor argument is the module, which must be positive. The module can be retrieved by the method getModule().

prepare() returns the remainder of the division by the module. The argument must be >= 0.

mod() returns the remainder of the division by the module. The argument must be >= 0 and <M². This method is more efficient, than prepare(). It is used to implement other operations.

mul() calculates the modular multiplication of the arguments.

sq() calculates the modular square of the argument (sq(a) == mul(a,a)).

mac() calculates the MAC, i.e. the expression s+a*b, by the module.

squac() calculates the "square and accumulate", i.e. the expression s+a*a, by the module.

pow() calculates the modular power. It is assumed, that the module is >1.