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}\),不满足次乘性。

多项式范数

Polynomial Norm -- from Wolfram MathWorld

可以对多项式 \(\begin{aligned}f(x)=\sum_{i=0}^{n} a_{i} x^{k}\end{aligned}\) 定义范数:

\[ \|f(x)\|_{p} =\left(\sum_{i=0}^{n}\left|a_{i}\right|^{p}\right)^{1 / p} \]

其实就是对系数计算向量范数。


FHE学习笔记 #3 数论中的前置知识
https://ailanxier.top/FHE-3-number theory
作者
Zeyu Dong
发布于
2022年11月4日
许可协议