[Library Checker] Polynomial Root Finding (Mod 998244353)

問題概要
代数の準備
解法
参考文献

問題概要

問題文 → ■

多項式の相異なる $1$ 次の因数を列挙する問題だと見なすこともできます．特にこの問題は，多項式の因数分解の特殊ケースです．実際，以下で解説するアルゴリズムはほとんどそのまま多項式の因数分解アルゴリズムの一部に利用できます．

$p=998244353$ とします．以下の解説の大部分は $p$ は任意の素数（あるいは素数のべき乗）としても成り立ちますが，一部 $p$ が奇数であることを前提としている部分もあります．

代数の準備

特に高校数学で学ぶ内容から類推できるであろう部分については，証明を省略します．（係数体を $\R$ や $\C$ から $\F_p$ に置き換えただけだと思います．）

$\F_p$ 係数の $1$ 変数多項式全体を $\F_p[x]$ と書きます．

【多項式の除法】
$f(x),g(x)\in \F_p[x]$ とし $g(x)\neq 0$ であるとき，$f(x)=g(x)q(x)+r(x)$ かつ $\deg(g)>\deg(r)$ を満たす $\F_p$ 係数多項式の組 $(q(x),r(x))$が一意に存在する．

$r(x)=0$ のとき $g(x)\mid f(x)$ と書く．

【因数定理】
$f(x)\in \F_p[x]$, $a\in \F_p$ に対して $f(x)$ が $x-a$ で割り切れることと $f(a)=0$ は同値である.　

【因数定理の一般化】
$f(x)\in \F_p[x]$, $a_1,\ldots,a_n\in \F_p$ とし，$a_i$ は相異なるとする．このとき $f(x)$ が $(x-a_1)\cdots(x-a_n)$ で割り切れることと $f(a_1)=\cdots=f(a_n)=0$ は同値である.　

因数定理と数学的帰納法からすぐに証明できます．$\F_p$ の元 $a,b$ について $ab=0$ ならば $a=0$ または $b=0$ であることなどを使います．

【多項式 GCD】
$f_1(x),f_2(x)\in \mathbb{F}_p[x]$ とし，$f_1(x)\neq 0$ または $f_2(x)\neq 0$ であるとする．これらを共に割り切るモニック多項式で最高次数のものを $\gcd(f_1(x),f_2(x))$ と書く（モニックとは最高次の係数が 1 であるということ）．
このときある $a_1(x), a_2(x)$ が存在して，$\gcd(f_1(x),f_2(x))=a_1(x)f_1(x)+a_2(x)f_2(x)$ が成り立つ．

後半部分は例えば，初等整数論でよく知られているのと同様の Euclid の互除法を用いた構成的な証明があります（競技プログラミングでは extgcd という名前でアルゴリズムが紹介されることが多いようです）．直接的に gcd を答えさせているわけではありませんが，この $a_1(x), a_2(x)$ の計算は Inv of Polynomials でも使われており，$\gcd(f_1,f_2)$ は $N=\max(\deg f_1,\deg f_2)$ として $O(N\log^2N)$ 時間で計算できることが知られています（互除法よりも高度なアルゴリズムが必要です）．

【互いに素】
$f(x),g(x)\in \mathbb{F}_p[x]$ は $\gcd(f(x),g(x))=1$ を満たすとき互いに素であるという．$f(x),g(x)$ が互いに素であるとき，任意の $h(x)\in \mathbb{F}_p[x]$ に対して次の同値が成り立つ：$f(x)\mid g(x)h(x)\iff f(x)\mid h(x)$．

$\impliedby$ は明らかなので，$\implies$ を示します．$a_1(x)f(x)+a_2(x)g(x)=1$ となる $a_1(x),a_2(x)$ をとって，$h(x)=1\cdot h(x)=a_1(x)f(x)h(x)+a_2(x)g(x)h(x)$ と書けば，右辺は $f(x)$ および $g(x)h(x)$ の倍数の和なので仮定により $f(x)$ で割り切れます．よって示されました．

【既約多項式】
$1$ 次以上の多項式 $f(x)\in \mathbb{F}_p[x]$ は，より低次の多項式の積として表せないとき既約多項式であるという．$f(x)\in \F_p[x]$ を既約多項式とするとき，任意の $g(x),h(x)\in \F_p[x]$ に対して次の同値が成り立つ：$f(x)\mid g(x)h(x) \iff f(x)\mid g(x)\lor f(x)\mid h(x)$．

$f(x)\mid g(x)$ ではないとして $f(x)\mid h(x)$ を示します．上で示したことから $f(x),g(x)$ が互いに素であることを示せばよいです．$\gcd(f(x),g(x))$ は $f(x)$ を割り切るモニック多項式ですが，$f(x)$ の既約性より $\gcd(f(x),g(x))=1$ なので示されました．

【既約多項式への分解の存在と一意性】
$0$ でない任意の多項式は，定数といくつかの既約モニック多項式の積として表すことができる．その方法は既約モニック多項式の並べ替えの不定性を除き一意である．

