離散対数 (log mod)
(Math/log_mod.hpp)

• View this file on GitHub
• Last update: 2023-04-05 23:10:22+09:00
• Include: #include "Math/log_mod.hpp"
• Link: https://qiita.com/suisen_cp/items/d597c8ec576ae32ee2d7

概要

離散対数問題
わかりやすさを重視して実装しているので，定数倍が重い．

解説

X^k = Y (mod M)を解く
gcd(X,M) = g = 1 ならX^(-1)が存在するのでBSGS
存在しない場合
X = X’ * g, Y = Y’ * g, M = M’ * g
とする．Yがgの倍数でないなら不可能
元の式を考えると，ある整数nが存在し，(g * X’) ^ k - g * Y’ = n * g * M’
変形, X’ * (g * X’) ^ (k-1) - Y’ = n * M’
これより，X, X’ ^ (-1) * Y’, M’ でまた再帰的に同じ問題を解けばよくなる

Ref

https://qiita.com/suisen_cp/items/d597c8ec576ae32ee2d7

Depends on

• Math/inv_mod.hpp
• Math/pow_mod.hpp

Verified with

• test/yosupo_DiscreteLog.test.cpp

Code

#include "./inv_mod.hpp"
#include "./pow_mod.hpp"

// https://qiita.com/suisen_cp/items/d597c8ec576ae32ee2d7
// 最小の非負整数xを返す
// a ^ x = b mod m
ll log_mod(ll a,ll b,ll m){
    auto BSGS=[](ll a,ll b,ll m){
        ll sq_m=sqrt(m)+1;

        // baby-step
        unordered_map<ll,ll> bs;
        ll bab=1;
        for(int i=0;i<sq_m;i++,bab=bab*a%m)if(!bs.count(bab)) bs[bab]=i;

        // giant-step
        ll a_m=pow_mod(inv_mod(a,m),sq_m,m);
        ll gia=b;
        for(int i=0;i<=sq_m;i++,gia=gia*a_m%m)if(bs.count(gia)) return sq_m*i+bs[gia];
        return -1ll;
    };

    function<ll(ll,ll,ll)> decomp_BSGS=[&decomp_BSGS, &BSGS](ll a,ll b,ll m){
        a%=m,b%=m;
        
        if(m==1) return 0ll;
        if(b==1) return 0ll;

        ll g=gcd(a,m);
        if(g==1) return BSGS(a,b,m);

        if(b%g) return -1ll;
        m/=g;
        b=(b/g)*inv_mod(a/g,m);
        ll res=decomp_BSGS(a,b,m);
        if(res<0) return -1ll;
        return res+1;
    };
    return decomp_BSGS(a,b,m);
}

#line 1 "Math/inv_mod.hpp"
ll inv_mod(ll a,ll m){
    ll b=m,u=1,v=0,t;
    while(b){
        t=a/b;
        swap(a-=t*b,b);swap(u-=t*v,v);
    }
    u%=m;
    if(u<0) u+=m;
    return u;
}
#line 1 "Math/pow_mod.hpp"
// a^n (mod m)
ll pow_mod(ll a,ll n,ll m){
    ll ret=1;
    while(n){
        if(n&1) ret=ret*a%m;
        a=(a*a)%m;
        n/=2;
    }
    return ret;
}
#line 3 "Math/log_mod.hpp"

// https://qiita.com/suisen_cp/items/d597c8ec576ae32ee2d7
// 最小の非負整数xを返す
// a ^ x = b mod m
ll log_mod(ll a,ll b,ll m){
    auto BSGS=[](ll a,ll b,ll m){
        ll sq_m=sqrt(m)+1;

        // baby-step
        unordered_map<ll,ll> bs;
        ll bab=1;
        for(int i=0;i<sq_m;i++,bab=bab*a%m)if(!bs.count(bab)) bs[bab]=i;

        // giant-step
        ll a_m=pow_mod(inv_mod(a,m),sq_m,m);
        ll gia=b;
        for(int i=0;i<=sq_m;i++,gia=gia*a_m%m)if(bs.count(gia)) return sq_m*i+bs[gia];
        return -1ll;
    };

    function<ll(ll,ll,ll)> decomp_BSGS=[&decomp_BSGS, &BSGS](ll a,ll b,ll m){
        a%=m,b%=m;
        
        if(m==1) return 0ll;
        if(b==1) return 0ll;

        ll g=gcd(a,m);
        if(g==1) return BSGS(a,b,m);

        if(b%g) return -1ll;
        m/=g;
        b=(b/g)*inv_mod(a/g,m);
        ll res=decomp_BSGS(a,b,m);
        if(res<0) return -1ll;
        return res+1;
    };
    return decomp_BSGS(a,b,m);
}

Back to top page