src/math/modular-arithmetic/mod-log.hpp

• View this file on GitHub
• Last update: 2023-07-06 05:03:35+09:00
• Include: #include "src/math/modular-arithmetic/mod-log.hpp"

Depends on

• src/cpp-template/header/int-alias.hpp

Code

#pragma once

#include <numeric>
#include <map>

#include "src/cpp-template/header/int-alias.hpp"

namespace luz {

  // calculate minimum x s.t. a^{x} = b (mod p),
  //   return -1 if answer is not exists.
  i64 mod_log(i64 a, i64 b, i64 p) {
    i64 g = 1;
    for (i64 i = p; i; i /= 2) (g *= a) %= p;
    g = std::gcd(g, p);

    i64 t = 1, c = 0;
    while (t % g) {
      if (t == b) return c;
      (t *= a) %= p;
      c++;
    }
    if (b % g) return -1;

    t /= g;
    b /= g;
    i64 n = p / g, h = 0, gs = 1;
    while (h * h < n) {
      (gs *= a) %= n;
      h++;
    }

    std::unordered_map< i64, i64 > bs;
    for (i64 s = 0, e = b; s < h; bs[e] = ++s) {
      (e *= a) %= n;
    }

    for (i64 s = 0, e = t; s < n;) {
      (e *= gs) %= n;
      s += h;
      if (bs.count(e)) return c + s - bs[e];
    }
    return -1;
  }

}

#line 2 "src/math/modular-arithmetic/mod-log.hpp"

#include <numeric>
#include <map>

#line 2 "src/cpp-template/header/int-alias.hpp"

#include <cstdint>

namespace luz {

  using i32 = std::int32_t;
  using i64 = std::int64_t;
  using u32 = std::uint32_t;
  using u64 = std::uint64_t;

}
#line 7 "src/math/modular-arithmetic/mod-log.hpp"

namespace luz {

  // calculate minimum x s.t. a^{x} = b (mod p),
  //   return -1 if answer is not exists.
  i64 mod_log(i64 a, i64 b, i64 p) {
    i64 g = 1;
    for (i64 i = p; i; i /= 2) (g *= a) %= p;
    g = std::gcd(g, p);

    i64 t = 1, c = 0;
    while (t % g) {
      if (t == b) return c;
      (t *= a) %= p;
      c++;
    }
    if (b % g) return -1;

    t /= g;
    b /= g;
    i64 n = p / g, h = 0, gs = 1;
    while (h * h < n) {
      (gs *= a) %= n;
      h++;
    }

    std::unordered_map< i64, i64 > bs;
    for (i64 s = 0, e = b; s < h; bs[e] = ++s) {
      (e *= a) %= n;
    }

    for (i64 s = 0, e = t; s < n;) {
      (e *= gs) %= n;
      s += h;
      if (bs.count(e)) return c + s - bs[e];
    }
    return -1;
  }

}

Back to top page