FHE学习笔记 #3 数论中的前置知识

本文最后更新于：2022年11月16日下午

文章使用 wolai 编写并导出，在 wolai 中观看效果更好，有颜色高亮和实时更新

不可约多项式 Irreducible Polynomial

Irreducible polynomial - Wikipedia

定义比较多，通俗来说，不可约多项式首先是「非常数多项式 Non-constant Polynomial」，且不能被分解成两个「非常数多项式」乘积的形式。

如果能分解为仅含常数项的多项式，那用单位元 $\bf 1$ 就能无限分解了，显然不合理。

更严格的定义是要说明在什么域上是不可约的，例如 $x^2-2$ 在整数域上是不可约的，因为它不能分解成系数为整数的非常数多项式。但是 $x^2-2$ 在实数域上属于可约多项式，可以分解为 $(x-\sqrt 2)(x-\sqrt 2)$。

单位根 Root of Unity

Root of unity - Wikipedia
n 次单位根的求法_cyzhou1221的博客-CSDN博客_n次单位根
极其推荐阅读 🔥：分圆多项式 (yhx-12243.github.io)，前置知识有详细讲述单位根和本原单位根的内容，需要科学上网

在复数域上，$n$ 次单位根是指方程 $z^n=1$ 的解，$n$ 为正整数，且在复数域内有且只有 $n$ 个解。解的形式为

\[ z_k=e^{\frac{2\pi i}{n}k}=\exp\left(\frac{2\pi i}{n}k\right),k\in\mathbb{Z} \]

证明：
复数的形式为 $z=R\exp(i\theta)=R\cos\theta+iRsin\theta,R>0$
两个复数 $z_1,z_2$ 相等 $\iff~~R_1=R_2,\theta_1=\theta_2+2k\pi,k\in \mathbb{Z}$
而复数 $1=1\exp(i0),\text{i.e.}\;R=1,\theta=0$，代入 $z^n=1$ 得到：
\[ R^n=1,n\theta=2k\pi+0,R\ge0,k\in \mathbb{Z} \]
解得 $\begin{aligned}R=1,\theta=\frac{2k\pi}{n}\end{aligned},k\in\mathbb{Z}$，则 $\begin{aligned}z_k=\exp\left(\frac{2\pi i}{n}k\right),k\in\mathbb{Z} \end{aligned}$

实际上，只有 $k=0,1,\cdots,n-1$ 共 $n$ 个不重根，也就是说，在复数域上对 1 开 $n$ 次方根的结果有 $n$ 个。

设 $\begin{aligned}z=\exp\left(\frac{2\pi i}{m}\right)\end{aligned}$，则这 $n$ 个根为 $z^0=1,z,z^2,\ldots,z^{n-1}$。

证明：
取 $k=n+s,s\in\mathbb{Z}$，则
\[ \begin{aligned} z_k=\exp\left(\frac{2\pi i}{n}k\right)&=\exp\left(\frac{2\pi i}{n}(n+s)\right)=\exp\left(2\pi i+\frac{2\pi i}{n}s\right) \\&=\exp\left(2\pi i\right)\times\exp\left(\frac{2\pi i}{n}s\right)=(e^{\pi i})^2\times\exp\left(\frac{2\pi i}{n}s\right) \\&=1\times\exp\left(\frac{2\pi i}{n}s\right)=z_s \end{aligned} \]
这里使用了欧拉公式 $e^{\pi i}+1=0$。
可以看出当 $k,s$ 属于同一同余类（模 $n$）时，这两个根是相同的，所以不重根的数目和模 $n$ 最小剩余系大小相同，即 $n$。

一些性质：

