分圆多项式从入门到进阶：定义、性质与计算全解析

分圆多项式是什么

分圆多项式（Cyclotomic Polynomial）是数论、代数学和群论中一个重要而基础的概念，它与单位根、代数数域和有限域理论等领域有着密切的联系。分圆多项式的研究可以追溯到18世纪，当时Gauss在研究正多边形尺规作图问题时首次系统地研究了它们。“分圆”一词来源于希腊语，意为“分割圆”，反映了这类多项式与单位圆上的点的紧密联系。在代数数论的发展中，Kronecker、Weber和Hilbert等数学家进一步揭示了分圆多项式在数域理论中的核心地位。在现代数学和计算机科学中，分圆多项式在密码学、编码理论、数字信号处理等领域有着广泛应用，是连接代数、几何和数论的重要桥梁。

为了方便大家下载，我已经给大家整理好了资源。资源链接放在下面，自取就好，如果链接失效，可以在评论区留言，我看到了会及时更新。

迅雷网盘下载

分圆多项式的下载安装包

本文章主体由本人所创，源文件为LaTex格式，使用Claude 3.7进行格式转换（LaTex -> Markdown），LaTex源码可见文末，编译后的PDF可下载。

PDF下载链接（永久有效）：

迅雷网盘下载

分圆多项式的核心概念与定义

单位根与本原单位根

单位根是复平面上单位圆周上的点，满足方程 $z^n = 1$ 的复数 $z$。对于每个正整数 $n$，存在 $n$ 个 $n$ 次单位根，表示为：

$$\omega_k = e^{2\pi i k/n} = \cos(2\pi k/n) + i\sin(2\pi k/n), \quad k = 0, 1, 2, \ldots, n-1$$

从几何角度看，$n$ 次单位根在复平面上构成了正 $n$ 边形的顶点，均匀分布在单位圆上。例如，4次单位根 $1, i, -1, -i$ 分别对应复平面上的点 $(1,0), (0,1), (-1,0), (0,-1)$，形成了一个正方形。

本原单位根是指那些阶恰好为 $n$ 的单位根，即满足 $z^n = 1$ 但对于任何 $1 \leq m < n$ 都有 $z^m \neq 1$ 的复数 $z$。$n$ 次本原单位根的个数等于欧拉函数 $\varphi(n)$ 的值。

例如，对于 $n=8$，8次单位根是 ${e^{2\pi i \cdot k/8} | k = 0, 1, \ldots, 7}$。其中 $k=0$ 得到 $\omega_0 = 1$（1次单位根），$k=2,6$ 得到 $\omega_2 = i, \omega_6 = -i$（4次单位根），$k=4$ 得到 $\omega_4 = -1$（2次单位根），而 $k=1,3,5,7$ 得到 $\omega_1, \omega_3, \omega_5, \omega_7$ 是8次本原单位根。

分圆多项式的定义：第 $n$ 个分圆多项式 $\Phi_n(x)$ 定义为所有 $n$ 次本原单位根的最小多项式，即：

$$\Phi_n(x) = \prod_{\substack{1 \leq k \leq n \ \gcd(k,n)=1}} (x - e^{2\pi i k/n})$$

其中 $\gcd(k,n)$ 表示 $k$ 和 $n$ 的最大公约数，条件 $\gcd(k,n)=1$ 确保只选取本原单位根。例如，$\Phi_1(x) = x - 1$，$\Phi_4(x) = (x-i)(x+i) = x^2 + 1$。从代数角度看，$\Phi_n(x)$ 是将 $n$ 次本原单位根 $\zeta$ 添加到有理数域 $\mathbb{Q}$ 后得到的扩域 $\mathbb{Q}(\zeta)$ 上 $\zeta$ 的最小多项式。

分圆多项式的性质与计算方法

性质概览：

整系数性质：尽管分圆多项式是通过复数单位根定义的，但 $\Phi_n(x)$ 的系数全部是整数。该性质可通过归纳法证明，关键在于利用 $\Phi_n(x)$ 的递推定义和Galois理论。特别地，对于任意 $n$ 次本原单位根 $\zeta$，其所有共轭元素也是 $n$ 次本原单位根，因此 $\Phi_n(x)$ 可以看作是Galois群作用下的轨道多项式。
次数：$\Phi_n(x)$ 的次数等于欧拉函数值 $\varphi(n)$。例如 $\varphi(4) = 2$ 对应 $\Phi_4(x) = x^2 + 1$ 的次数为2，$\varphi(5) = 4$ 对应 $\Phi_5(x) = x^4 + x^3 + x^2 + x + 1$ 的次数为4。
递推关系：分圆多项式之间存在重要的递推关系：

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

