modular_arithmetic.cc

Go to the documentation of this file.

// modular arithmetic
// this module written by Thorsten Reinecke, 2000-04-13
// last change: 2000-04-14

// Grundidee: a mod N = a - floor(a/N)*N
// Trick: (teure) Division vermeiden durch Vorberechnung von (2^k)/N,
//        denn: 1/N = ((2^k)/N) * (1/(2^k))
//        und Division durch 2^k durch Shiften
// Einzige Bedingung: a darf nicht zu groß werden (oder k muß vergrößert werden)

class CN_Residue
{
 private:
  mpz_t N; // Modulo
  mpz_t R; // reciprocal of N (=2^(2*ldN)/N)
  mpz_t h; // helper variable
  unsigned int k;
 public:
  inline CN_Residue() // constructor
    {
      cout << "Modular arithmetic using precomputed reciprocal activated." << endl;
      mpz_init(N); mpz_init(R); mpz_init(h);
      k=0; // initialize with a dummy value
    };
  inline void init(const mpz_t M) // Initialization
    {
      mpz_set(N,M); // NResidue --> mod N
      k=mpz_sizeinbase(N,2)+1;
      mpz_set_ui(h,1); mpz_mul_2exp(h,h,2*k);
      mpz_cdiv_q(R,h,N); //mpz_add_ui(R,R,1);
    };
  inline explicit CN_Residue(const mpz_t M) // constructor
    { 
      CN_Residue();
      init(M);
    };
  inline ~CN_Residue() // destructor
    {
      mpz_clear(N);
      mpz_clear(R);
      mpz_clear(h);
    };
  inline void mod(mpz_t res, const mpz_t a) // res = a mod N
    {
      mpz_fdiv_q_2exp(h,a,k-1); mpz_add_ui(h,h,1);
      mpz_mul(h,h,R); 
      mpz_fdiv_q_2exp(h,h,k+1);
      mpz_mul(h,h,N); mpz_sub(res,a,h);
      if (mpz_sizeinbase(res,2)>k+1) 
       { mpz_mod(res,res,N); cerr << endl << "moderror!" << endl; }
    }
};

---