離散対数 (Baby-step giant-step)
(NumberTheory/ModularArithmetic/baby_step_giant_step.py)

• View this file on GitHub
• Last update: 2021-03-07 00:19:35+09:00

概要

整数 $x, y, m$ が与えられたとき $x^k \equiv y \pmod{m}$ を満たす $k$ を求めるアルゴリズム。

使い方

baby_step_giant_step(x: int, y: int, MOD: int) -> int
MOD 上で $x^k \equiv y$ を満たす $k$ を返す。そのような $k$ が存在しない場合は -1 を返す。計算量 $O(\sqrt {\mathrm{MOD}})$

Verified with

• TestCase/LibraryChecker/discrete_logarithm_mod.test.py

Code

def baby_step_giant_step(x, y, MOD):
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    x %= MOD
    y %= MOD
    k, add, g = 1, 0, gcd(x, MOD)
    while g > 1:
        if y == k:
            return add
        if y % g:
            return -1
        y //= g
        MOD //= g
        add += 1
        k = (k * x // g) % MOD
        g = gcd(x, MOD)

    sqrtMOD = int(MOD ** 0.5) + 1
    baby = {}
    cur = y
    for i in range(sqrtMOD + 1):
        baby[cur] = i
        cur = (cur * x) % MOD

    xpow = pow(x, sqrtMOD, MOD)
    cur = k
    for i in range(1, sqrtMOD + 1):
        cur = (cur * xpow) % MOD
        if cur in baby:
            return sqrtMOD * i - baby[cur] + add

    return -1

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page