由此可得 $\Phi_n(x) = \frac{x^n - 1}{\prod_{d|n, d<n} \Phi_d(x)}$，这是计算分圆多项式最常用的方法。

对称性：$\Phi_n(x)$ 是自倒多项式，即 $\Phi_n(x) = x^{\varphi(n)}\Phi_n(1/x)$，这意味着如果 $\alpha$ 是 $\Phi_n(x)$ 的根，那么 $1/\alpha$ 也是它的根。

首几项分圆多项式：$\Phi_1(x) = x-1$，$\Phi_2(x) = x+1$，$\Phi_3(x) = x^2+x+1$，$\Phi_4(x) = x^2+1$，$\Phi_5(x) = x^4+x^3+x^2+x+1$，$\Phi_6(x) = x^2-x+1$，$\Phi_7(x) = x^6+x^5+x^4+x^3+x^2+x+1$，$\Phi_8(x) = x^4+1$，$\Phi_9(x) = x^6+x^3+1$，$\Phi_{10}(x) = x^4-x^3+x^2-x+1$，$\Phi_{12}(x) = x^4-x^2+1$。

计算方法：

直接定义法：确定满足 $\gcd(k,n)=1$ 的所有 $k$ 值，计算对应的本原单位根 $\omega_k = e^{2\pi i k/n}$，构造多项式 $\Phi_n(x) = \prod (x - \omega_k)$ 并展开化简。但这种方法在 $n$ 较大时计算复杂度高，且需要处理复数运算。
递推法：从已知的 $\Phi_1(x) = x-1$ 开始，利用公式 $\Phi_n(x) = \frac{x^n - 1}{\prod_{d|n, d<n} \Phi_d(x)}$ 递推计算。该算法的时间复杂度约为 $O(d(n) \cdot n^2)$，比直接定义法更高效。
莫比乌斯反演法：利用公式 $\Phi_n(x) = \prod_{d|n} (x^{n/d} - 1)^{\mu(d)}$ 直接计算，其中 $\mu(d)$ 是莫比乌斯函数。这种方法可以并行计算，但需要预先计算莫比乌斯函数值。
特殊情况公式：当 $n = p$ 是质数时 $\Phi_p(x) = \frac{x^p - 1}{x - 1} = x^{p-1} + x^{p-2} + \cdots + x + 1$；当 $n = p^m$ 时 $\Phi_{p^m}(x) = \Phi_p(x^{p^{m-1}})$；当 $n = 2p$ 且 $p$ 是奇质数时 $\Phi_{2p}(x) = \Phi_p(-x)$。

计算分圆多项式的代码实现

以下是使用Python和SymPy库实现递推法的完整代码：

from sympy import symbols, Poly, div

def cyclotomic_polynomial_recursive(n):
    """使用递推方法计算第n个分圆多项式"""
    x = symbols('x')
    
    if n == 1:
        return Poly(x - 1, x)
    
    # 计算x^n - 1
    result = Poly(x**n - 1, x)
    
    # 对每个n的真因子d，除以Φ_d(x)
    for d in range(1, n):
        if n % d == 0:  # d是n的因子
            divisor = cyclotomic_polynomial_recursive(d)
            q, r = div(result, divisor)
            result = q
    
    return result

# 测试前几个分圆多项式
for i in range(1, 13):
    print(f"Φ_{i}(x) = {cyclotomic_polynomial_recursive(i)}")

使用莫比乌斯反演法的实现：

from sympy import symbols, Poly
from sympy.ntheory import mobius

