exBSGS 学习笔记

发布于

概述

exBSGS(扩展大步小步法,ex Baby Step Giant Step)可以在 $\Theta\left(\sqrt p \log p\right)$ 的时间内求解关于 $x$ 的方程 $a^x \equiv b \pmod p$ (不要求 $a$ 与 $p$ 互质)的最小整数解。

前置知识

exBSGS

我们知道,$a^x \equiv b \pmod p$ 可以写成 $a^x + kp = b$。

设 $\gcd\left\{a, p\right\} = d$

根据斐蜀定理,这个式子有解的充要条件是 $d \mid n$,否则直接返回无解
那么上面的式子就是:
$$a^{x - 1} \cdot \frac ad + k \cdot \frac pd = \frac bd$$

此时,让 $x \gets x - 1, p \gets p \cdot d^{-1}, n \gets n \cdot d^{-1}$,递归求解,直到 $a$ 与 $p$ 互质,然后 BSGS 求解。

若此时一共递归 $t$ 次,设 $D$ 为所有 $d$ 的乘积,则原式就是:
$$a^{x - t} \cdot \frac{a^t}D \equiv \frac nD \pmod {\frac pD}$$

注意在跑普通 BSGS 的时候有一个系数 $\dfrac{a^t}D$ 要乘上。

代码

tp BSGS(tp a, tp b, tp p, tp c) {
  tp t = ceil(sqrt(p)), val = 1;
  unordered_map<tp, tp> m;
  b = b % p;
  for (tp i = 0; i < t; ++i) {
    m[b * val % p] = i;
    val = val * a % p;
  }
  a = val;
  if (!a) return b ? -1 : 1;
  for (tp i = 1, val = c; i <= t; ++i) {
    val = val * a % p;
    if (m.count(val)) return i * t - m[val];
  }
  return -1;
}

tp exBSGS(tp a, tp b, tp p) {
  a = a % p; b = b % p;
  if (b == 1 || p == 1) return 0;
  tp t = 0, d, c = 1;
  while ((d = gcd(a, p)) != 1) {
    if (b % d) return -1;
    ++t;
    b /= d; p /= d;
    c = (a / d * c) % p;
    if (c == b) return t;
  }
  tp ans = BSGS(a, b, p, c);
  if (ans == -1) return -1;
  return ans + t;
}

void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
  tp p, a, b;
  while (bin >> a >> p >> b, a | b | p) {
    tp ans = exBSGS(a, b, p);
    if (ans == -1) bin << "No Solution\n";
    else bin << ans << '\n';
  }
}

Barrett 优化的代码:

struct Barrett{typedef unsigned long long ull;typedef __uint128_t LL;ull m,B;Barrett()=default;Barrett(ull m):m(m),B((LL(1)<<64)/m){}friend ull operator%(ull a,const Barrett&mod){ull r=a-mod.m*(LL(mod.B)*a>>64);return r>=mod.m?r-mod.m:r;}};

tp gcd(tp a, tp b) {
  while (b ^= a ^= b ^= a %= b);
  return a;
}

tp BSGS(tp a, tp b, Barrett p, tp c) {
  tp t = ceil(sqrt(p.m)), val = 1;
  unordered_map<tp, tp> m;
  b = b % p;
  for (tp i = 0; i < t; ++i) {
    m[b * val % p] = i;
    val = val * a % p;
  }
  a = val;
  if (!a) return b ? -1 : 1;
  for (tp i = 1, val = c; i <= t; ++i) {
    val = val * a % p;
    if (m.count(val)) return i * t - m[val];
  }
  return -1;
}

tp exBSGS(tp a, tp b, tp p) {
  a = a % p; b = b % p;
  if (b == 1 || p == 1) return 0;
  tp t = 0, d, c = 1;
  while ((d = gcd(a, p)) != 1) {
    if (b % d) return -1;
    ++t;
    b /= d; p /= d;
    c = (a / d * c) % p;
    if (c == b) return t;
  }
  tp ans = BSGS(a, b, p, c);
  if (ans == -1) return -1;
  return ans + t;
}

void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
  tp p, a, b;
  while (bin >> a >> p >> b, a | b | p) {
    tp ans = exBSGS(a, b, p);
    if (ans == -1) bin << "No Solution\n";
    else bin << ans << '\n';
  }
}

暂无评论

发表评论