后量子密码｜前置基础 01｜PQC 极简数学：模运算、有限域、多项式环、矩阵、范数与小系数噪声
-
- 前言
- 一、先从一条核心公式看全局
-
- 1.1
t
=
A
s
+
e
\\mathbf t=\\mathbf A\\mathbf s+\\mathbf e
t=As+e 中有什么 - 1.2 为什么一定要先规定“计算空间”
- 1.1
- 二、模运算：把无限整数压进有限空间
-
- 2.1 同余不是近似相等
- 2.2 为什么同一个系数有两种写法
- 2.3 环、域与逆元
- 三、多项式环：格密码真正进行计算的地方
-
- 3.1 从系数模
q
q
q 到多项式模f
(
x
)
f(x)
f(x) - 3.2 完整算一次多项式乘法
- 3.3 卷积为什么会“折返并变号”
- 3.1 从系数模
- 四、从一个多项式到矩阵和向量
-
- 4.1 多项式与系数向量是同一个对象的两种视角
- 4.2 模块格中的“矩阵元素”仍然是多项式
- 五、范数：怎样描述秘密和噪声“足够小”
-
- 5.1 在模
q
q
q 的世界里衡量大小 - 5.2 小系数不等于小密钥空间
- 5.3 噪声为什么既不能没有，也不能失控
- 5.1 在模
- 六、把所有概念重新装回公式
- 七、读完本文应该建立的数学直觉
专栏说明：《后量子密码》专栏，本专栏面向零基础读者，循序渐进讲解后量子密码理论、NIST标准算法、攻击分析、工程落地与迁移实践。 https://blog.csdn.net/r_feynman_/category_13197405.html
前言
第一次阅读 ML-KEM、ML-DSA 或 LWE 资料时，真正劝退初学者的往往不是算法流程，而是下面这类公式：
t
=
A
s
+
e
(
m
o
d
q
)
\\mathbf t=\\mathbf A\\mathbf s+\\mathbf e\\pmod q
t=As+e(modq)
公式看起来只有一次乘法和一次加法，背后却同时藏着模运算、多项式环、卷积、矩阵向量、中心化表示、范数和随机采样。任何一个概念没有接上，后面的密钥生成、封装和签名推导都会变成机械抄公式。
不过，理解这些内容并不需要先学完一整本抽象代数。对于后量子密码入门，最重要的是弄清楚三个问题：
本文把原本分散的数学概念放回同一条主线中。读完之后，再看到
A
s
+
e
\\mathbf A\\mathbf s+\\mathbf e
As+e，应该能够从最外层的矩阵运算，一直展开到最底层的系数乘加。
本文建立的是阅读格密码所需的数学直觉，不替代 ML-KEM、ML-DSA 标准中的参数、采样、编码和安全证明。
一、先从一条核心公式看全局
1.1
t
=
A
s
+
e
\\mathbf t=\\mathbf A\\mathbf s+\\mathbf e
t=As+e 中有什么
格密码资料中经常出现如下公开关系：
t
=
A
s
+
e
(
m
o
d
q
)
\\mathbf t=\\mathbf A\\mathbf s+\\mathbf e\\pmod q
t=As+e(modq)
可以先把它读成一句普通的话：
用公开矩阵
A
\\mathbf A
A 乘秘密向量
s
\\mathbf s
s，加入一份较小的随机误差
e
\\mathbf e
e，最后把所有系数约简到模
q
q
q 的范围内，得到公开向量
t
\\mathbf t
t。
各符号通常承担如下角色：
|
q q q |
限定系数范围的模数 | 是 |
|
A \\mathbf A A |
公开矩阵或由种子展开得到的矩阵 | 是 |
|
s \\mathbf s s |
从小系数分布采样的秘密向量 | 否 |
|
e \\mathbf e e |
从小系数分布采样的误差向量 | 通常不公开 |
|
t \\mathbf t t |
带噪声的公开结果 | 是 |
这里最容易产生的误解，是把
A
\\mathbf A
A、
s
\\mathbf s
s 和
e
\\mathbf e
e 当成普通整数矩阵。模块格密码中，它们的元素往往不是单个整数，而是多项式环中的多项式。于是一次矩阵乘法实际上包含四层运算：
矩阵乘法
⟶
多项式乘法
⟶
卷积与折返
⟶
系数模
q
约简
\\text{矩阵乘法} \\longrightarrow \\text{多项式乘法} \\longrightarrow \\text{卷积与折返} \\longrightarrow \\text{系数模 }q\\text{ 约简}
矩阵乘法⟶多项式乘法⟶卷积与折返⟶系数模 q 约简
后面的全部内容，就是把这四层依次拆开。
1.2 为什么一定要先规定“计算空间”
普通整数中的
10
+
5
=
15
10+5=15
10+5=15。若在模
12
12
12 的空间中，则有：
10
+
5
≡
3
(
m
o
d
12
)
10+5\\equiv3\\pmod {12}
10+5≡3(mod12)
普通多项式中，
x
4
x^4
x4 是四次项；若在模
x
4
+
1
x^4+1
x4+1 的多项式环中，则有：
x
4
≡
−
1
(
m
o
d
x
4
+
1
)
x^4\\equiv-1\\pmod{x^4+1}
x4≡−1(modx4+1)
同一个表达式放进不同的计算空间，会得到不同结果。因此，看到后量子密码公式时，不能只看“算了什么”，还要先看它“在哪里算”。
二、模运算：把无限整数压进有限空间
2.1 同余不是近似相等
给定正整数
q
q
q，若
q
q
q 能整除
a
−
b
a-b
a−b，即：
q
∣
(
a
−
b
)
q\\mid(a-b)
q∣(a−b)
则称
a
a
a 与
b
b
b 模
q
q
q 同余，记作：
a
≡
b
(
m
o
d
q
)
a\\equiv b\\pmod q
a≡b(modq)
例如：
17
≡
5
(
m
o
d
12
)
17\\equiv5\\pmod {12}
17≡5(mod12)
因为：
17
−
5
=
12
17-5=12
17−5=12
同余不是“两个数比较接近”，而是说它们在模
q
q
q 的计算中属于同一个剩余类。于是：
−
1
≡
q
−
1
(
m
o
d
q
)
-1\\equiv q-1\\pmod q
−1≡q−1(modq)
q
+
2
≡
2
(
m
o
d
q
)
q+2\\equiv2\\pmod q
q+2≡2(modq)
2
q
−
3
≡
q
−
3
(
m
o
d
q
)
2q-3\\equiv q-3\\pmod q
2q−3≡q−3(modq)
我们通常使用
0
,
1
,
…
,
q
−
1
0,1,\\ldots,q-1
0,1,…,q−1 表示这些剩余类，并写成：
Z
q
=
Z
/
q
Z
\\mathbb Z_q=\\mathbb Z/q\\mathbb Z
Zq=Z/qZ
模加法和模乘法分别为：
(
a
+
b
)
m
o
d
q
(a+b)\\bmod q
(a+b)modq
(
a
b
)
m
o
d
q
(ab)\\bmod q
(ab)modq
模加法运算规则：
(
a
+
b
)
m
o
d
q
=
[
(
a
m
o
d
q
)
+
(
b
m
o
d
q
)
]
m
o
d
q
(a+b)\\bmod q = \\big[(a\\bmod q)+(b\\bmod q)\\big]\\bmod q
(a+b)modq=[(amodq)+(bmodq)]modq
模乘法运算规则：
(
a
b
)
m
o
d
q
=
(
(
a
m
o
d
q
)
(
b
m
o
d
q
)
)
m
o
d
q
(ab)\\bmod q= \\big((a\\bmod q)(b\\bmod q)\\big)\\bmod q
(ab)modq=((amodq)(bmodq))modq
计算过程中可以随时约简，不必等到一个巨大整数产生后再取模，可以在中间步骤不断把系数拉回有限范围，避免数值过大带来的运算压力与溢出问题。
2.2 为什么同一个系数有两种写法
先把模运算想象成钟表。钟表只有
12
12
12 个刻度，指针从
11
11
11 点继续往前走
2
2
2 格，会回到
1
1
1 点，因此可以写成：
11
+
2
≡
1
(
m
o
d
12
)
11+2\\equiv1\\pmod {12}
11+2≡1(mod12)
如果允许用“向后走”来表示位置，那么
11
11
11 点也可以写成
−
1
-1
−1 点。因为从
12
12
12 点的位置往回走
1
1
1 格，仍然会落在
11
11
11 点：
11
≡
−
1
(
m
o
d
12
)
11\\equiv-1\\pmod {12}
11≡−1(mod12)
模
q
q
q 的数字也是如此。相差整数个
q
q
q 的数字，在模
q
q
q 的计算中表示同一个位置：
a
≡
a
+
q
≡
a
−
q
(
m
o
d
q
)
a\\equiv a+q\\equiv a-q\\pmod q
a≡a+q≡a−q(modq)
以模
17
17
17 为例：
16
≡
−
1
(
m
o
d
17
)
16\\equiv-1\\pmod {17}
16≡−1(mod17)
因为：
16
−
(
−
1
)
=
17
16-(-1)=17
16−(−1)=17
所以，
16
16
16 和
−
1
-1
−1 不是两个不同的模
17
17
17 元素，而是同一个元素的两种写法。同理：
15
≡
−
2
(
m
o
d
17
)
15\\equiv-2\\pmod {17}
15≡−2(mod17)
9
≡
−
8
(
m
o
d
17
)
9\\equiv-8\\pmod {17}
9≡−8(mod17)
实际使用时，通常根据目的选择不同写法。
第一种是非负表示，适合存储和传输。
程序和密码协议通常把模
q
q
q 的元素统一表示为：
{
0
,
1
,
2
,
…
,
q
−
1
}
\\{0,1,2,\\ldots,q-1\\}
{0,1,2,…,q−1}
因此在模
17
17
17 中，
−
1
-1
−1 通常不会直接存储为负数，而是存储为
16
16
16；
−
2
-2
−2 存储为
15
15
15。这样每个元素都有唯一的非负编码。
第二种是中心化表示，适合分析大小。
分析秘密或噪声时，我们关心的不是它采用了哪个编号，而是它距离
0
0
0 有多远。此时会把元素改写成最接近
0
0
0 的那个整数。通常选择区间：
[
−
q
2
,
q
2
)
\\left[-\\frac q2,\\frac q2\\right)
[−2q,2q)
当
q
=
17
q=17
q=17 时，可使用的整数就是：
{
−
8
,
−
7
,
…
,
−
1
,
0
,
1
,
…
,
7
,
8
}
\\{-8,-7,\\ldots,-1,0,1,\\ldots,7,8\\}
{−8,−7,…,−1,0,1,…,7,8}
于是：
16
↦
16
−
17
=
−
1
16\\mapsto16-17=-1
16↦16−17=−1
15
↦
15
−
17
=
−
2
15\\mapsto15-17=-2
15↦15−17=−2
9
↦
9
−
17
=
−
8
9\\mapsto9-17=-8
9↦9−17=−8
这不是把元素改掉了，只是换了一种更适合观察的写法。比如：
16
+
3
≡
2
(
m
o
d
17
)
16+3\\equiv2\\pmod {17}
16+3≡2(mod17)
如果先把
16
16
16 换成中心化表示
−
1
-1
−1，计算就变成：
−
1
+
3
=
2
-1+3=2
−1+3=2
结果完全相同，但“
16
16
16 其实只是距离
0
0
0 一格”这件事会更加清楚。
因此，后量子密码中说某个秘密系数或误差系数“很小”时，通常是在中心化表示下说的。存储时它可能是
16
16
16，分析时则写成
−
1
-1
−1，它的大小应当记为：
∣
−
1
∣
=
1
|{-1}|=1
∣−1∣=1
而不是
16
16
16。
2.3 环、域与逆元
在普通整数中，只要除数不为零就能讨论除法；模运算中，除法必须通过乘法逆元实现。若存在
a
−
1
a^{-1}
a−1 满足：
a
a
−
1
≡
1
(
m
o
d
q
)
aa^{-1}\\equiv1\\pmod q
aa−1≡1(modq)
则
a
−
1
a^{-1}
a−1 称为
a
a
a 的模逆元，并且可以写：
b
a
≡
b
a
−
1
(
m
o
d
q
)
\\frac ba\\equiv ba^{-1}\\pmod q
ab≡ba−1(modq)
逆元存在的条件是：
gcd
(
a
,
q
)
=
1
\\gcd(a,q)=1
gcd(a,q)=1
例如在模
7
7
7 下：
3
−
1
≡
5
(
m
o
d
7
)
3^{-1}\\equiv5\\pmod7
3−1≡5(mod7)
因为：
3
×
5
=
15
≡
1
(
m
o
d
7
)
3\\times5=15\\equiv1\\pmod7
3×5=15≡1(mod7)
当
q
q
q 是质数时，
Z
q
\\mathbb Z_q
Zq 中每个非零元素都存在逆元，此时它构成有限域，常记作：
F
q
\\mathbb F_q
Fq
但当模数为合数时，情况不再成立。例如在
Z
6
\\mathbb Z_6
Z6 中，
2
2
2 没有乘法逆元，因为不存在
x
x
x 使：
2
x
≡
1
(
m
o
d
6
)
2x\\equiv1\\pmod6
2x≡1(mod6)
因此需要区分：
- 环允许加、减、乘，但非零元素不一定可除；
- 域在此基础上保证每个非零元素都有乘法逆元。
这个区别会延续到多项式中。即便系数来自有限域，多项式取模之后得到的整体结构也可能只是环，而不是域。
三、多项式环：格密码真正进行计算的地方
3.1 从系数模
q
q
q 到多项式模
f
(
x
)
f(x)
f(x)
系数属于
Z
q
\\mathbb Z_q
Zq 的多项式集合记作：
Z
q
[
x
]
\\mathbb Z_q[x]
Zq[x]
其中的一个多项式可以写成：
a
(
x
)
=
a
0
+
a
1
x
+
⋯
+
a
d
x
d
,
a
i
∈
Z
q
a(x)=a_0+a_1x+\\cdots+a_dx^d, \\qquad a_i\\in\\mathbb Z_q
a(x)=a0+a1x+⋯+adxd,ai∈Zq
如果只要求系数模
q
q
q，多项式次数仍可能随着乘法不断增长。为了让计算对象始终保持固定长度，还要再选择一个模多项式。例如格密码中常见：
R
q
=
Z
q
[
x
]
/
(
x
n
+
1
)
R_q=\\mathbb Z_q[x]/(x^n+1)
Rq=Zq[x]/(xn+1)
这个记号同时规定了两条规则：
q
q
q 约简；
x
n
+
1
x^n+1
xn+1 约简。
因为：
x
n
+
1
≡
0
(
m
o
d
x
n
+
1
)
x^n+1\\equiv0\\pmod{x^n+1}
xn+1≡0(modxn+1)
所以：
x
n
≡
−
1
(
m
o
d
x
n
+
1
)
x^n\\equiv-1\\pmod{x^n+1}
xn≡−1(modxn+1)
继续乘以
x
x
x，可得：
x
n
+
1
≡
−
x
x^{n+1}\\equiv-x
xn+1≡−x
x
n
+
2
≡
−
x
2
x^{n+2}\\equiv-x^2
xn+2≡−x2
所有次数不小于
n
n
n 的项都会折回低次位置，并且在跨过
x
n
x^n
xn 时带上负号。因此，
R
q
R_q
Rq 中每个元素最终都能用不超过
n
−
1
n-1
n−1 次的多项式表示：
a
(
x
)
=
a
0
+
a
1
x
+
⋯
+
a
n
−
1
x
n
−
1
a(x)=a_0+a_1x+\\cdots+a_{n-1}x^{n-1}
a(x)=a0+a1x+⋯+an−1xn−1
固定次数让多项式可以作为固定长度数据处理，也让向量化、矩阵化和快速变换成为可能。
3.2 完整算一次多项式乘法
在下面这个教学用小环中：
R
7
=
Z
7
[
x
]
/
(
x
4
+
1
)
R_7=\\mathbb Z_7[x]/(x^4+1)
R7=Z7[x]/(x4+1)
计算：
(
x
3
+
2
x
+
1
)
(
x
2
+
3
x
+
4
)
(x^3+2x+1)(x^2+3x+4)
(x3+2x+1)(x2+3x+4)
先按照普通多项式乘法展开：
(
x
3
+
2
x
+
1
)
(
x
2
+
3
x
+
4
)
=
x
3
(
x
2
+
3
x
+
4
)
+
2
x
(
x
2
+
3
x
+
4
)
+
(
x
2
+
3
x
+
4
)
=
x
5
+
3
x
4
+
4
x
3
+
2
x
3
+
6
x
2
+
8
x
+
x
2
+
3
x
+
4
=
x
5
+
3
x
4
+
6
x
3
+
7
x
2
+
11
x
+
4
\\begin{aligned} &(x^3+2x+1)(x^2+3x+4)\\\\ ={}&x^3(x^2+3x+4)\\\\ &+2x(x^2+3x+4)\\\\ &+(x^2+3x+4)\\\\ ={}&x^5+3x^4+4x^3\\\\ &+2x^3+6x^2+8x\\\\ &+x^2+3x+4\\\\ ={}&x^5+3x^4+6x^3+7x^2+11x+4 \\end{aligned}
===(x3+2x+1)(x2+3x+4)x3(x2+3x+4)+2x(x2+3x+4)+(x2+3x+4)x5+3x4+4x3+2x3+6x2+8x+x2+3x+4x5+3x4+6x3+7x2+11x+4
由于模多项式是
x
4
+
1
x^4+1
x4+1，所以：
x
4
≡
−
1
x^4\\equiv-1
x4≡−1
x
5
=
x
⋅
x
4
≡
−
x
x^5=x\\cdot x^4\\equiv-x
x5=x⋅x4≡−x
代回原式：
x
5
+
3
x
4
+
6
x
3
+
7
x
2
+
11
x
+
4
≡
−
x
−
3
+
6
x
3
+
7
x
2
+
11
x
+
4
=
6
x
3
+
7
x
2
+
10
x
+
1
\\begin{aligned} x^5+3x^4+6x^3+7x^2+11x+4 &\\equiv -x-3+6x^3+7x^2+11x+4\\\\ &=6x^3+7x^2+10x+1 \\end{aligned}
x5+3x4+6x3+7x2+11x+4≡−x−3+6x3+7x2+11x+4=6x3+7x2+10x+1
最后把系数模
7
7
7：
7
≡
0
(
m
o
d
7
)
,
10
≡
3
(
m
o
d
7
)
7\\equiv0\\pmod7, \\qquad 10\\equiv3\\pmod7
7≡0(mod7),10≡3(mod7)
因此结果为：
(
x
3
+
2
x
+
1
)
(
x
2
+
3
x
+
4
)
≡
6
x
3
+
3
x
+
1
(x^3+2x+1)(x^2+3x+4) \\equiv6x^3+3x+1
(x3+2x+1)(x2+3x+4)≡6x3+3x+1
这一步计算体现了多项式环中的两次约简：先利用
x
4
≡
−
1
x^4\\equiv-1
x4≡−1 约简次数，再对每个系数模
7
7
7。
3.3 卷积为什么会“折返并变号”
设：
a
(
x
)
=
∑
i
=
0
n
−
1
a
i
x
i
a(x)=\\sum_{i=0}^{n-1}a_ix^i
a(x)=i=0∑n−1aixi
b
(
x
)
=
∑
j
=
0
n
−
1
b
j
x
j
b(x)=\\sum_{j=0}^{n-1}b_jx^j
b(x)=j=0∑n−1bjxj
普通乘积为：
a
(
x
)
b
(
x
)
=
∑
i
=
0
n
−
1
∑
j
=
0
n
−
1
a
i
b
j
x
i
+
j
a(x)b(x)= \\sum_{i=0}^{n-1}\\sum_{j=0}^{n-1}a_ib_jx^{i+j}
a(x)b(x)=i=0∑n−1j=0∑n−1aibjxi+j
若暂时不考虑模多项式，乘积中
x
k
x^k
xk 的系数是：
d
k
=
∑
i
+
j
=
k
a
i
b
j
d_k=\\sum_{i+j=k}a_ib_j
dk=i+j=k∑aibj
这就是离散卷积：输出位置
k
k
k 汇总所有下标和等于
k
k
k 的系数乘积。
进入
R
q
=
Z
q
[
x
]
/
(
x
n
+
1
)
R_q=\\mathbb Z_q[x]/(x^n+1)
Rq=Zq[x]/(xn+1) 后，对于
i
+
j
≥
n
i+j\\ge n
i+j≥n 的项，有：
x
i
+
j
=
x
i
+
j
−
n
x
n
≡
−
x
i
+
j
−
n
x^{i+j}=x^{i+j-n}x^n\\equiv-x^{i+j-n}
xi+j=xi+j−nxn≡−xi+j−n
因此，最终第
k
k
k 个系数可以写成：
c
k
=
∑
i
+
j
=
k
a
i
b
j
−
∑
i
+
j
=
k
+
n
a
i
b
j
(
m
o
d
q
)
c_k =\\sum_{i+j=k}a_ib_j -\\sum_{i+j=k+n}a_ib_j \\pmod q
ck=i+j=k∑aibj−i+j=k+n∑aibj(modq)
第一部分来自没有越过次数边界的项，第二部分来自越界后折回并变号的项。这种运算称为负循环卷积。
需要特别注意，它不是逐项相乘。一般情况下：
(
a
0
,
a
1
,
…
)
⋅
(
b
0
,
b
1
,
…
)
≠
(
a
0
b
0
,
a
1
b
1
,
…
)
(a_0,a_1,\\ldots)\\cdot(b_0,b_1,\\ldots) \\ne (a_0b_0,a_1b_1,\\ldots)
(a0,a1,…)⋅(b0,b1,…)=(a0b0,a1b1,…)
一个输出系数通常会同时受到多个输入系数影响。标准算法实现中常使用 NTT 将卷积转换为更高效的点值乘法，但 NTT 优化没有改变环乘法本身的数学结果。
四、从一个多项式到矩阵和向量
4.1 多项式与系数向量是同一个对象的两种视角
次数小于
n
n
n 的多项式：
a
(
x
)
=
a
0
+
a
1
x
+
⋯
+
a
n
−
1
x
n
−
1
a(x)=a_0+a_1x+\\cdots+a_{n-1}x^{n-1}
a(x)=a0+a1x+⋯+an−1xn−1
可以直接对应为系数向量：
a
(
x
)
⟷
(
a
0
a
1
⋮
a
n
−
1
)
a(x) \\longleftrightarrow \\begin{pmatrix} a_0\\\\ a_1\\\\ \\vdots\\\\ a_{n-1} \\end{pmatrix}
a(x)⟷
a0a1⋮an−1
例如：
3
+
2
x
+
5
x
3
⟷
(
3
,
2
,
0
,
5
)
T
3+2x+5x^3 \\longleftrightarrow (3,2,0,5)^T
3+2x+5x3⟷(3,2,0,5)T
这不是把多项式“近似”成向量，而是更换表示方式。多项式强调代数运算，向量强调系数排列，信息没有丢失。
固定一个多项式
a
(
x
)
a(x)
a(x) 后，映射：
b
(
x
)
↦
a
(
x
)
b
(
x
)
m
o
d
(
x
n
+
1
)
b(x)\\mapsto a(x)b(x)\\bmod(x^n+1)
b(x)↦a(x)b(x)mod(xn+1)
对
b
(
x
)
b(x)
b(x) 的系数是线性的，因此可以写成矩阵乘法。以
n
=
4
n=4
n=4 为例：
(
c
0
c
1
c
2
c
3
)
=
(
a
0
−
a
3
−
a
2
−
a
1
a
1
a
0
−
a
3
−
a
2
a
2
a
1
a
0
−
a
3
a
3
a
2
a
1
a
0
)
(
b
0
b
1
b
2
b
3
)
(
m
o
d
q
)
\\begin{pmatrix} c_0\\\\ c_1\\\\ c_2\\\\ c_3 \\end{pmatrix}= \\begin{pmatrix} a_0&-a_3&-a_2&-a_1\\\\ a_1&a_0&-a_3&-a_2\\\\ a_2&a_1&a_0&-a_3\\\\ a_3&a_2&a_1&a_0 \\end{pmatrix} \\begin{pmatrix} b_0\\\\ b_1\\\\ b_2\\\\ b_3 \\end{pmatrix} \\pmod q
c0c1c2c3
=
a0a1a2a3−a3a0a1a2−a2−a3a0a1−a1−a2−a3a0
b0b1b2b3
(modq)
矩阵右上区域的负号，正是高次项按照
x
4
≡
−
1
x^4\\equiv-1
x4≡−1 折返产生的。由此可以看出：
多项式环不是与线性代数无关的另一套系统；一次环乘法，本身就可以看作一种具有特殊结构的线性变换。
4.2 模块格中的“矩阵元素”仍然是多项式
只使用一个多项式仍然难以同时兼顾安全性、性能和密钥尺寸。模块格方案会进一步把多个环元素组成向量和矩阵。例如：
A
∈
R
q
k
×
k
\\mathbf A\\in R_q^{k\\times k}
A∈Rqk×k
s
,
e
,
t
∈
R
q
k
\\mathbf s,\\mathbf e,\\mathbf t\\in R_q^k
s,e,t∈Rqk
假设
k
=
2
k=2
k=2，则：
A
=
(
a
00
(
x
)
a
01
(
x
)
a
10
(
x
)
a
11
(
x
)
)
\\mathbf A= \\begin{pmatrix} a_{00}(x)&a_{01}(x)\\\\ a_{10}(x)&a_{11}(x) \\end{pmatrix}
A=(a00(x)a10(x)a01(x)a11(x))
s
=
(
s
0
(
x
)
s
1
(
x
)
)
\\mathbf s= \\begin{pmatrix} s_0(x)\\\\ s_1(x) \\end{pmatrix}
s=(s0(x)s1(x))
矩阵向量乘法展开为：
A
s
=
(
a
00
(
x
)
s
0
(
x
)
+
a
01
(
x
)
s
1
(
x
)
a
10
(
x
)
s
0
(
x
)
+
a
11
(
x
)
s
1
(
x
)
)
\\mathbf A\\mathbf s= \\begin{pmatrix} a_{00}(x)s_0(x)+a_{01}(x)s_1(x)\\\\ a_{10}(x)s_0(x)+a_{11}(x)s_1(x) \\end{pmatrix}
As=(a00(x)s0(x)+a01(x)s1(x)a10(x)s0(x)+a11(x)s1(x))
其中每一次乘法都要执行多项式卷积与模多项式约简，每一次加法都要对系数模
q
q
q。因此：
(
A
s
)
i
=
∑
j
=
0
k
−
1
a
i
j
(
x
)
s
j
(
x
)
(
m
o
d
(
q
,
x
n
+
1
)
)
(\\mathbf A\\mathbf s)_i= \\sum_{j=0}^{k-1}a_{ij}(x)s_j(x) \\pmod{(q,\\,x^n+1)}
(As)i=j=0∑k−1aij(x)sj(x)(mod(q,xn+1))
式中的
(
m
o
d
(
q
,
x
n
+
1
)
)
\\pmod{(q,\\,x^n+1)}
(mod(q,xn+1)) 是一种直观写法，强调系数和多项式次数都需要约简。
现在再看：
t
=
A
s
+
e
(
m
o
d
q
)
\\mathbf t=\\mathbf A\\mathbf s+\\mathbf e\\pmod q
t=As+e(modq)
就可以逐层展开为：
一个多项式向量
=
多项式矩阵
×
秘密多项式向量
+
误差多项式向量
\\text{一个多项式向量}= \\text{多项式矩阵} \\times \\text{秘密多项式向量} + \\text{误差多项式向量}
一个多项式向量=多项式矩阵×秘密多项式向量+误差多项式向量
这正是模块格算法中常见数据结构的数学来源。
五、范数：怎样描述秘密和噪声“足够小”
5.1 在模
q
q
q 的世界里衡量大小
“误差很小”不是一句凭感觉的描述，需要用范数给出边界。对于实向量：
x
=
(
x
1
,
x
2
,
…
,
x
n
)
\\mathbf x=(x_1,x_2,\\ldots,x_n)
x=(x1,x2,…,xn)
常见范数包括：
∥
x
∥
1
=
∑
i
=
1
n
∣
x
i
∣
\\|\\mathbf x\\|_1= \\sum_{i=1}^{n}|x_i|
∥x∥1=i=1∑n∣xi∣
∥
x
∥
2
=
∑
i
=
1
n
x
i
2
\\|\\mathbf x\\|_2= \\sqrt{\\sum_{i=1}^{n}x_i^2}
∥x∥2=i=1∑nxi2
∥
x
∥
∞
=
max
i
∣
x
i
∣
\\|\\mathbf x\\|_\\infty= \\max_i|x_i|
∥x∥∞=imax∣xi∣
取：
x
=
(
1
,
−
2
,
2
,
0
)
\\mathbf x=(1,-2,2,0)
x=(1,−2,2,0)
则：
∥
x
∥
1
=
5
\\|\\mathbf x\\|_1=5
∥x∥1=5
∥
x
∥
2
=
3
\\|\\mathbf x\\|_2=3
∥x∥2=3
∥
x
∥
∞
=
2
\\|\\mathbf x\\|_\\infty=2
∥x∥∞=2
三种范数回答的问题不同：
-
ℓ
1
\\ell_1
ℓ1 范数观察所有坐标绝对值之和； -
ℓ
2
\\ell_2
ℓ2 范数对应常见的欧氏距离； -
ℓ
∞
\\ell_\\infty
ℓ∞ 范数关注绝对值最大的那个坐标。
对于多项式：
a
(
x
)
=
a
0
+
a
1
x
+
⋯
+
a
n
−
1
x
n
−
1
a(x)=a_0+a_1x+\\cdots+a_{n-1}x^{n-1}
a(x)=a0+a1x+⋯+an−1xn−1
只需把系数视为向量即可定义范数。例如：
a
(
x
)
=
1
−
2
x
+
x
2
a(x)=1-2x+x^2
a(x)=1−2x+x2
对应系数向量
(
1
,
−
2
,
1
)
(1,-2,1)
(1,−2,1)，所以：
∥
a
∥
1
=
4
,
∥
a
∥
2
=
6
,
∥
a
∥
∞
=
2
\\|a\\|_1=4, \\qquad \\|a\\|_2=\\sqrt6, \\qquad \\|a\\|_\\infty=2
∥a∥1=4,∥a∥2=6
,∥a∥∞=2
如果系数存储在
0
0
0 到
q
−
1
q-1
q−1 之间，应先转换为中心化代表，再讨论绝对值和范数。否则，模
q
q
q 下的
−
1
-1
−1 会被误认为大小是
q
−
1
q-1
q−1。
5.2 小系数不等于小密钥空间
假设秘密多项式的每个系数只来自：
{
−
1
,
0
,
1
}
\\{-1,0,1\\}
{−1,0,1}
单看一个系数，确实只有三种可能；但若有
n
n
n 个相互组合的系数，候选总数为：
3
n
3^n
3n
若再把
k
k
k 个多项式组成秘密向量，理想化地看，候选数量会上升到：
3
k
n
3^{kn}
3kn
真实算法使用的是规定好的概率分布，系数不一定独立均匀，因此不能仅用这个式子计算正式安全强度。但它足以纠正一个常见误解：
“每个系数很小”只描述单个坐标的取值范围，不代表整个高维秘密容易穷举。
更重要的是，攻击者面对的通常不是可以逐坐标独立验证的密码，而是经过高维线性混合、模约简和噪声扰动后的整体关系。安全性来自结构化难题及其参数选择，而不是单纯把某个整数取得很大。
5.3 噪声为什么既不能没有，也不能失控
如果公开关系没有噪声：
t
=
A
s
(
m
o
d
q
)
\\mathbf t=\\mathbf A\\mathbf s\\pmod q
t=As(modq)
攻击者看到的是精确的线性关系。在满足相应可解条件时，可以尝试利用模线性代数恢复
s
\\mathbf s
s。
加入误差后：
t
=
A
s
+
e
(
m
o
d
q
)
\\mathbf t=\\mathbf A\\mathbf s+\\mathbf e\\pmod q
t=As+e(modq)
攻击者只能看到被扰动的结果。问题不再是求解一组精确方程，而是从大量近似关系中恢复共同秘密。这正是 LWE 一类问题的核心直觉。
但噪声并不是越大越好。算法需要同时满足两件相反的事：
- 对攻击者而言，噪声要足以掩盖精确线性关系；
- 对合法接收者而言，噪声又必须受控，不能淹没编码信息或破坏验证条件。
可以把参数设计理解为三方平衡：
安全性
⟷
正确性
⟷
性能与尺寸
\\text{安全性} \\quad\\longleftrightarrow\\quad \\text{正确性} \\quad\\longleftrightarrow\\quad \\text{性能与尺寸}
安全性⟷正确性⟷性能与尺寸
维度增大通常会带来更多计算和存储成本；误差增大可能提高某些攻击的难度，也可能增加解密失败或签名拒绝的概率；采样实现若泄露时间、分支或功耗特征，还可能引入侧信道问题。
因此，“小秘密 + 小噪声”不是随意挑几个小整数，而是算法标准经过安全分析后确定的概率分布和参数边界。
六、把所有概念重新装回公式
现在可以完整拆解：
t
=
A
s
+
e
(
m
o
d
q
)
\\mathbf t=\\mathbf A\\mathbf s+\\mathbf e\\pmod q
t=As+e(modq)
第一层，
A
\\mathbf A
A、
s
\\mathbf s
s、
e
\\mathbf e
e 和
t
\\mathbf t
t 是矩阵或向量：
t
i
(
x
)
=
∑
j
a
i
j
(
x
)
s
j
(
x
)
+
e
i
(
x
)
t_i(x)=\\sum_j a_{ij}(x)s_j(x)+e_i(x)
ti(x)=j∑aij(x)sj(x)+ei(x)
第二层，每个元素属于多项式环：
a
i
j
(
x
)
,
s
j
(
x
)
,
e
i
(
x
)
∈
R
q
a_{ij}(x),s_j(x),e_i(x)\\in R_q
aij(x),sj(x),ei(x)∈Rq
R
q
=
Z
q
[
x
]
/
(
x
n
+
1
)
R_q=\\mathbb Z_q[x]/(x^n+1)
Rq=Zq[x]/(xn+1)
第三层，一次多项式乘法是负循环卷积：
c
k
=
∑
i
+
j
=
k
a
i
b
j
−
∑
i
+
j
=
k
+
n
a
i
b
j
(
m
o
d
q
)
c_k= \\sum_{i+j=k}a_ib_j -\\sum_{i+j=k+n}a_ib_j \\pmod q
ck=i+j=k∑aibj−i+j=k+n∑aibj(modq)
第四层，所有系数最终都约简到模
q
q
q 的剩余类中：
c
k
∈
Z
q
c_k\\in\\mathbb Z_q
ck∈Zq
第五层，
s
\\mathbf s
s 和
e
\\mathbf e
e 的系数来自规定的小值分布，大小可通过中心化表示和范数分析。
把这五层连起来，原本抽象的公式就变成了一套明确的计算过程：
生成公开多项式矩阵 A
↓
采样小系数秘密向量 s
↓
执行多项式矩阵乘法 A·s
↓
加入小系数误差向量 e
↓
按 x^n + 1 约简次数，按 q 约简系数
↓
得到公开向量 t
不同后量子算法会改变矩阵维度、模数、采样分布、编码方式和安全变换，但这条代数主线会反复出现。
需要再强调一次：
t
=
A
s
+
e
\\mathbf t=\\mathbf A\\mathbf s+\\mathbf e
t=As+e 只是理解 LWE、Module-LWE 及其相关结构的入口，不是对 ML-KEM 或 ML-DSA 完整流程的替代。真实标准还包含随机种子展开、NTT 表示、压缩与解压缩、哈希、KDF、重加密检查、拒绝采样和严格的字节编码规则。
七、读完本文应该建立的数学直觉
本文不要求记住每一个术语的形式化定义，但需要建立以下判断：
q
q
q 不只是“算完取余”。 它定义了有限的系数空间，也决定了标准表示、中心化表示和逆元是否存在；
x
n
+
1
x^n+1
xn+1 下越界项会折返并变号；
下一篇将从数学对象转向密码接口，区分 PKE 与 KEM，并推演“带噪声的公开关系”如何真正参与加密、解密、封装和解封装。