def cyclotomic_polynomial_mobius(n):
    """使用莫比乌斯反演计算第n个分圆多项式"""
    x = symbols('x')
    
    # 找出n的所有因子
    factors = []
    for d in range(1, n + 1):
        if n % d == 0:
            factors.append(d)
    
    # 应用莫比乌斯反演公式
    result = 1
    for d in factors:
        mu_d = mobius(d)
        if mu_d != 0:  # 跳过μ(d)=0的情况
            term = (x**(n//d) - 1)**(mu_d)
            result *= term
    
    return Poly(result, x)

# 测试
for i in range(1, 7):
    print(f"Φ_{i}(x) = {cyclotomic_polynomial_mobius(i)}")

实例计算：$\Phi_6(x)$ 的莫比乌斯反演法

6的因子有：1, 2, 3, 6。计算莫比乌斯函数值：$\mu(1)=1$, $\mu(2)=-1$, $\mu(3)=-1$, $\mu(6)=1$。代入公式：

$$\Phi_6(x) = (x^6 - 1)^1 \cdot (x^3 - 1)^{-1} \cdot (x^2 - 1)^{-1} \cdot (x - 1)^1 = \frac{(x^6 - 1)(x - 1)}{(x^3 - 1)(x^2 - 1)}$$

计算得：

$$\frac{(x^6 - 1)(x - 1)}{(x^3 - 1)(x^2 - 1)} = \frac{(x^3 - 1)(x^3 + 1)(x-1)}{(x^3 - 1)(x-1)(x+1)} = \frac{x^3 + 1}{x + 1} = x^2 - x + 1$$

分圆多项式的应用领域

代数数论：分圆多项式是研究分圆域和代数整数环的基础工具。分圆域 $\mathbb{Q}(\zeta_n)$ 是 $\mathbb{Q}$ 上的伽罗瓦扩张，其伽罗瓦群同构于 $(\mathbb{Z}/n\mathbb{Z})^*$，即模 $n$ 的简化剩余类乘法群。分圆域在Kronecker-Weber定理中起核心作用，该定理指出任何阿贝尔扩张都包含在某个分圆域中。

有限域理论：分圆多项式在有限域的构造和分析中起着核心作用。例如，要构造 $\mathbb{F}{2^4}$，可以使用 $\Phi{15}(x) \bmod 2 = x^4 + x + 1$ 作为定义多项式，因为它在 $\mathbb{F}_2$ 上是不可约的。

编码理论：循环码和BCH码的设计与分析依赖于分圆多项式的性质。BCH码的生成多项式是某些分圆多项式的乘积，Reed-Solomon码利用分圆多项式的性质设计高效纠错编码，循环冗余校验(CRC)的设计也利用了分圆多项式的性质。

密码学：基于理想格的密码方案（如NTRU加密系统）利用分圆多项式定义的环 $\mathbb{Z}[x]/(\Phi_n(x))$ 作为基础结构。某些全同态加密方案（如BGV方案）使用分圆多项式环作为明文和密文空间。分圆多项式的不可约性和其他代数性质直接影响了许多基于环的密码系统的安全性参数选择。

离散傅里叶变换：在FFT算法中，$n$ 次单位根 $\omega_n = e^{2\pi i/n}$ 及其幂起着核心作用。FFT算法利用单位根满足 $\omega_n^n = 1$ 和 $\omega_n^{n/2} = -1$ 等性质，将 $O(n^2)$ 复杂度的离散傅里叶变换降低到 $O(n\log n)$。

常见问题

问：分圆多项式为什么系数都是整数？ 答：因为分圆多项式 $\Phi_n(x)$ 可以看作是Galois群作用下的轨道多项式，对于任意 $n$ 次本原单位根 $\zeta$，其所有共轭元素也是 $n$ 次本原单位根，这样的多项式具有整系数。

问：计算分圆多项式有哪些常用方法？ 答：主要有三种方法：直接定义法（适用于较小的 $n$）、递推法（利用 $x^n - 1 = \prod_{d|n} \Phi_d(x)$ 的关系）和莫比乌斯反演法（利用公式 $\Phi_n(x) = \prod_{d|n} (x^{n/d} - 1)^{\mu(d)}$）。此外还有适用于特殊情况（如 $n$ 为质数、质数幂或 $2p$）的简化公式。

问：分圆多项式的次数是多少？ 答：第 $n$ 个分圆多项式 $\Phi_n(x)$ 的次数等于欧拉函数值 $\varphi(n)$，即小于等于 $n$ 且与 $n$ 互质的正整数个数。