多項式因数分解
概要
整数係数多項式 $f \in \mathbb{Z}[x]$ を既約因子の積に分解する操作は、計算機代数の中心的操作のひとつである。 sangi は次の段階構成で実装されている:
- content 抽出 — 係数の GCD を定数因子として分離
- 無平方分解 — Yun のアルゴリズム
- 有限体上の因数分解 — Cantor-Zassenhaus (DDF + EDF)
- Hensel 持ち上げ — $\mathrm{GF}(p)$ から $\mathbb{Z}$ へ
- 因子復元 — Zassenhaus 組合せ または van Hoeij LLL
関連 API: factorize, squareFreeFactorization。
パイプライン全体像
典型的な sangi の factorize(f) 呼び出しは次のように展開される:
$$f = c_0 \cdot \mathrm{prim}(f) \;\to\; \prod_i f_i^{e_i} \;\to\; \prod_{i,j} g_{i,j}$$
ここで $c_0$ は content (全係数の GCD)、$\mathrm{prim}(f)$ は原始部、$f_i^{e_i}$ は Yun 分解の冪因子、$g_{i,j}$ は各 $f_i$ を既約に分解したもの。 最終的に重複度付きで $f = c_0 \prod_{i,j} g_{i,j}^{e_i}$ となる。
Yun の無平方分解 (square-free factorization)
$f = \prod_i f_i^i$ ($f_i$ は無平方かつ互いに素) の形に分解する。 Yun のアルゴリズム (1976) は、素朴な「$\gcd(f, f')$ を取って割る」を効率化したものである。
アルゴリズム
$f$ を $\mathbb{Q}[x]$ または $\mathbb{Z}[x]$ で考え、$\mathrm{char}(K) = 0$ または $\mathrm{char}(K) \nmid \deg f$ を仮定する:
- $g := \gcd(f, f')$, $C_1 := f/g$, $D_1 := f'/g - C_1'$ を計算
- 反復: $a_i := \gcd(C_i, D_i)$, $C_{i+1} := C_i / a_i$, $D_{i+1} := D_i / a_i - C_{i+1}'$
- $f_i = a_i$ を取り出し、$C$ が定数になるまで続ける
計算量: $\gcd$ 計算が支配的で、SR-PRS を使えば $\mathbb{Z}[x]$ で多項式オーダー。
sangi の実装
squareFreeFactorization(f) は Yun を SR-PRS ベースの intPolyGcd 上に実装している。
既約判定はしないので、出力 $f_i$ はさらに次段で既約因子に分解される必要がある。
GF(p) 上での因数分解
無平方 $\mathbb{Z}[x]$ 因子を素数 $p$ で還元すると、$\mathrm{GF}(p)[x]$ 上の無平方多項式になる ($p \nmid \mathrm{disc}(f)$ である限り)。 その既約分解は線形代数 (Berlekamp) または確率的 GCD (Cantor-Zassenhaus) で求まる。
Berlekamp 法 (1967)
Frobenius 写像 $\phi: x \mapsto x^p$ の作用を $\mathbb{F}_p[x]/(f)$ 上で考え、その固有空間 (Berlekamp 部分代数) の基底を線形代数で求める。 基底ベクトル $v(x)$ に対して $\gcd(f, v(x) - c)$ を $c \in \mathrm{GF}(p)$ で走らせれば既約因子が抽出できる。 $p$ が小さいときに有効。
Cantor-Zassenhaus 法 (1981)
2 段階の確率的アルゴリズム:
- DDF (distinct-degree factorization): $\gcd(f, x^{p^d} - x)$ を $d = 1, 2, \ldots$ で計算し、次数 $d$ の既約因子の積をまとめて抽出。
- EDF (equal-degree factorization): 同次数の既約因子の積から、ランダム多項式 $h(x)$ で $\gcd(f, h^{(p^d-1)/2} - 1)$ を取り、確率 $\approx 1/2$ で分裂を起こす。
$p$ が大きいと Berlekamp の線形代数 ($O(n^3)$) より速く、sangi の高速パイプラインで採用されている。
関連記事: 有限体上の因数分解
Hensel 持ち上げ
$\mathrm{GF}(p)$ 上の因数分解 $f \equiv f_1 f_2 \cdots f_r \pmod{p}$ を、係数の精度を二乗的に上げながら $\bmod p^k$ に持ち上げる手法。 $k$ は Mignotte 上界 $\|f\|_\infty \cdot \binom{n}{n/2}$ などから決め、$p^k$ が真の整数因子の係数を一意に決定できるまで上げる。
線形 Hensel (1 因子ペア)
$f \equiv u v \pmod{p^k}$, $\gcd(u, v) = 1$ in $\mathrm{GF}(p)$ なら、$\bmod p^{2k}$ に持ち上げる:
$$U = u + p^k \cdot s, \quad V = v + p^k \cdot t$$
$s, t$ は Bezout 係数から得られる線形補正項。各反復で精度が倍になる ($p^k \to p^{2k}$) ので $\log k$ 反復で目標精度に達する。
多因子 Hensel (binary tree)
$r$ 個の因子を二分木状に組み合わせ、葉から根に向かって 1 ステップずつ持ち上げる。 全体の計算量は $O(M(n p^k) \log r)$ 程度。 sangi の高速パイプラインはこの二分木 Hensel を使う。
関連記事: 整数上の因数分解
Zassenhaus 法 (組合せ復元)
Hensel 持ち上げ後、$f \equiv F_1 F_2 \cdots F_r \pmod{p^k}$ が得られるが、 $\mathbb{Z}[x]$ での真の因子は $F_i$ の積の組合せとして現れる (例えば $\mathbb{Z}[x]$ で既約な因子が $\mathrm{GF}(p)$ で 2 つに分裂しているケース)。 どの組合せが真の因子かを決める問題が残る。
Zassenhaus 法は $2^r$ 通りの部分集合を増加サイズ順に列挙し、各部分集合の積 (mod $p^k$) を正規化して試し割り:
- サイズ 1 の部分集合: $r$ 通り。各 $F_i$ を試し割り。
- サイズ 2: $\binom{r}{2}$ 通り。$F_i F_j$ を試し割り。
- ...サイズ $\lfloor r/2 \rfloor$ まで
$r$ が小さい ($\leq 12$ 程度) なら全列挙が現実的。
sangi の factorize は $r \leq 12$ でこの経路を使う。
van Hoeij LLL 法 (難ケース)
Swinnerton-Dyer 多項式 $\prod (x \pm \sqrt{p_1} \pm \sqrt{p_2} \pm \cdots)$ のような病的ケースでは、 $r$ が次数に比例して大きくなり Zassenhaus の $2^r$ が爆発する。 van Hoeij (2002) はこの選択問題を整数格子の最短ベクトル問題に翻訳することで多項式時間に解いた。
アイデア
Hensel 因子の対数 $\log F_i$ (適切な意味で) を行とする格子を構成し、LLL 基底縮小 (Lenstra-Lenstra-Lovász, 1982) で「短い」基底ベクトルを見つける。 短いベクトルは 0/1 係数の組合せに対応し、真の整数因子の選択を直接与える。
計算量: $O(n^{O(1)})$ — 多項式時間 (LLL の精度パラメータ依存)。
sangi の factorize は $r > 12$ でこの経路に切替える。
LLL の実装は linalg/LLL.hpp に同梱されており、追加リンクは不要である。
factorize API の構成
sangi の factorize(f) は単一のエントリポイントで、入力次数と Hensel 因子数 $r$ に応じて Cantor-Zassenhaus / Hensel 持ち上げ / Zassenhaus 組合せ / van Hoeij LLL を内部で自動切替する。
対応型は int, int64_t, Int, Rational で、追加リンクなしで完全パイプラインが利用できる。
| 段階 | 主な経路 | 備考 |
|---|---|---|
| 小規模 ($\deg \lesssim 10$) | 有理根定理 + 試し割り | 係数が小さい場合の高速経路 |
| $\mathbb{F}_p$ 上の因数分解 | Cantor-Zassenhaus | 確率的・期待 $O(n^2 \log p)$ |
| $\mathbb{Z}$ への持ち上げ | Hensel 持ち上げ | $O(M(n L) \log L)$ |
| 因子復元 ($r \leq 12$) | Zassenhaus 組合せ | $2^r$ 列挙 |
| 因子復元 ($r > 12$) | van Hoeij LLL | 多項式時間、linalg/LLL.hpp 同梱 |
Int 型と Rational 型は内部で int64_t または Int パスに委譲される。
計算量と実用範囲
| 段階 | 計算量 | 備考 |
|---|---|---|
| content + 有理根 | $O(n \cdot d(c_0) \cdot d(c_n))$ | $d$ は約数の個数 |
| Yun 無平方分解 | $O(n^2)$ 多項式演算 | SR-PRS GCD 経由 |
| Cantor-Zassenhaus | $O(n^2 \log p)$ 期待値 | 確率的 |
| Hensel 持ち上げ | $O(M(n L) \log L)$ | $L = k \log p$ |
| Zassenhaus 組合せ | $O(2^r \cdot n)$ | $r \leq 12$ で実用的 |
| van Hoeij LLL | 多項式時間 | $r > 12$ で必要 |
実用上、$\deg f \leq 100$ かつ係数 bit 長 $\leq 1024$ 程度のサイズは 1 秒以下に収まることが多い。 Swinnerton-Dyer 系の難ケースでは Zassenhaus 経路が破綻するので van Hoeij が必須になる。
設計判断
単一 factorize API
factorize() は単一のエントリポイントで、Cantor-Zassenhaus・Hensel 持ち上げ・Zassenhaus 組合せ・van Hoeij LLL を含む完全パイプラインを提供する。
分割ビルドやリンク選択は不要で、ユーザは入力多項式の型と次数だけを気にすれば良い。
$r \leq 12$ で Zassenhaus を使う理由
$2^r$ の組合せ全列挙は $r \leq 12$ で 4,096 通り、$r = 16$ で 65,536 通り、$r = 20$ で 100 万通り。 Hensel 持ち上げ後の試し割りコスト ($O(n L)$) が支配的になる $r$ の上限は実測で 12 付近にある。 これより大きいと van Hoeij の LLL 前処理コストを払っても多項式時間のほうが速い。
参考文献
- Berlekamp, E. R. (1967). "Factoring polynomials over finite fields". Bell System Technical Journal, 46(8), 1853–1859.
- Cantor, D. G. and Zassenhaus, H. (1981). "A new algorithm for factoring polynomials over finite fields". Mathematics of Computation, 36(154), 587–592.
- Yun, D. Y. Y. (1976). "On square-free decomposition algorithms". SYMSAC '76, 26–35.
- Zassenhaus, H. (1969). "On Hensel factorization, I". Journal of Number Theory, 1(3), 291–311.
- van Hoeij, M. (2002). "Factoring polynomials and the knapsack problem". Journal of Number Theory, 95(2), 167–189.
- Lenstra, A. K., Lenstra, H. W., and Lovász, L. (1982). "Factoring polynomials with rational coefficients". Mathematische Annalen, 261(4), 515–534.