分圆多项式

Published: June 11, 2021 by Daltao

Categories:
algorithm 101

分圆多项式
参考资料

分圆多项式

记 $w_n$ 表示一个 $n$ 次本原单位根（即 $w_n^1,\ldots,w_n^{n-1}\neq 1$ 且 $w_n^{n}=1$ ）。那么 $w_n^1,w_n^1,\ldots,w_n^{n-1},w_n^n$ 是 $x^n-1$ 的 $n$ 个根。因此有：

$x^n-1=\prod_{i=1}^{n}(x-w_n^i)$

定义分圆多项式为 $\Phi_n(x)=\prod_{i=1}^{n}(x-w_n^i)^{[gcd(i,n)=1]}$ 。即根恰好为所有 $n$ 次本原根的多项式。

由定义可以发现：

$\prod_{d|n}\Phi_d(x)=x^n-1$

我们可以用莫比乌斯反演推出：

$\begin{aligned} \sum_{d|n}\ln \Phi_d(x)&=\ln(x^n-1)\\ \Rightarrow \ln \Phi_n(x)&=\sum_{d|n}\mu(n/d)\ln(x^d-1)\\ \Rightarrow \Phi_n(x)&=\prod_{d|n}(x^d-1)^{\mu(n/d)}\\ \end{aligned}$

我们也可以通过递推的方式计算 $\Phi_n(x)$ ，直接通过 $(x^n-1)/\prod_{d|n\land d<n}\Phi_d(x)$ 来得到，其中 $\Phi_1(x)=x-1$ 。

分圆多项式的特性如下：

分圆多项式都是首一整系数多项式
分圆多项式在整数环 $\mathbb{Z}$ 上是不可约的
在 $\mod \Phi_n(x)$ 意义下， $x$ 的阶正好为 $n$ 。

题目1：计算 $\Phi_n(x)$ 。

可以考虑两种做法，一种是通过 $\Phi_n(x)=(x^n-1)/\prod_{d|n\land d<n}\Phi_d(x)$ 来得到。这种做法的时间复杂度为 $O(\sum_{d|n}d^2)$ ，同时它还能对于任意 $t|n$ ，找到 $\Phi_t(x)$ 。

还有一种方法是通过 $\Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(n/d)}$ 得到，利用一些技术，我们可以得到 $O(n\log_2n)$ 的时间复杂度的算法。

题目2：对 $x^n-1$ 做因式分解，将其分解为 $f_1\times f_2\times \cdots \times f_k$ 的形式，且 $f_i$ 是不可约整系数多项式。

提供一道题目。

根据下面公式找到所有分圆多项式，之后输出即可。

$\prod_{d|n}\Phi_n(d)=x^n-1$

分圆多项式

参考资料