離散対数問題(モノイド)
(Src/Algebra/Monoid/MonoidDiscreteLogarithm.hpp)

• View this file on GitHub
• Last update: 2025-08-21 17:55:17+09:00
• Include: #include "Src/Algebra/Monoid/MonoidDiscreteLogarithm.hpp"

概要

モノイド $(X, \oplus)$ と集合 $S$ に対して関数 $f : X\times S\rightarrow S$ が定義されているとする。

$x \in S, s, t \in S$ に対して $f(x^{n}, s) = t$ を満たす最小の $n$ を計算する。それが入力で与えられる正整数 $N$ 以上である、または存在しないならばstd::nulloptを返す。

ライブラリの使い方

template <class X, class S, class H>
std::optional<usize> MonoidDiscreteLogarithm(typename X::Element x, S s, S t, usize N)  (1)

template <class X, class S>
std::optional<usize> MonoidDiscreteLogarithm(X x, S s, S t, usize N) (2)

(1) Xはconcepts::Monoidを満たす必要がある。 Xに対してS action(X, S)が定義されている必要がある。HはSの要素のハッシュを取る関数オブジェクトである必要がある。

$S$ に対してstd::hashが定義されているならば(2)を用いることができる((2)は未verify…)

例えば、通常の離散対数問題( $x^{n} \equiv y\pmod{M}$ なる最小の $n$ を見つける)ときは以下のようにする。

using S = mint;
struct X {
    using Element = mint;
    static Element identity() {
        return mint{1};
    }
    static Element operation(Element L, Element R) {
        return L * R;
    }
    static Element action(Element x, S s) {
        return x * s;
    }
};
struct Hasher {
    size_t operator()(const S& v) const {
        return v.val();
    }
};
int main() {
    auto ans = MonoidDiscreteLogarithm<M, mint, Hasher>(mint{x}, mint{1}, mint{y}, M);
}

計算量

• X::identity()を高々 $2$ 回呼び出す
• X::operation()を高々 $4\lfloor \sqrt{N}\rfloor + O(1)$ 回呼び出す
• X::action()を高々 $3\lfloor\sqrt{N}\rfloor + O(1)$ 回呼び出す
• std::unordered<S>に高々 $\lfloor\sqrt{N}\rfloor$ 要素挿入され、高々 $\lfloor\sqrt{N}\rfloor + O(1)$ 回検索を行う

参考

• モノイド作用に関する離散対数問題

メモ

逆元が定義できるなら、最初に $x^{km}s\in T$ を発見して、あとは逆元かけながら高々 $m$ ステップ戻る… みたいにすると早くなるかも？

変更履歴

2025/8/21 作成

Depends on

• Src/Algebra/Action/ActionConcept.hpp
• Src/Algebra/Monoid/MonoidConcept.hpp
• Src/Algebra/Semigroup/SemigroupConcept.hpp
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/AtCoder/abc222_g.test.cpp
• Test/AtCoder/abc270_g.test.cpp
• Test/LC/discrete_logarithm_mod.test.cpp

Code

#pragma once

#include "./MonoidConcept.hpp"
#include "../Action/ActionConcept.hpp"
#include "../../Template/TypeAlias.hpp"

#include <algorithm>
#include <cassert>
#include <concepts>
#include <cmath>
#include <functional>
#include <optional>
#include <unordered_set>

