FHE学习笔记 #2 多项式环 _生活百科

https://en.wikipedia.org/wiki/Polynomial_ring
https://zhuanlan.zhihu.com/p/419266064
这篇知乎文章讲的比较透彻，但是不易理解，可以结合以下视频学习。
无尽沙砾大佬的视频：3-6-多项式环-4_哔哩哔哩_bilibili ~3-6-多项式环-8_哔哩哔哩_bilibili
【FHE学习笔记 #2 多项式环】顾沛老师的视频：30.多项式环1_哔哩哔哩_bilibili
本文主要是简化了知乎文章的叙述，优化了公式的显示效果，便于自己理解
文章使用 wolai 编写并导出，在 wolai 中观看效果更好，有颜色高亮和实时更新

背景以往认知中的多项式是函数形式的，且定义在数域上。如果 \(\mathbb{P}\) 是一个数域，那么 \(\mathbb{P}\) 上的一元多项式环 \(\mathbb{P}[x]\) 是由形如
\[a_n x^n+a_{n-1} x^{n-1}+\cdots+a_1 x+a_0, \quad n \geqslant 0, \quad a_i \in \mathbb{P}, \quad i=0,1, \ldots, n\]的元素组成的集合。集合 \(\mathbb{P}[x]\) 上两个元素 \(a_n x^n+a_{n-1} x^{n-1}+\cdots+a_1 x+a_0, b_m x^m+b_{m-1} x^{m-1}+\cdots+b_1 x+b_0\)（不妨设 \(m \geqslant n\)）相等当且仅当对任何 \(0 \leqslant i \leqslant m, a_i=b_i\)（这里规定，如果 \(k>n\)，则 \(a_k=0\)）。而环 \(\mathbb{P}[x]\) 的加法就是合并同类项，乘法是展开相乘再合并同类项。
但是实际上多项式可以推广到一般环上，这样的定义会出问题。例如 \(x\) 究竟是什么东西，取值是什么，它可能都不需要取自数域 \(\mathbb{P}\) 。所以必须更严格的给出 \(x\) 的定义，其实就是后面所谓的超越元（不定元）。
\(R\) 上添加 \(u\) 形成的环 \(R[u]\)

为了和知乎大佬、顾沛老师的记号统一，用 \(u\) 来表示之前认知中的 \(x\)，也就是自变量。

多项式的系数是定义在一个环 \(R\) 上的，若 \(R\) 和 \(u\) 要组成多项式运算，则要求他们的运算结果在一个更大的环 \(R[u]\) 上，且要求这是包含 \(R\cup \{u\}\) 最小的环。

这里有一个更大的环 \(\widetilde R\)，它包含了 \(R,u,R[u]\)，至于为什么有这个环笔者也不太清楚
他们之间的关系是这样的：

文章插图

为了构造出环 \(R[u]\)，考虑它里面的每个元素 \(x\)，都是由以下几种形式构成：

\(R\) 中的元素，即 \(x \in R\)，且它们之间的乘法加法都是封闭的，都在 \(R\) 中
\(u\) 的自乘，即存在某个正整数 \(n\) 使得 \(x=u^n\)
\(u\) 的自加，即存在某个整数 \(m\) 使得 \(x=m u\)
\(u\) 的自乘和 \(R\) 中元素的互乘，即存在 \(a, b \in R\) 和正整数 \(n\) 使得 \(x=a u^n\) 或 \(x=u^n a\) 或 \(x=a u^n b\)
上述情况的加和，\(x=r+\sum_n m_n u^n+\sum_n a_n u^n+\sum_n u^n b_n+\sum_n c_n u^n d_n\)，\(r \in R, a_n, b_n, c_n, d_n\) 是 \(R\) 当中的元素序列

这样 \(R[u]\) 的元素形式比较复杂，通常我们要求 \(R\) 和 \(\widetilde{R}\) 都是可换幺环，并且它们的幺元相同，来简化元素形式，同时更贴近多项式的形式。
在这样要求以后，我们看到 \(u^n\) 的自加 \(m u^n\) 可以表述为
\[\sum_{i=1}^m u^n=\sum_{i=1}^m\left(1 u^n\right)=\left(\sum_{i=1}^m 1\right) u^n\]因为 \(1 \in R\) 而 \(R\) 是环，因此 1 的自加也在 \(R\) 当中，即存在 \(a \in R\) 使得 \(\begin{aligned}a=\sum_{i=1}^m 1\end{aligned}\)，进而自加 \(m u^n\) 可以表示为 \(a u^n, a \in R\) 的形式，同理自乘也可以化成 \(a u^n, a \in R\) 的形式。其余可以通过交换性获得相同的形式。最后 \(R[u]\) 中元素的形式简化为：
\[x=a_0+\sum_n a_n u^n, a_0, a_n \in R\]可以人为规定 \(u^0=1\)，最后将其写成 \(x=\sum_n a_n u^n ， n\) 取值从0开始，到某个正整数。