mod_add

uint64_t mod_add(uint64_t a, uint64_t b, uint64_t m)
{
    // a, b가 m보다 작다고 가정
    a %= m; 
    b %= m;
    return (a >= m - b) ? (a - (m - b)) : (a + b);
}

a + b ≧ m の 場合 a - (m - b) を行い、そうでない場合 a ≧ m-b で検査を行う理由は、オーバーフローを防ぐためである。

mod_sub

uint64_t mod_sub(uint64_t a, uint64_t b, uint64_t m)
{
    // a, b가 m보다 작다고 가정
    a %= m; 
    b %= m;
    return (a < b) ? (a - b + m) : (a - b);
}

a < b であれば結果が負数になるので、結果が負数にならないようにするために m を加える。 mod m では m は 0 と同じであるため結果には影響がない。

mod_mul

uint64_t mod_mul(uint64_t a, uint64_t b, uint64_t m)
{
    uint64_t res = 0;
    while (b > 0) {
        if (b & 1)
            res = mod_add(res, a, m);
        b = b >> 1;
        a = mod_add(a, a, m);
    }
    return res;
}

a*b 演算時にオーバーフロー防止のためにdouble addtion アルゴリズムを適用して素早く計算する。

mod_pow

uint64_t mod_pow(uint64_t a, uint64_t b, uint64_t m)
{
    uint64_t res = 1;
    while (b > 0) {
        if (b & 1)
            res = mod_mul(res, a, m);
        b = b >> 1;
        a = mod_mul(a, a, m);
    }
    return res;
}

a^b でオーバーフローが発生するのを防ぐためにsquaremultiplicationアルゴリズムを使用する。