namespace zawa {

namespace discretelog_internal {

using namespace concepts;

template <class X, class S>
concept Condition = Monoid<X> and Action<X, S>;

template <class F, class S>
concept Hasher = std::is_invocable_r_v<usize, F, S>;

template <class S>
concept STDHashable = requires (S s) {
    { std::hash<S>{}(s) } -> std::convertible_to<usize>;
};

} // namespace discretelog_internal

template <class X, class S, class H>
requires discretelog_internal::Condition<X, S> and discretelog_internal::Hasher<H, S>
std::optional<usize> MonoidDiscreteLogarithm(typename X::Element x, S s, S t, usize N) {
    assert(N);
    if (s == t)
        return 0;
    using XE = typename X::Element;
    using Hashset = std::unordered_set<S, H>;
    const usize m = std::max<usize>(1, sqrtl(N));
    Hashset T;
    T.reserve(m);
    const XE xm = [&]() {
        XE xi = X::identity();
        for (usize i = 0 ; i < m ; i++)
            T.insert(X::action(xi = X::operation(xi, x), t));
        return xi;
    }();
    XE prv = X::identity();
    for (usize k = 1, fail = 0 ; (k - 1) * m <= N and fail < 2 ; k++) {
        XE cur = X::operation(prv, xm);
        const S val = X::action(cur, s);
        if (T.contains(val)) {
            for (auto [i, xi] = std::pair<usize, XE>(0, prv) ; i < m ; i++, xi = X::operation(xi, x)) {
                if (X::action(xi, s) == t) {
                    const usize res = (k - 1) * m + i;
                    return res < N ? std::optional<usize>{res} : std::nullopt;
                }
            } 
            fail++;
        }
        prv = std::move(cur);
    }
    return std::nullopt;
}

template <class X, class S>
requires discretelog_internal::Condition<X, S> and discretelog_internal::STDHashable<S>
std::optional<usize> MonoidDiscreteLogarithm(typename X::Element x, S s, S t, usize N) {
    return MonoidDiscreteLogarithm<X, S, std::hash<S>>(x, s, t, N); 
}

} // namespace zawa

#line 2 "Src/Algebra/Monoid/MonoidDiscreteLogarithm.hpp"

#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 2 "Src/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

} // namespace zawa
#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 2 "Src/Algebra/Action/ActionConcept.hpp"

#line 4 "Src/Algebra/Action/ActionConcept.hpp"

namespace zawa {

namespace concepts {

template <class G, class X>
concept Action = requires {
    typename G::Element;
    { G::action(std::declval<typename G::Element>(), std::declval<X>()) } -> std::same_as<X>;
};

// Is appropriate name X-set?
template <class G, class X>
concept Acted = requires {
    typename G::Element;
    { G::acted(std::declval<typename G::Element>(), std::declval<X>()) } -> std::same_as<typename G::Element>;
};

} // namespace concepts

} // namespace zawa
#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 6 "Src/Algebra/Monoid/MonoidDiscreteLogarithm.hpp"

#include <algorithm>
#include <cassert>
#line 10 "Src/Algebra/Monoid/MonoidDiscreteLogarithm.hpp"
#include <cmath>
#include <functional>
#include <optional>
#include <unordered_set>

namespace zawa {

namespace discretelog_internal {

using namespace concepts;

template <class X, class S>
concept Condition = Monoid<X> and Action<X, S>;

template <class F, class S>
concept Hasher = std::is_invocable_r_v<usize, F, S>;

template <class S>
concept STDHashable = requires (S s) {
    { std::hash<S>{}(s) } -> std::convertible_to<usize>;
};

} // namespace discretelog_internal

template <class X, class S, class H>
requires discretelog_internal::Condition<X, S> and discretelog_internal::Hasher<H, S>
std::optional<usize> MonoidDiscreteLogarithm(typename X::Element x, S s, S t, usize N) {
    assert(N);
    if (s == t)
        return 0;
    using XE = typename X::Element;
    using Hashset = std::unordered_set<S, H>;
    const usize m = std::max<usize>(1, sqrtl(N));
    Hashset T;
    T.reserve(m);
    const XE xm = [&]() {
        XE xi = X::identity();
        for (usize i = 0 ; i < m ; i++)
            T.insert(X::action(xi = X::operation(xi, x), t));
        return xi;
    }();
    XE prv = X::identity();
    for (usize k = 1, fail = 0 ; (k - 1) * m <= N and fail < 2 ; k++) {
        XE cur = X::operation(prv, xm);
        const S val = X::action(cur, s);
        if (T.contains(val)) {
            for (auto [i, xi] = std::pair<usize, XE>(0, prv) ; i < m ; i++, xi = X::operation(xi, x)) {
                if (X::action(xi, s) == t) {
                    const usize res = (k - 1) * m + i;
                    return res < N ? std::optional<usize>{res} : std::nullopt;
                }
            } 
            fail++;
        }
        prv = std::move(cur);
    }
    return std::nullopt;
}

template <class X, class S>
requires discretelog_internal::Condition<X, S> and discretelog_internal::STDHashable<S>
std::optional<usize> MonoidDiscreteLogarithm(typename X::Element x, S s, S t, usize N) {
    return MonoidDiscreteLogarithm<X, S, std::hash<S>>(x, s, t, N); 
}

} // namespace zawa

Back to top page