$f(x)$ が $2$ 通りの分解 $f(x)=c\cdot p_1(x)\cdots p_k(x) = c\cdot q_1(x)\cdots q_l(x)$ を持つとします．$p_1(x)\mid f(x) =c\cdot q_1(x)\cdots q_l(x)$ から $p_1(x)$ はどれかの $q_j(x)$ を割り切ります．さらに $q_j(x)$ の既約性より $p_1(x)=q_j(x)$ が分かります．この共通の因数で両辺を割ると次数が下がるので，$f$ の次数についての帰納法を考えれば証明が完成します．

解法

$f(x)$ を $N$ 次 $\F_p$ 係数多項式とし，その相異なる根が $a_1, \ldots, a_M$ であるとします．$f$ だけが与えられていて $a_i$ を求めたいです．

step 1. $g(x)=\prod(x-a_i)$ を求める

Fermat の小定理と因数定理から，$\F_p$ において $x^p-x$ の既約多項式への分解は

$$x^p-x=\prod_{a\in \mathbb{F}_p}(x-a)$$

であることを利用すると，$g(x)=\gcd(x^p-x,f(x))$ が求めるものであることが分かります．

繰り返し二乗法で $(x^p-x) \bmod f(x)$ を求めたあと $\gcd$ をとることで，この部分は $O(N\log N\log p + N\log^2N)$ 時間で計算することができます．

問題の目的のためには $f$ を $g$ に取り換えてもよく，その上で次の step 2 に進みます．

step 2. 根の分離

次の性質を持つ多項式を「良い多項式」と呼ぶことにします：相異なる $a_1,\ldots,a_d\in \F_p$ を用いて $\prod(x-a_i)$ と書ける．

step 1. より，本問は，良い多項式を 1 次式の積に分解する問題に帰着されました．

次のことをその方法とともに証明します．

$f$ を $n$ 次の良い多項式とし，$n\geq 2$ であるとする．このとき，期待時間 $O(n\log n\log p)$ で次を行うことができる乱択アルゴリズムが存在する：
$f(x)=f_1(x)f_2(x)$ となる良い多項式 $f_1,f_2$ であって $0.3n \leq \deg f_1 \leq 0.7n$ を満たすものを見つける．

このことを認めると，本問は期待時間 $O(n\log^2n\log p)$ 時間で解けることが基本的な計算量解析で分かると思います．

$f_1, f_2$ を得る具体的なアルゴリズムは次の通りです：

$n$ 次未満の $\F_p$ 係数多項式 $g(x)$ をランダムにとる．
$h(x)=g(x)^{(p-1)/2}\bmod f(x)$ とする．
$f_1(x)=\gcd(f(x),h(x)-1)$, $f_2(x)=f(x)/f_1(x)$ とする．

このとき，$f$ の各根 $a_i$ について次のことが成り立ちます．

$x-a_i$ は $f_1(x), f_2(x)$ のちょうどひとつを割り切る．
$x-a_i$ が $f_1(x)$ を割り切る確率は $\dfrac{p-1}{2p}$, $f_2(x)$ を割り切る確率は $\dfrac{p+1}{2p}$ である．またこの確率は $i$ について互いに独立である．

実際，$n$ 次未満の多項式 $g$ に対して $a_i$ を代入する写像 $\F_p[x]/(f) \ni g\longmapsto (g(a_1),\ldots,g(a_n))\in \F_p^n$ が全単射であることが分かります（因数定理の一般化から単射性が分かります）．代数の知識が十分な場合には，中国剰余定理を考えてもよいでしょう．よって，乱択した $\F_p$ の元 $a$ が $a^{(p-1)/2}=1$ を満たす確率を考えればよく，これは $\dfrac{p-1}{2p}$ です．

$\deg f_1$ は二項分布 $B(n,(p-1)/2p)$ に従うため，上述の不等式を正の確率で満たすことも分かります．なお，不等式は計算量解析を簡単にするため持ち出していますが，実際にはこの不等式を満たす $f_1, f_2$ を満たさない場合にも再帰的に $f$ を分解していけばよいです．

参考

「$a_1+c,\ldots,a_n+c$ がほとんど全ての $c$ について平方剰余や非剰余に偏るということはないだろう」と信じると，$g(x)$ の乱択について $g(x)=x+c$ の形に限定しても意図通りの期待時間計算量が実現できるのではないかと考えられそうです．すると，$g(x)^{(p-1)/2}\bmod f$ の計算過程で $g(x)$ 倍が高速に行えて定数倍改善が期待できます．

https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Rabin_algorithm ではこの方法（と同値な方法）が紹介されています．「Correctness proof」において正当性に言及がありそうですが，ここでは私の記事でいうところの $\deg(f_1)\in \{0,n\}$ となる確率が低いということについて述べているのみで，アルゴリズム全体の計算量を保証する議論はここには記載されていないように思いますし，私もそれ以上は調べていません．