Day 017-Q3 | Miller-Rabin + Pollard's Rho

問題

$T$ 個の整数 $N_i$ が与えられる。各 $N_i$ について最大素因数を答えよ。

入力形式

T
N_1
N_2
...
N_T

制約

$1 \le T \le 100$

$1 \le N_i \le 10^{18}$

入出力例

入力例 1

出力例 1

3
1000000007
998244353

12 = 2²×3 → 最大素因数3、1000000007は素数、998244353は素数

入力例 2

2
600851475143
9999999999999937

出力例 2

6857
9999999999999937

600851475143 = 71×839×1471×6857

ヒント (段階的開示)

ヒント1: 方向性

$N \le 10^{18}$ なので試し割りは不可能（$\sqrt{10^{18}} = 10^9$）。確率的アルゴリズムを使う必要がある。

ヒント2: アプローチ

Miller-Rabin素数判定: $O(\log^2 N)$ で高確率（決定的）に素数判定。Pollard's Rho: $O(N^{1/4} \log N)$ で因数を1つ見つける。組み合わせて完全素因数分解を $O(N^{1/4} \log N \cdot \log N)$ で実現。

ヒント3: 誘導

from math import gcd
import random

def miller_rabin(n, witnesses=None):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n % 2 == 0: return False

    # n-1 = 2^r * d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1; d //= 2

    if witnesses is None:
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

    for a in witnesses:
        if a >= n: continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1: continue
        for _ in range(r - 1):
            x = x * x % n
            if x == n - 1: break
        else:
            return False
    return True

模範解答 (Python)

import sys
from math import gcd, isqrt
import random

def miller_rabin(n):
    if n < 2: return False
    if n in (2, 3, 5, 7): return True
    if n % 2 == 0: return False

    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1; d //= 2

    # n < 3,317,044,064,679,887,385,961,981 まで決定的
    for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if a >= n: continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1: continue
        for _ in range(r - 1):
            x = x * x % n
            if x == n - 1: break
        else:
            return False
    return True

def pollard_rho(n):
    if n % 2 == 0: return 2

    while True:
        x = random.randint(2, n - 1)
        y = x
        c = random.randint(1, n - 1)
        d = 1

        while d == 1:
            x = (x * x + c) % n
            y = (y * y + c) % n
            y = (y * y + c) % n
            d = gcd(abs(x - y), n)

        if d != n:
            return d

def factorize(n):
    if n <= 1: return []
    if miller_rabin(n): return [n]

    # 小さい因数は試し割り
    for p in [2, 3, 5, 7, 11, 13]:
        if n % p == 0:
            res = []
            while n % p == 0:
                res.append(p)
                n //= p
            return res + factorize(n)

    # Pollard's Rho で因数を1つ見つける
    d = n
    while d == n:
        d = pollard_rho(n)

    return factorize(d) + factorize(n // d)

def solve():
    T = int(input())
    for _ in range(T):
        n = int(input())
        if n == 1:
            print(1)
            continue
        factors = factorize(n)
        print(max(factors))

solve()

Step-by-Step 解説

1Miller-Rabin の原理
フェルマーの小定理の強化版。$n-1 = 2^r \cdot d$ と表し、ランダムな $a$ について $a^d \equiv 1 \pmod{n}$ または $a^{2^j d} \equiv -1 \pmod{n}$ が成立しない $a$ が存在すれば合成数。決定的な証人集合 $\{2,3,5,\ldots,37\}$ で $n < 3.3 \times 10^{24}$ まで完全に正確。

2Pollard's Rho の原理
擬似乱数列 $x_{i+1} = x_i^2 + c \pmod{n}$ を生成。Floyd の循環検出で $\gcd(|x_i - x_j|, n) > 1$ となる組を発見。誕生日のパラドックスから、期待ステップ数は $O(N^{1/4})$。

3完全素因数分解
再帰的に: (1) $n = 1$ なら終了、(2) Miller-Rabin で素数なら $[n]$ を返す、(3) Pollard's Rho で因数 $d$ を見つけ、$\text{factorize}(d) + \text{factorize}(n/d)$。

4最大素因数の取得
factorize(n) の結果リストの max をとるだけ。

よくあるミス

ミス	原因	正しい書き方
Pollard's Rho が無限ループ	c の選択が悪い（c=0 や c=n-2）	ループを `while True` にして再試行
d == n のとき再試行しない	因数が見つからなかったケース	`while d == n: d = pollard_rho(n)`
オーバーフロー (C++)	$x \times x$ が 128bit 超え	Python は任意精度なので不問

次のステップ

発展問題: N個の整数の最大公約数の素因数分解（複数同時処理）
応用: 離散対数問題での使用（BSGS + Pollard's Rho）

自己評価

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

Day 017-Q3 — Miller-Rabin素数判定 + Pollard's Rho素因数分解

問題