離散対数 (src/Math/DiscreteLogarithm.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2023-10-29 17:46:55+09:00
Include: #include "src/Math/DiscreteLogarithm.hpp"

半群 $E$ が集合 $T$ に左作用するとする.
[入力] $x\in E$, $s,t\in T$, $n\in \mathbb{N}$
[出力] $0 \le i < n$ かつ $x^is=t$ を満たす非負整数 $i$ ( 存在しないなら $-1$ ) :

メンバ関数

名前	概要	計算量
`DiscreteLogarithm(mp,op,hash,lim)`	コンストラクタ. `mp` : $ E \times T \rightarrow T$ ( 作用 ) `op` : $E \times E \rightarrow E$ ( 半群 $E$ の二項演算 ) `hash` : $T \rightarrow \mathbb{N}$ ( int に変換 )
`operator()(x,s,t,n)`	$0 \le i < n$ かつ $x^is=t$ を満たす非負整数 $i$ を返す. 存在しないなら $-1$ を返す.	作用, 二項演算の計算量がそれぞれ $O(A), O(B)$ のとき $O(A\sqrt{n}+B\log{n})$

参考

https://maspypy.com/モノイド作用に関する離散対数問題

Depends on

関数型や関数オブジェクトに関するテンプレート (src/Internal/function_traits.hpp)

Verified with

Code

#pragma once
#include <cmath>
#include <vector>
#include "src/Internal/function_traits.hpp"
// mp : E × T -> T
// op : E × E -> E
// hash : T -> int
// s,t ∈ T, x ∈ E
// return min{ i : x^i(s) = t and i ∈ [0,N) } or -1 (not found)
template <class F, class G, class H> class DiscreteLogarithm {
 const F &mp;
 const G &op;
 const H &hash;
 const int64_t lim;
 using T= result_type_t<F>;
 using E= result_type_t<G>;
public:
 DiscreteLogarithm(const F &mp, const G &op, const H &hash, int64_t lim= 1ll << 50): mp(mp), op(op), hash(hash), lim(lim) { static_assert(std::is_convertible_v<std::invoke_result_t<H, T>, int>); }
 int64_t operator()(const E &x, T s, const T &t, int64_t N= -1) const {
  if (N < 0) N= lim;
  const int m= 1 << std::__lg(int(std::sqrt(N) + 1)), mask= m - 1;
  std::vector<T> val(m), vs(m);
  std::vector<int> os(m + 1), so(m);
  T s1= t;
  for (int i= 0; i < m; ++i) ++os[so[i]= hash(val[i]= s1= mp(x, s1)) & mask];
  for (int i= 0; i < m; ++i) os[i + 1]+= os[i];
  for (int i= 0; i < m; ++i) vs[--os[so[i]]]= val[i];
  E y= x;
  for (int k= m; k>>= 1;) y= op(y, y);
  bool failed= false;
  for (int64_t n= 0;; s= s1) {
   for (int a= hash(s1= mp(y, s)) & mask, j= os[a]; j < os[a + 1]; ++j) {
    if (s1 == vs[j]) {
     for (int i= 0;; s= mp(x, s)) {
      if (s == t) return n + i < N ? n + i : -1;
      if (++i == m) break;
     }
     if (failed) return -1;
     failed= true;
     break;
    }
   }
   if ((n+= m) >= N) break;
  }
  return -1;
 }
};

#line 2 "src/Math/DiscreteLogarithm.hpp"
#include <cmath>
#include <vector>
#line 2 "src/Internal/function_traits.hpp"
#include <type_traits>
// clang-format off
namespace function_template_internal{
template<class C>struct is_function_object{
 template<class U,int dummy=(&U::operator(),0)> static std::true_type check(U *);
 static std::false_type check(...);
 static C *m;
 static constexpr bool value= decltype(check(m))::value;
};
template<class F,bool,bool>struct function_type_impl{using type= void;};
template<class F>struct function_type_impl<F,true,false>{using type= F *;};
template<class F>struct function_type_impl<F,false,true>{using type= decltype(&F::operator());};
template<class F> using function_type_t= typename function_type_impl<F,std::is_function_v<F>,is_function_object<F>::value>::type;
template<class... Args>struct result_type_impl{using type= void;};
template<class R,class... Args>struct result_type_impl<R(*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)const>{using type= R;};
template<class F> using result_type_t= typename result_type_impl<function_type_t<F>>::type;
template<class... Args>struct argument_type_impl{using type= void;};
template<class R,class... Args>struct argument_type_impl<R(*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)const>{using type= std::tuple<Args...>;};
template<class F> using argument_type_t= typename argument_type_impl<function_type_t<F>>::type;
}
using function_template_internal::result_type_t,function_template_internal::argument_type_t;
// clang-format on
#line 5 "src/Math/DiscreteLogarithm.hpp"
// mp : E × T -> T
// op : E × E -> E
// hash : T -> int
// s,t ∈ T, x ∈ E
// return min{ i : x^i(s) = t and i ∈ [0,N) } or -1 (not found)
template <class F, class G, class H> class DiscreteLogarithm {
 const F &mp;
 const G &op;
 const H &hash;
 const int64_t lim;
 using T= result_type_t<F>;
 using E= result_type_t<G>;
public:
 DiscreteLogarithm(const F &mp, const G &op, const H &hash, int64_t lim= 1ll << 50): mp(mp), op(op), hash(hash), lim(lim) { static_assert(std::is_convertible_v<std::invoke_result_t<H, T>, int>); }
 int64_t operator()(const E &x, T s, const T &t, int64_t N= -1) const {
  if (N < 0) N= lim;
  const int m= 1 << std::__lg(int(std::sqrt(N) + 1)), mask= m - 1;
  std::vector<T> val(m), vs(m);
  std::vector<int> os(m + 1), so(m);
  T s1= t;
  for (int i= 0; i < m; ++i) ++os[so[i]= hash(val[i]= s1= mp(x, s1)) & mask];
  for (int i= 0; i < m; ++i) os[i + 1]+= os[i];
  for (int i= 0; i < m; ++i) vs[--os[so[i]]]= val[i];
  E y= x;
  for (int k= m; k>>= 1;) y= op(y, y);
  bool failed= false;
  for (int64_t n= 0;; s= s1) {
   for (int a= hash(s1= mp(y, s)) & mask, j= os[a]; j < os[a + 1]; ++j) {
    if (s1 == vs[j]) {
     for (int i= 0;; s= mp(x, s)) {
      if (s == t) return n + i < N ? n + i : -1;
      if (++i == m) break;
     }
     if (failed) return -1;
     failed= true;
     break;
    }
   }
   if ((n+= m) >= N) break;
  }
  return -1;
 }
};