对于任意 $n$，当 $k=0$ 时，$z_k=1$
$n$ 次单位根的模为 1，在复平面 Complex plane 上等分单位圆，如下图是 $n=5$ 次单位根在复平面上的分布
$n$ 次单位根的任意次幂仍为 $n$ 次单位根
证明：
设 $z$ 是 $n$ 次单位根，则对于 $k\in\mathbb{Z}$，有
\[ (z^k)^n=(z^n)^k=1^k=1 \]
同理可以证出，任意两个 $n$ 次单位根的乘积仍然是 $n$ 次单位根
由上述性质，可以得到所有 $n$ 次单位根可以构成一个乘法交换循环群
利用 $n$ 个根对 $x^n-1$ 进行多项式分解
由 Vieta 定理可以得到：
\[ z=\exp\left(\frac{2\pi i}{m}\right)，x^n-1=(x-1)(x-z)\cdots(x-z^{n-1}) \]
Vieta's formulas - Wikipedia

单位原根 Primitive Roots of Unity

$n$ 次单位原根是指 $n$ 次单位根中的某些根 $z$，满足 $\forall m\in\{1,2,\ldots,n-1\},z^m\not=0,z^n=1$。

$n$ 次单位根 $z_k$ 满足 $\gcd(n,k)=1$ $\iff$ $n$ 次单位原根。

