mod.cpp

Ugrás a fájl dokumentációjához.

#include "mod.h"
#include "gcdx.h"
 
namespace bme {
 
    int Mod::default_modulus = INITIAL_DEFAULT_MODULUS;
    int Mod::print_mode = INITIAL_PRINT_MODE;
 
    Mod Mod::add(const Mod& other)const {
        if (is_invalid() || other.is_invalid() || mod != other.mod) {
            return Mod(0, 0);
        }
        return Mod(val + other.val, mod);
    }
 
    Mod Mod::multiply(const Mod& other)const {
        if (is_invalid() || other.is_invalid() || mod != other.mod) {
            return Mod(0, 0);
        }
        return Mod(val * other.val, mod);
 
    }
 
    Mod Mod::inverse()const {
        if (is_invalid()) { return Mod(0, 0); }
        int a, b;
        int d = gcdx(val, mod, a, b);
        if (d > 1) {
            return Mod(0, 0);    //csak a modulushoz relatív prím elemekre számolható inverz
        }
 
        return Mod(a, mod);
    }
 
    Mod Mod::pow(int k)const {
        if (is_invalid()) { return Mod(0, 0); }
        
        //ha negatív a kitevő, akkor az inverzet emeljük (-k)-adik hatványra
        if (k < 0) {
            return inverse().pow(-k);
        }
 
        //ha k=0, akkor az érték 1
        if (k == 0) { return Mod(1, mod); }
 
        //ha k=1, akkor visszaadjuk saját magát
        if (k == 1) { return *this; }
 
        //ha a kitevő páros, akkor val^k=((val^{k/2})^2)
        if (k % 2 == 0) {
            Mod tmp = pow(k / 2);
            return tmp * tmp;
        }
 
        //ha a kitevő páratlan, akkor val^k=((val^{(k-1)/2})^2*val)
        Mod tmp = pow((k - 1) / 2);
        return tmp * tmp * (*this);
 
    }
 
    ostream& operator<<(ostream& os, const Mod& M) {
        if (!M.is_invalid()) {
            if (Mod::get_print_mode() == NORMAL_PRINT_MODE) {
                os << "Mod(" << M.get_val() << "," << M.get_mod() << ")";
            }
            else if (Mod::get_print_mode() == SHORT_PRINT_MODE) {
                os << M.get_val();
            }
        }
        else {
            os << "INVALID";
        }
        return os;
    }
 
}