Day 148-Q4 | Pollard's p-1法

問題

合成数$N$、境界値$B$、底$a$が与えられる。以下の手順でPollard's p-1法を実行し、見つかった非自明な約数を出力せよ（見つからなければ$-1$）。

$B$以下の各素数$q$について$q^k\le B$を満たす最大の$k$を求め、$M=\prod q^k$を計算する（$\mathrm{lcm}(1,\dots,B)$に等しい）。
$x=a^M\bmod N$を計算する。
$g=\gcd(x-1,N)$を計算する。
$1<g<N$なら$g$を出力、そうでなければ$-1$を出力。

入力形式

N B a

制約

$N$は異なる2素数の積（$100\le N\le10^6$）

$2 \le B \le 50$

$2 \le a < N$, $\gcd(a,N)=1$

入出力例

入力例1

15251 10 2

出力例1

入力例2

15251 3 2

出力例2

-1

$N=15251=101\times151$。$B=10$では151の発見に成功するが$B=3$では指数$M$が小さすぎて失敗する。

概念図：$M$が$p-1$を割り切るかどうかで成否が決まる

ヒント（段階的開示）

ヒント1（方向性）

Pollard's rhoが乱択的な衝突狙いなのに対し、p-1法は「$p-1$が小さな素因数だけでできているなら必ず捕まえられる」決定的な狙い撃ちである。まず指数$M$の作り方を正確に実装する。

ヒント2（アプローチ）

$M=\mathrm{lcm}(1,\dots,B)$は各素数$q\le B$について$q^k\le B$となる最大の$k$を求め掛け合わせる。フェルマーの小定理より$p-1\mid M$なら$a^M\equiv1\pmod p$。

ヒント3（誘導）

def compute_M(B):
    M = 1
    for q in range(2, B + 1):
        if is_prime(q):
            qk = q
            while qk * q <= B:
                qk *= q
            M *= qk
    return M

def pollard_p_minus_1(N, B, a):
    import math
    M = compute_M(B)
    x = pow(a, M, N)
    g = math.gcd(x - 1, N)
    return g if 1 < g < N else -1

模範解答 (Python)

import sys
import math

def is_prime(n):
    if n < 2:
        return False
    for d in range(2, int(n ** 0.5) + 1):
        if n % d == 0:
            return False
    return True


def compute_M(B):
    M = 1
    for q in range(2, B + 1):
        if is_prime(q):
            qk = q
            while qk * q <= B:
                qk *= q
            M *= qk
    return M


def pollard_p_minus_1(N, B, a):
    M = compute_M(B)
    x = pow(a, M, N)
    g = math.gcd(x - 1, N)
    if 1 < g < N:
        return g
    return -1


def main():
    N, B, a = map(int, sys.stdin.readline().split())
    print(pollard_p_minus_1(N, B, a))


main()

Step-by-Step 解説

1指数$M$の構成が本手法の心臓部
$M=\mathrm{lcm}(1,\dots,B)$を「$B$以下の素数のべき乗の積」として構成することで、$p-1$がどんな重複した素因数を持っていても$p-1\mid M$を保証しやすくする。

2フェルマーの小定理からの帰結
$p-1\mid M$なら$a^M\equiv(a^{p-1})^{M/(p-1)}\equiv1\pmod p$。よって$p\mid(a^M-1)$が成り立つ。

3滑らかさは十分条件であって必要条件ではない
$q-1$が$B$-滑らかでなくても、$a$の位数がたまたま$M$を割り切れば成功することがある。入力例1はこのケース。

4$B$が小さいと失敗する理由
$M$が小さすぎると両方の素因数側で$a^M\equiv1$が成立せず$\gcd(x-1,N)=1$になる。$B$を段階的に増やす探索戦略が実務的な使い方。

よくあるミス

ミス	原因	正しい書き方
$M$を単純な積にしてしまう	同じ素因数を重複してべき乗しすぎ、または不足する	素数ごとに「$B$以下で最大のべき乗」だけを1回掛ける
$\gcd(x,N)$を計算してしまう	保証されるのは$a^M\equiv1$（$x=1$）であることを見落とす	必ず`x-1`との$\gcd$を取る
$g=N$を成功と誤判定	$p,q$両方が同時に割り切れると$g=N$になる	`1 < g < N`を厳密にチェックする
$B$を大きくすれば必ず見つかると誤解	$q-1$が大きな素因数しか持たない場合は原理的に困難	この手法は限定的であり失敗時は別手法の併用が必要と理解する
`a**M % N`と書いてしまう	$M$が大きいと多倍長の巨大な数を経由し極端に遅い	3引数`pow(a, M, N)`を使う

次のステップ

発展: $B$を少しずつ増やしながら繰り返し適用する「境界値探索付きp-1法」を実装し、必要な試行回数を実測せよ。
次回予告: Weak Heap（簡略版・1回の比較だけで親子関係を決定する非対称マージ規則）

自己評価

完全理解おおむね理解要復習

Day 148-Q4 — Pollard's p-1法（整数分解・素因数の"滑らかさ"を突く決定的手法）

問題