Baby-step Giant-step

概要

離散対数問題(Discrete Logarithm Problem)を解くアルゴリズム。

ある \(X, Y, M\) について \(X^K \equiv Y\) (mod \(M\)) となる \(K\) を求める。

具体的計算

1. Baby-step

\(m = \lceil \sqrt{M} \rceil\) とし、 \(X^0, X^1, ..., X^{m-1}\) を求めておく。

2. Giant-step

\(R = X^{-m}\) を計算し、 \(a = 0\) から \(Y \times R^a \equiv X^b\) (mod \(M\)) となる \(0 \le b \le m-1\) が見つかるまで計算する。 (この計算は高々 \(O(m)\) 回)

\(K = ma + b\) を解として出力する。

計算量

\(O(\sqrt{M})\)

実装

# X^K ≡ Y (mod M) となるような K を求める
def solve(X, Y, M):
    D = {1: 0}

    sq = int(M**.5)+1

    # Baby-step
    Z = 1
    for i in range(sq):
        Z = Z * X % M
        D[Z] = i+1

    if Y in D:
        return D[Y]

    # Giant-step
    R = pow(Z, M-2, M) # R = X^(-sq)

    for i in range(1, sq+1):
        Y = Y * R % M
        if Y in D:
            return D[Y] + i*sq
    return -1

X = 3; Y = 193; MOD = 10**9 + 7
r = solve(X, Y, MOD)
assert pow(X, r, MOD) == Y, (pow(X, r, MOD), Y)

参考

戻る