Day 030-Q5 — 競技数学：原始根・離散対数・位数計算

2026-05-13 赤色 Master / Phase 8+ ★★★★★★★★★ BSGS・整数論

問題

奇素数 $p$ について、原始根判定 / 離散対数 / 位数計算の3種クエリに答えよ。

制約

$3 \le p \le 10^9$
$Q \le 10^5$
$1 \le g, a, b < p$

入出力例

入力例 1

7 4
1 3
2 3 5
3 2
1 2

出力例 1

Yes
5
3
No

ヒント (段階的開示)

ヒント1: 方向性
原始根判定は位数 = $p-1$ チェック。離散対数は BSGS で $O(\sqrt{p})$。位数は $p-1$ の素因数分解 + 試し。
ヒント2: アプローチ
$\mathrm{ord}_p(a)$ は $p-1$ の約数。$p-1$ の各素因数 $q$ で割り続けて確認。
ヒント3: BSGS
$a^x = b$ を $a^{im} = b a^{-j}$ と分解、$m = \lceil\sqrt{p}\rceil$。

模範解答 (Python)

import sys
from math import isqrt
input = sys.stdin.readline

def factorize(n):
    factors = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

def multiplicative_order(a, p, factors_pm1):
    ord_val = p - 1
    for q in factors_pm1:
        while ord_val % q == 0 and pow(a, ord_val // q, p) == 1:
            ord_val //= q
    return ord_val

def bsgs(a, b, p):
    if b == 1:
        return 0
    m = isqrt(p - 1) + 1
    table = {}
    aj = 1
    for j in range(m):
        if aj not in table:
            table[aj] = j
        aj = aj * a % p
    am_inv = pow(pow(a, m, p), p - 2, p)
    cur = b
    for i in range(m + 1):
        if cur in table:
            x = i * m + table[cur]
            return x
        cur = cur * am_inv % p
    return -1

def solve():
    line = input().split()
    p, Q = int(line[0]), int(line[1])
    factors_pm1 = factorize(p - 1)
    results = []
    for _ in range(Q):
        query = list(map(int, input().split()))
        qtype = query[0]
        if qtype == 1:
            g = query[1]
            if g % p == 0:
                results.append("No"); continue
            ord_g = multiplicative_order(g, p, factors_pm1)
            results.append("Yes" if ord_g == p - 1 else "No")
        elif qtype == 2:
            a, b = query[1], query[2]
            x = bsgs(a, b, p)
            results.append(str(x))
        elif qtype == 3:
            a = query[1]
            if a % p == 0:
                results.append("0"); continue
            ord_a = multiplicative_order(a, p, factors_pm1)
            results.append(str(ord_a))
    print('\n'.join(results))

solve()

Step-by-Step 解説

1$p-1$ の素因数分解
$\sqrt{p}$ までの試し割り。
2位数計算
各素因数 $q$ で ord_val // q 乗が 1 の間は割り続ける。
3原始根判定
$\mathrm{ord}_p(g) = p - 1$ なら原始根。
4BSGS
baby step: $a^j$ をハッシュテーブル。giant step: $b \cdot (a^{-m})^i$ を検索。
5クエリ処理
$p-1$ の素因数分解は一度だけ。

よくあるミス

ミス原因正しい書き方
BSGS で x=0 見落としb=1 のケース先頭で if b==1: return 0
位数で素因数の指数を無視$q^2$ で割れる場合while ord_val % q == 0 ループ
逆元計算忘れ$a^{-m}$ が必要pow(pow(a,m,p), p-2, p)
BSGS の m が小さい解見落としm = isqrt(p-1) + 1

次のステップ

  • Pohlig-Hellman アルゴリズム
  • 楕円曲線上の離散対数（ECDLP）

自己評価

自分の回答

気づき・メモ