自己瞎证明的 🥺：
$\gcd(n,k)=1$ 说明 $z_k$ 就是 $n$ 次单位原根
设 $\forall k\in\{k|\gcd(n,k)=1\}$，$\begin{aligned}z_k=\exp\left(\frac{2k\pi i}{n}\right)\end{aligned}$ ，则 \[ \begin{aligned} \exists d \in\mathbb{N^+}\text{~s.t.~} z_k^d=\exp\left(\frac{2kd\pi i}{n}\right)=1 \end{aligned} \]
由 $\exp(i\theta)=\cos\theta+i\sin\theta$ 展开得到
\[ \exp\left(i\frac{2kd\pi }{n}\right)=\cos\left(\frac{2kd\pi }{n}\right)+i\sin\left(\frac{2kd\pi }{n}\right) \]
则 $\begin{aligned}\frac{2kd\pi }{n}=2k'\pi,k'\in\mathbb{Z}\end{aligned}$，这样 $\begin{aligned}\cos\frac{2kd\pi }{n}\end{aligned}$ 才会等于 1，
化简得到 $kd=k'n,k'\in\mathbb Z$，即 $n\mid kd$，
又因为 $\gcd(n,k)=1$，所以 $n\mid d$，也就是说 $n\le d$，所以 $n$ 就是使 $z_k^d=1$ 成立的最小正数 $d$，满足 $n$ 次单位原根的定义。
$n$ 次单位原根都满足 $\gcd(n,k)=1$
首先 $k=0$ 时一定不是 $n$ 次单位原根，因为本身就是 1，同时也不满足 $\gcd(n,k)=1$。
假设 $z_k,1\le k<n$ 是 $n$ 次单位原根，记 $\gcd(n,k)=d,1\le d<n,n=n'd,k=k'd,n'\in \mathbb{Z},k' \in \mathbb Z$，那么有
\[ z_k^{n'}=\exp\left(\frac{2kn'\pi i}{n}\right)=\exp\left(\frac{2\pi i}{n}\times\frac{kn}{d}\right)=\exp\left(2\pi i k'\right)=1 \]
如果 $d\not=1$，则有 $n'<n$，这就不满足 $z_k$ 是 $n$ 次单位原根的前提，得到矛盾，所以 $d=1$，即 $\gcd(n,k)=1$。

性质：

若 $n$ 是质数，对于 $k=\{1,2,\ldots,n-1\}$ 的 $z_k$ 都是 $n$ 次单位原根
若 $z$ 为 $n$ 次单位原根，则 $z^0,z^1,z^2,\ldots,z^{n-1}$是互异的 $n$ 次单位根，即生成了整个 $n$ 次单位根循环群，$z$ 是生成元
证明：
首先由 $n$ 次单位根的性质可知 $z$ 的任意次幂都是 $n$ 次单位根。
假设存在 $z^a=z^b,0\le a<b\le n-1$，那么 $z^{b-a}=1,0<b-a\le n-1$，这就与原根的定义矛盾，所以这些次幂都是互异的。

分圆多项式 Cyclotomic Polynomial

Cyclotomic polynomial - Wikipedia
数论讲义下多项式 2 分圆多项式_哔哩哔哩_bilibili
分圆多项式的简单性质与应用 - 知乎 (zhihu.com)
极其推荐阅读 🔥：分圆多项式 (yhx-12243.github.io)

$n$ 次分圆多项式是 $x^n-1$ 的因式，具有以下特点：

具有整数系数
是唯一且不可约的
首一多项式
不是任何 $x^k-1,k<n$ 的因式
是实数域上 $n$ 次单位根的极小多项式

从最后一点可以看出，$n$ 次分圆多项式与 $n$ 次单位原根有着紧密的关系，实际上，$n$ 次分圆多项式的形式就是 $n$ 次单位原根为单根的首一多项式的乘积：

\[ \Phi_{n}(x)=\prod_{\substack{1 \leq k \leq n \\ \operatorname{gcd}(k, n)=1}}\left(x-e^{2 i \pi \frac{k}{n}}\right) \]

由于 $n$ 次单位原根一共有 $\varphi(n)$ 个，所以 $n$ 次分圆多项式的次数为 $\text{deg}\;\Phi_n(x)=\varphi(n)$，大概也就是分圆多项式使用 $\Phi$ 的原因吧。
这里上下界划到了 $[1,n]$，其实是和 $[0,n-1]$ 模 $n$ 等价的，但是不能对 $0$ 进行 $\gcd$ 运算，所以后面都用 $[1,n]$。

$n$ 次分圆多项式具有许多奇妙的特性：

$\begin{aligned}\prod_{d\mid n}\Phi_d(x)=x^n-1\end{aligned}$
首先讲一个引理 $\begin{aligned}\sum_{d\mid n}\varphi(d)=n\end{aligned}$ 及其证明，类似这个证明可以证出上述特性。
证明：
如果 $\gcd(k,n)=d,k<n$，那么就有 $\begin{aligned}\gcd\left(\frac{k}{d},\frac{n}{d}\right)=1\end{aligned}$。
如果我们要统计 $1\sim n$ 的整数中，满足 $\gcd(k,n)=d$ 的 $k$ 的个数，记为 $f(d)$。
让我们试着考虑一下小于 $\begin{aligned}\frac{n}{d}\end{aligned}$ 的整数中，与 $\begin{aligned}\frac{n}{d}\end{aligned}$ 互质的数 $k'$，会发现他们乘上 $d$ 后，满足 $\gcd(k'd,n)=d$。
所以有 $\begin{aligned}f(d)=\varphi\left(\frac{n}{d}\right)\end{aligned}$。
又因为 $n$ 和 $1\sim n$ 中每个整数的 $\gcd$ 都是 $n$ 的因子，所以有 $\begin{aligned}\sum_{d=1}^nf(d)=\sum_{d\mid n}f(d)=n\end{aligned}$，
进而得到 $\begin{aligned}\sum_{d\mid n}\varphi\left(\frac{n}{d}\right)=n\end{aligned}$，由于因子 $d$ 和 $\begin{aligned}\frac{n}{d}\end{aligned}$ 具有对称性，所以 $\begin{aligned}\sum_{d\mid n}\varphi(d)=n\end{aligned}$。
类似上面的证明思路，先设 $\begin{aligned}\omega_n^k=\exp\left(\frac{2k\pi i}{n}\right),k\in\{0,1,\ldots,n-1\}\end{aligned}$ 为一个 $n$ 次单位根，记 $\gcd(n,k)=d,n=n'd,k=k'd,\gcd(n',k')=1,n'>k'$。
此时我们会发现，$w_{n'}^{k'}$ 不就是 $n'$ 次单位原根吗，因为它满足了 $\gcd(n',k')=1$，注意到 $n'\mid n$，即它也是 $n$ 的因子。
进一步会发现，$w_{n'}^{k'}$ 是个 $n$ 次单位根，因为有
\[ \begin{aligned} \omega_{n'}^{k'}=\exp\left(\frac{2k'\pi i}{n'}\right)=\exp\left(\frac{2k'\pi i\times\frac{n}{n'}}{n'\times\frac{n}{n'}}\right) =\exp\left(\frac{2k'd\pi i}{n}\right) =\exp\left(\frac{2k\pi i}{n}\right) =w_n^k \end{aligned} \]
又绕回来了，显然可以看出每个 $n$ 的因子 $n'$ 的单位原根，都和 $n$ 次单位根有着一一对应的关系。
对于一个 $n$ 次单位根 $w_n^k$，每个 $k$ 确定了一个因子 $n'$ 和其对应的 $w_{n'}^{k'}$ 单位原根。
又因为我们上面有 $x^n-1$ 的因式分解形式为
\[ x^n-1=(x-1)(x-w_n^1)\cdots(x-w_n^{n-1}) \]
还有 $n'$ 的分圆多项式形式
\[ \Phi_{n'}(x)=\prod_{\substack{1 \leq k' \leq n' \\ \operatorname{gcd}(k', n')=1}}\left(x-w_{n'}^{k'}\right) \]
根据一一对应关系，逐一代替为 $ n' $ 次单位原根就能得到 $\begin{aligned}\prod_{d\mid n}\Phi_d(x)=x^n-1\end{aligned}$。
当 $n$ 为质数时，有：
\[ \Phi_{n}(x)=\frac{x^{n}-1}{x-1}=x^{n-1}+x^{n-2}+\cdots+1 \]
证明：
首先有个因式分解的奇技淫巧：
\[ x^{n}-1=(x-1)\left(x^{n-1}+x^{n-2}+\cdots+x+1\right) \]
把右边乘进去就会发现中间次数项都被巧妙地消掉了，只剩 $n$ 次方项和 1。
然后由第一个分圆多项式的性质，可以知道当 $n$ 为质数时，因子只有 1 和它本身，有
\[ \begin{aligned} \prod_{d\mid n}\Phi_d(x)=\Phi_1(x)\Phi_n(x)=(x-w_1^1)\Phi_n(x)=(x-1)\Phi_n(x)=x^n-1 \end{aligned} \]
移项后再代入上述因式分解中即可得到 $\begin{aligned} \Phi_{n}(x)=\frac{x^{n}-1}{x-1}=x^{n-1}+x^{n-2}+\cdots+1 \end{aligned}$
对于任意正整数 $n$，$\Phi_{n}(x)$ 是整数多项式环 $\mathbb{Z}[x]$ 中的不可约多项式
$\Phi_{2^{d}}(x)=x^{2^{d-1}}+1$

范数

范数 (ustc.edu.cn)
Norm (mathematics) - Wikipedia ~ 规范（数学） - 维基百科
Polynomial Norm -- from Wolfram MathWorld

范数是一个从实数或复数向量空间（Real or Complex Vector Space）$X$ 到非负实数（Non-negative Real Bumbers）$\mathbb R$的实值函数（Real-valued Function） $f:X\to\mathbb R$，并且满足以下性质：

正定性 Positive Definiteness：
\[ f(x)=0\iff x=0 \]
绝对齐次性（Absolute Homogeneity）：
$\forall s\in\mathbb R,\forall x\in X,f(sx)=|s|f(x)$，$s$ 为标量。
三角不等式（Triangle Inequality，或叫「次加性」 Subadditivity）：
\[ \forall x, y \in X,f(x+y) \leq f(x)+f(y) \]

称 $f(x)$ 是 $X$ 上的范数，记为 $\|x\|$。

非负性其实由绝对齐次性和次加性推出，所以不是必须指出的性质：
首先令 $s=0$，可以得到 $f(0\times x)=f(0)=0$。
令 $s=-1$，可以得到 $\forall x\in X,f(-x)=f(x)$，假设存在 $f(a)<0$，则 $f(-a)=f(a)<0$。
根据次加性有 $f(a+(-a))=f(0)=0<f(a)+f(-a)$，然而 $f(a)+f(-a)<0$，所以矛盾。

对于 $n$ 维欧式空间（Euclidean Space） $\mathbb{R}^n$，其上的向量形式为 $\boldsymbol{x}=\left(x_{1}, x_{2}, \ldots, x_{n}\right)$，有几种常用的范数：

$p$-范数：
\[ \|\boldsymbol{x}\|_{p}:=\left(\sum_{i=1}^{n}\left|x_{i}\right|^{p}\right)^{1 / p} \]
里面常用的有「1-范数（又叫曼哈顿范数 Manhattan Norm）」和「2-范数（又叫欧几里得范数 Euclidean Norm）」，分别为：
\[ \|\boldsymbol x\|_{1}=\sum_{i=1}^{n}\left|x_{i}\right|,\quad\|\boldsymbol x\|_{2}=\sqrt{\sum_{i=1}^{n} x_{i}^{2}} \]
无穷范数 Infinity Norm：
Uniform norm - Wikipedia
\[ \|\boldsymbol{x}\|_{\infty}:=\max \left(\left|x_{1}\right|, \ldots,\left|x_{n}\right|\right) \]
实际上称为最大范数（Maximum Norm）更好，更一般的称呼是「一致范数（Uniform Norm）」，这是定义在取指为集合 $S$ 上有界函数 $f$，形式为：
\[ \|f\|_{\infty}=\|f\|_{\infty, S}=\sup \{|f(s)|: s \in S\} \]
sup 是 supremum（上确界）的简写，类似还有 inf 是 infimum（下确界）的简写。
一致范数有许多名称：上确界范数 Supremum Norm、切比雪夫范数 Chebyshev Norm 和无穷范数。
当上确界就是取最大值时，才称为最大范数。
一致范数的起名和函数序列的一致收敛有关。

矩阵范数 Matrix Norm

Matrix norm - Wikipedia
矩阵范数 - 维基百科，自由的百科全书 (wikipedia.org)
1.2. 矩阵范数

定义和范数类似，设 $K$ 为实数或复数构成的域，$K^{m\times n}$ 是 $m$ 行 $n$ 列的矩阵，函数 $\|\cdot\|: K^{m \times n} \rightarrow \mathbb{R}$ 称为 $K^{m\times n}$ 上的范数，且要满足以下条件（$\alpha\in K$，$A, B \in K^{m \times n}$）：

非负：$\|A\| \geq 0$
正定：$\|A\|=0 \Longleftrightarrow A=0_{m, n}$
绝对齐次性：$\|\alpha A\|=|\alpha|\|A\|$
次加性：$\|A+B\| \leq\|A\|+\|B\|$
不是必须的性质：次乘性：$\|A B\| \leq\|A\|\|B\|$，拥有次乘性的矩阵范数用处很大，同时所有定义在 $K^{n\times n}$ 上的矩阵范数都具有次乘性

比较常使用的矩阵范数：

向量范数诱导的矩阵范数 Matrix Norms Induced by Vector Norms：
$\|\cdot\|_{\alpha},\;\|\cdot\|_{\beta}$ 分别是 $K^n$ 和 $K^m$ 上的向量范数，矩阵 $A^{m\times n}$ 是从 $K^n$ 到 $K^m$ 的线性变换矩阵，相应的诱导范数为：
\[ \begin{aligned}\|A\|_{\alpha, \beta} &=\sup \left\{\|A \boldsymbol x\|_{\beta}:\boldsymbol x \in K^{n} \text { with }\|\boldsymbol x\|_{\alpha}=1\right\} \\ &=\sup \left\{\frac{\|A \boldsymbol x\|_{\beta}}{\|\boldsymbol x\|_{\alpha}}:\boldsymbol x \in K^{n} \text { with }\boldsymbol x \neq 0\right\} \end{aligned} \]
用来衡量矩阵对向量的拉伸程度。
向量范数诱导的矩阵范数 $\|\cdot\|_{\alpha, \alpha}$ 都具有次乘性，即
\[ \|A B\|_{\alpha, \alpha} \leq\|A\|_{\alpha, \alpha}\|B\|_{\alpha, \alpha} \]
同时这样的范数满足：
\[ \forall r\in\mathbb N^+,\left(\left\|A^{r}\right\|_{\alpha, \alpha}\right)^{1 / r} \geq \rho(A) \]
$\rho(A)$ 是矩阵 $A$ 的谱半径 Spectral Radius，是 $A$ 中特征值绝对值的最大值。
此外谱半径还是任意矩阵范数的下确界。
当 $K^n$ 和 $K^m$ 的向量范数都是 $p$-范数时，诱导的矩阵范数称为矩阵的诱导 $p$-范数，形式如下：
\[ \|A\|_{p}=\max _{\boldsymbol x \neq 0} \frac{\|A\boldsymbol x\|_{p}}{\|\boldsymbol x\|_{p}}=\max _{x \neq 0} \frac{\begin{aligned}\left(\sum_{i=1}^{m}\left|\sum_{j=1}^{n} a_{i j}\boldsymbol x_{j}\right|^{p}\right)^{1 / p}\end{aligned} }{\begin{aligned}\left(\sum_{j=1}^{n}\left|\boldsymbol x_{j}\right|^{p}\right)^{1 / p}\end{aligned} } \]
- $p=1$，相当于矩阵每一列绝对值相加，得到的和向量的中的最大值：
  \[ \|A\|_{1}=\max _{1 \leq j \leq n} \sum_{i=1}^{m}\left|a_{i j}\right| \]
- $p=\infty$，相当于矩阵每一行绝对值相加，得到的和向量的中的最大值：
  \[ \|A\|_{\infty}=\max _{1 \leq i \leq m} \sum_{j=1}^{n}\left|a_{i j}\right| \]
- $p=2$，诱导的矩阵范数就是谱范数。矩阵 $A$ 的谱范数是 $A$ 最大的奇异值 $\sigma_{\max }(A)$ 或半正定矩阵 $A^* A$ 的最大特征值的平方根：
  \[ \|A\|_{2}=\sqrt{\lambda_{\max }\left(A^{*} A\right)}=\sqrt{\rho\left(A^{*} A\right)}=\sigma_{\max }(A) \]
  $A^*$ 是 $A$ 的共轭转置 Conjugate Transpose
"Entry-wise" Matrix Norms 逐元素的矩阵范数（不会翻译）
这种范数将 $m\times n$ 矩阵视作大小为 $mn$ 的向量，再运用向量范数进行计算
部分记号和上述的 $p$-范数相同，但是意义不同
- $L_{p,q}$ 范数：
  记 $(a_1,a_2,\ldots,a_n)$是矩阵 $A$ 的列，$L_{2,1}$ 范数可以视作对于每一列向量计算 2-范数，再加和，即：
  \[ \|A\|_{2,1}=\sum_{j=1}^{n}\left\|a_{j}\right\|_{2}=\sum_{j=1}^{n}\left(\sum_{i=1}^{m}\left|a_{i j}\right|^{2}\right)^{\frac{1}{2}} \]
  更一般的，设 $p,q\ge 1$，$L_{2,1}$ 范数可以推广到$L_{p,q}$ 范数：
  \[ \|A\|_{p, q}=\left(\sum_{j=1}^{n}\left(\sum_{i=1}^{m}\left|a_{i j}\right|^{p}\right)^{\frac{q}{p}}\right)^{\frac{1}{q}} \]
- 弗罗贝尼乌斯范数 Frobenius Norm：
  其实就是 $p=q=2$ 的 $L_{p,q}$ 范数，他的形式如下：
  \[ \|A\|_{\mathrm{F}}=\sqrt{\sum_{i}^{n} \sum_{j}^{n}\left|a_{i j}\right|^{2}}=\sqrt{\operatorname{trace}\left(A^{*} A\right)}=\sqrt{\sum_{i=1}^{\min \{m, n\}} \sigma_{i}^{2}(A)} \]
  具有次乘性的且通常比诱导范数容易计算。
- 最大值范数 Max Norm
  即矩阵中绝对值最大的元素，形式为 $\begin{aligned}\|A\|_{\max }=\max _{i j}\left|a_{i j}\right|\end{aligned}$，不满足次乘性。