10-5-图形学与密码学
一句话概括
计算机图形学用 矩阵统一表示缩放、旋转、平移、错切与投影——引入第 4 维(齐次坐标,homogeneous coordinates)的唯一目的,是让"平移"这个不是线性变换的操作也能写成矩阵乘法;密码学中的希尔密码(Hill cipher)用模 下可逆的密钥矩阵 做加解密 。两者的共同点是:都在用矩阵做变换,正确性与安全性都归结为矩阵的可逆性。
本篇分两大部分:
图形学部分
- 为什么必须是 :齐次坐标的必要性(本篇最核心的洞察)
- 五种基本变换矩阵的完整列表(缩放、旋转、平移、错切、反射)
- 旋转矩阵的推导(展开 与 )
- 复合变换的顺序: 从右往左作用,顺序不同结果不同(数值演示)
- 法向量为什么要用逆转置矩阵 (配推导)
- 透视投影与正交投影
- 三维变换流水线:模型 → 世界 → 相机 → 裁剪 → 屏幕
密码学部分
- 希尔密码的原理与完整数值例子
- 密钥矩阵必须在模 26 下可逆:(配反例)
- RSA、中国剩余定理与线性代数
- 格密码与 LWE 的直觉
- 六道完整例题(旋转与反射的顺序、绕任意点缩放、点/方向/直线、法向量与光照、两条逆矩阵恒等式的证明、numpy 数值实验)
一、定义:为什么用 矩阵(齐次坐标的必要性)
1.1 问题的提出
三维图形的最基本操作是"把每个顶点的坐标变一下"。我们希望所有操作都能写成矩阵乘向量 ,因为矩阵乘法可以:
- 复合:连续做两个变换 一个矩阵(),一次乘法搞定;
- 硬件加速:GPU 就是为大规模矩阵乘法设计的;
- 统一管理:整条流水线都是矩阵。
但这里立刻遇到一个障碍。
定理 10.5.1(平移不是线性变换)
设 ()是平移。则 不是 上的线性变换。
证明 线性变换必须满足 (由 取 即得)。但
故 不线性。也可以直接验证可加性失效:
推论:不存在 矩阵 使 对所有 成立(否则 就是线性的)。
这就是核心矛盾:缩放、旋转是线性的(有 矩阵),平移不是线性的(没有 矩阵)——但平移在实践中和它们一样常用。
1.2 解决办法:升一维
把三维点 表示成四维向量
(最后一位固定为 ),然后取 矩阵
验证:
平移被实现了!
这一招的实质
在三维中不可行的操作,在四维中变成了线性操作。用第 8 章的语言:仿射变换(affine transformation)是高一维空间中的线性变换的"截面"。
更精确地说, 矩阵的左上 块负责线性部分,最后一列负责平移部分,最后一行 保证第 4 个分量恒为 。这类矩阵构成一个群,叫仿射群(affine group)。
1.3 齐次坐标的一般形式与"点"和"向量"的区分
一般地,齐次坐标写成 ,实际三维坐标是
(;这一除法叫透视除法,perspective division,第六节要用)。标量倍表示同一个点:
一个漂亮的副产品:第 4 分量区分"点"与"向量"。
| 对象 | 齐次表示 | 第 4 分量 | 平移矩阵作用的效果 |
|---|---|---|---|
| 点(point) | 被平移 ✓(点应该动) | ||
| 方向向量(direction) | 不变 ✓(方向不该动) |
验证(方向向量 ):
第 4 分量为 时,最后一列的 乘的正是这个 ,贡献为零,向量不被平移。这就是为什么"法向量、光照方向、速度"这类量都要用 表示。这个机制完全自动,不需要特判"这是个向量,别平移它"。
为什么叫"齐次"
因为表示不唯一: 与 表示同一个点。这种"相差一个非零倍数视为同一个对象"的结构,与射影空间(projective space)的构造一致。数学上,齐次坐标把 嵌入到射影空间 中,从而让无穷远点()也有了归宿——这也是透视投影中平行线"交于无穷远"的代数原因。
二、几何直观:基本变换矩阵完整列表
以下全部是 矩阵,作用在列向量 上(左乘)。记 、。
2.1 缩放(scaling)
几何效果:沿三个坐标轴分别按 倍拉伸/压缩。 为均匀缩放(保持形状),否则为非均匀缩放(会改变角度,例如把圆压成椭圆)。
非均匀缩放改变角度
非均匀缩放不是正交变换,它会破坏垂直关系(圆变椭圆),因此法向量必须用逆转置矩阵变换(第五节)。
2.2 绕坐标轴的旋转(rotation)
绕 轴转 :
绕 轴转 :
绕 轴转 :
绕 轴的矩阵"看起来"符号反了
注意 的右上角是 、左下角是 ,与 的排布相反。这不是笔误,而是右手坐标系的直接后果:从 轴正向往原点看时, 的方向与平面上的直觉相反。自己动手推一遍(见 2.6 节方法)就能确认。
2.3 平移(translation)
几何效果:整块图形沿向量 平移。唯一必须依赖第 4 维才能表示的变换。
2.4 错切(shear)
沿 方向、以 为参数的错切:
几何效果:把点 送到 。 越大的点被推得越远,正方形被"推"成平行四边形。它是保持体积()但不保持角度的变换。
三种错切()与它们的反向版本共六个,是图形学中把"任意矩阵分解为一串基本操作"的构件之一(任何一个 的矩阵都可分解为一系列错切与旋转)。
2.5 反射(reflection)
关于 平面的反射(即 ):
关于 平面的反射():
几何效果:镜像。注意 ——反射改变手性(左手系变右手系),这是它与旋转()的本质区别。在图形学中,若模型矩阵的 ,三角形顶点的环绕顺序(winding order)会翻转,可能被错误地剔除(culling),需要额外处理。
2.6 旋转矩阵的推导
以绕 轴为例。设旋转角为 (逆时针,右手系)。要找 矩阵(三维情形把 行/列补成单位)满足
第 1 步:看基向量去哪。 线性变换由它在基向量上的作用唯一确定(这是第 8 章的核心,见 8-1-线性变换的思想)。设 的第 1 列是 、第 2 列是 。
第 2 步:。 是 轴上的单位向量,长度为 、与 轴夹角为 。逆时针转 后,它仍然是单位向量,但与 轴夹角变成 ,故坐标为
(这就是单位圆上角度为 的点,也是 与 的几何定义。)
第 3 步:。 与 轴夹角为 (即 )。转 后夹角为 ,故
最后一步用了和角公式(这才是旋转矩阵里出现 组合的真正原因):
第 4 步:把两列拼起来。
第 5 步:数值验证()。
第 6 步:旋转矩阵的三条重要性质。
- 正交矩阵(orthogonal matrix):,故 。反向旋转就是转置,计算上极其便宜(不用求逆)。
- (保体积、保手性)。
- 保长度与保角度:、。见 4-4-标准正交基与Gram-Schmidt。
2.7 五种变换的对比总表
| 变换 | 矩阵的左上 块 | 是否用第 4 列 | 行列式 | 保长度 | 保角度 | 保持手性 | 说明 |
|---|---|---|---|---|---|---|---|
| 缩放(均匀) | 否 | 否(除 ) | 是 | 时是 | 形状不变,大小变 | ||
| 缩放(非均匀) | 否 | 否 | 否 | 视符号 | 圆变椭圆 | ||
| 旋转 | 正交, | 否 | 是 | 是 | 是 | 刚体转动 | |
| 平移 | 是 | 是 | 是 | 是 | 唯一必需第 4 维者 | ||
| 错切 | 单位三角阵 | 否 | 否 | 否 | 是 | 保体积不保角 | |
| 反射 | 正交, | 否 | 是 | 是 | 否 | 镜像 | |
| 正交投影 | 降秩矩阵 | 否 | 否 | 否 | 否 | 不可逆 | |
| 透视投影 | 非仿射(第 4 行非 ) | 是 | 0 | 否 | 否 | 否 | 需透视除法 |
三、性质与定理:复合变换的顺序
3.1 从右往左作用
设要对点 依次施加:先缩放 、再旋转 、最后平移 。写成矩阵:
记忆规则:矩阵从右往左作用在向量上,最右边的最先作用。 因为矩阵乘法结合,可以先算出
然后对所有顶点一律用 ——这就是图形学里"把变换烘焙进一个矩阵"的做法,效率的关键。注意这里的书写顺序 与作用顺序相反:
| 代码里的写法 | 实际作用顺序 | 记忆口诀 |
|---|---|---|
M = T @ R @ S | 先 ,再 ,最后 | "读从右到左" |
M = S @ R @ T | 先 ,再 ,最后 | 顺序完全相反,结果不同 |
矩阵乘法不交换
一般来说 。唯一"安全"的情形是同一类型变换之间(如两个平移、两个同轴旋转、两个同为对角阵的缩放),它们互相交换。
3.2 数值演示:两种顺序的差异
取
具体矩阵(,):
顺序 A:先缩放、再旋转、最后平移,即 。
第 1 步( 作用):
第 2 步( 作用):
第 3 步( 作用):
顺序 B:先平移、再旋转、最后缩放,即 (注意作用顺序是先 、再 、最后 )。
第 1 步( 作用):
第 2 步( 作用):
第 3 步( 作用,翻倍):
结果对比:
| 顺序 | 矩阵写法 | 作用顺序 | 结果 |
|---|---|---|---|
| A | 缩放 → 旋转 → 平移 | ||
| B | 平移 → 旋转 → 缩放 |
两点距离:
差了将近 4 个单位——顺序不仅影响结果,而且影响巨大。(顺带注意:顺序 A 里缩放没有放大平移量,因为 在最左边;顺序 B 里缩放把平移后的位置整体放大了 2 倍。这就是"平移量会被外层的缩放放大"这一常见 bug 的来源。)
常见实践约定
- 是最常用的顺序:先把模型摆正(缩放、旋转),再放到场景中的位置(平移)。若反过来,平移量会被缩放系数放大,通常不是想要的效果。
- 绕任意点旋转要先平移到原点、旋转、再平移回去:。这是 模式的一个特例("把旋转中心搬到原点")。
- 不同图形 API 在投影矩阵和深度范围的约定上不同(例如 NDC 的 范围有 与 两派),跨 API 移植时要核对,以所用库的官方文档为准。
- 欧拉角的旋转顺序约定(XYZ、ZYX、YXZ…)在不同软件中不同,且存在万向节死锁(gimbal lock)。这就是为什么动画系统常用四元数(quaternion)表示旋转——它是 维单位球面上的点,比 矩阵省空间且便于插值。
四、计算方法与步骤:法向量、投影与变换流水线
4.1 问题的提出
若顶点按 变换,法向量 应该怎么变?直觉答案"也用 "是错的。
反例:取非均匀缩放 ( 方向拉伸 2 倍),并取法向量 。
- 若直接用 :。
- 而正确的法向量应该是 的方向(见 4.3 节验算)。
为什么会错?因为法向量不是"点",而是"约束":它描述的是"曲面在这点朝哪个方向"。点被拉伸时,法向量要"反向"调整以保持垂直关系。
4.2 推导
设定。设 是一张曲面(或平面),在点 处有切向量 ,法向量 满足
(这是"垂直"的代数表述,见 1-2-长度与点积。)
变换后的要求。变换后:新曲面在 处,切向量变成
(切向量是"点的差"或"曲线的导数",作为方向向量它随 一起变换,这是正确的。)我们要求新的法向量 与新的切向量垂直:
求解。我们希望上式由已知的 推出,即希望
(第一步两边转置;第二步左乘 ,用到 可逆。)取 (长度无所谓,法向量只需要方向),得到
这就是"逆转置矩阵"(inverse transpose)的来历。
适用条件: 必须可逆。若 奇异(如投影矩阵),则法向量变换需要特殊处理(通常用伴随矩阵或先做逆转置、再处理退化情形)。
4.3 验算
仍取 ,。
(对角矩阵的逆转置就是取倒数,所以 分量从 变成 ——拉伸方向上的法向量分量被压缩,这正是"反向调整"。)
垂直性验证。取原切向量 、,两者都与 正交:
变换后:,。检查与 的垂直性:
用 直接变换则失败:
几何解释: 把 拉伸 2 倍,原本"斜 45°"的法向量 应该变成"更平"的 ,而 变得更陡——完全错的方向。
两个特例
- 若 是旋转:,故 。旋转矩阵下法向量和普通向量一样变换——这解释了为什么很多人在只用旋转时从没发现这个坑。
- 若 是均匀缩放 :,只改变长度不改变方向,所以看起来"也没问题"。只有非均匀缩放或错切才会暴露错误。
4.4 投影矩阵
4.4.1 正交投影(orthographic projection)
最简单的正交投影:把三维投影到 平面上(沿 方向平行投影):
作用:。——投影矩阵一定不可逆(信息被丢掉了, 无法恢复)。这正是 4-2-投影与投影矩阵 中"、 降秩、 是到正交补的投影"的直接体现。
带视景体的正交投影(用于 CAD、建筑图)把轴对齐的盒子 线性映射到标准立方体 :
它是仿射变换(最后一行仍是 ),保持平行线仍然平行。
4.4.2 透视投影(perspective projection)
透视的关键是远处的物体看起来小,即
这个映射不是线性的(出现除法),但用齐次坐标可以写成矩阵乘法加一次除法!取 矩阵
验证:
注意这个矩阵的最后一行是 ,不再是 ——它把深度 搬到第 4 分量上,为随后的透视除法(perspective division,)做准备。
完整的透视投影矩阵(把视锥映射到标准立方体,约定 为近/远平面深度):
要点:
- 左上的非对角项 、 是把视锥的不对称性(视线不在正中间)编码进去,这叫离轴投影(off-axis projection),是 VR 双眼渲染的关键;
- 最后一行 表明 ,即深度越远, 越大,除法后坐标越小——直观的"近大远小";
- 这个矩阵本身是可逆的。按底行 展开(该行只有一个非零元),余子式恰好是左上 块,而它是上三角的:
数值核对:取 、、、,得
与 numpy.linalg.det 输出的 -1.0202020202020203 完全一致 ✓。只要 、、,就有 , 存在。
- 它为什么可逆: 把深度完整地保存在第 4 分量里,所以信息没有丢失;而且 与 之间是一一对应的(见下面的提示框)。
纠一个流传很广的说法:"透视投影矩阵 "
需要把三个不同的矩阵分清——本篇 4.4.2 节的"最简透视矩阵"恰好是最特殊的那一个:
| 矩阵 | 形式 | 行列式 | 秩 | 是否可逆 |
|---|---|---|---|---|
| 4.4.2 节的最简透视 | 单位矩阵把第 4 行改成 | | | 不可逆 |
| 真实投影矩阵 (上式) | 见上 | | | 可逆 |
| 正交投影(把 压成 ) | | | | 不可逆 |
最简透视矩阵之所以奇异,是因为它把整个 方向压成了同一个深度。 看它的第 4 分量:, 在除法中被约掉,输出的深度恒为 ——深度信息真的丢了。
真实的投影矩阵不同:它把 编码进 :
由此可以反解出深度:
这就是深度缓冲(z-buffer)能工作的数学基础:屏幕上的每个像素都带着一个可恢复的深度值。"除以 "这一步是多对一的降维(一条视线上的点映到同一像素),它才是真正不可逆的那一步——而它根本不是矩阵乘法,所以谈不上"矩阵奇异"。
实践后果:不要因为"投影不可逆"就以为不能对投影矩阵求逆——真实的视图/投影矩阵在裁剪空间里可逆,可以放心做反投影(例如从屏幕坐标反算世界坐标,用于拾取、阴影贴图);只是必须额外提供深度 ,因为它在投影后被降成了一个附加坐标。
那"不能对透视投影后的法向量用逆转置"这句话对不对? 对,但理由要改:法向量必须在投影之前的空间里变换(那时矩阵是模型视图矩阵的 部分,可逆),一旦做过透视除法,法向量的"垂直"含义已经在二维屏幕空间里失效了(第四节 4.3 节的验算依赖的是三维内积)。所以流水线里算光照,一定要在投影之前。
正交与透视的对比:
| 项目 | 正交投影 | 透视投影 |
|---|---|---|
| 第 4 行 | ||
| 是否仿射 | 是 | 否 |
| 平行线 | 保持平行 | 汇聚到消失点 |
| 远处物体 | 大小不变 | 变小 |
| 是否需要透视除法 | 否 | 是 |
| 典型用途 | CAD、工程图、2D 游戏 | 3D 游戏、VR、电影 |
| 深度信息 | 线性保留 | 非线性(精度集中在近处) |
五、三维变换流水线
一个顶点从模型坐标走到屏幕像素,要经过五次矩阵乘法(加一次除法):
| 阶段 | 输入 | 变换 | 输出空间 | 矩阵 |
|---|---|---|---|---|
| 1. 模型变换 | 模型局部坐标 | 摆放到场景 | 世界坐标(world) | |
| 2. 视图变换 | 世界坐标 | 以相机为原点 | 相机/视空间(view) | |
| 3. 投影变换 | 相机坐标 | 视锥 → 标准立方体 | 裁剪空间(clip) | |
| 4. 透视除法 | 齐次坐标 | 除以 | 标准化设备坐标 NDC | (不是矩阵) |
| 5. 视口变换 | NDC | 映射到像素 | 屏幕坐标(screen) |
合并写法(图形学中无处不在的一行公式):
其中 通常就是前面讲的 。整条流水线从右往左读:模型 → 世界 → 相机 → 裁剪。
几个值得注意的线性代数事实:
- 每一步都是矩阵(第 4 步除外),所以可以预先合并成 ,对每个顶点只做一次 乘法。这是 GPU 性能的基础。
- :视图矩阵本质是"把相机变换的逆作用到世界上",等价于把整个世界反向移动,使相机落到原点、朝向 。求逆在这里有明确的几何含义。
- 裁剪空间的第 4 分量 同时充当"深度索引",裁剪(clipping)的条件是 ,写成齐次形式是为了在除法之前就剔除不可见的顶点(避免 或 导致的除零与翻转)。
- 法向量在每个阶段都要用对应的逆转置矩阵变换(第四节的结论),但投影阶段例外(因为 奇异)。
六、例题:图形学数值验算与代码
以下示例只用 numpy。
import numpy as np
# ---------- 基础构造函数:全部返回 4x4 矩阵 ----------
# 约定:scale 既可传单个标量(各向同性缩放),也可传 (sx, sy, sz) 三元组。
def translate(a):
T = np.eye(4)
T[0:3, 3] = a
return T
def scale(s):
S = np.eye(4)
if np.isscalar(s):
sx = sy = sz = s
else:
sx, sy, sz = s
S[0, 0], S[1, 1], S[2, 2] = sx, sy, sz
return S
def rotate_z(theta):
c, s = np.cos(theta), np.sin(theta)
R = np.eye(4)
R[0, 0], R[0, 1] = c, -s
R[1, 0], R[1, 1] = s, c
return R
def shear_xy(k):
H = np.eye(4)
H[0, 1] = k
return H
def reflect_xy():
R = np.eye(4)
R[2, 2] = -1
return R
# ---------- 1. 旋转矩阵的推导验证:R e1 与 R e2 ----------
th = np.pi / 6 # 30 度
R = rotate_z(th)
e1 = np.array([1.0, 0, 0, 1])
e2 = np.array([0, 1.0, 0, 1])
print("R e1 =", np.round(R @ e1, 6), " 理论 (cos30, sin30, 0) =", (round(np.cos(th), 6), round(np.sin(th), 6)))
print("R e2 =", np.round(R @ e2, 6), " 理论 (-sin30, cos30, 0) =", (round(-np.sin(th), 6), round(np.cos(th), 6)))
print("R^T R = I ?", np.allclose(R.T @ R, np.eye(4)))
print("det R =", round(np.linalg.det(R), 12))
# ---------- 2. 复合顺序:TRS 与 SRT 的差异 ----------
p = np.array([1.0, 0, 0, 1])
T = translate([3.0, 1.0, 0.0])
S = scale(2.0)
M_TRS = T @ R @ S # 先缩放、再旋转、最后平移
M_SRT = S @ R @ T # 先平移、再旋转、最后缩放
print("\nTRS @ p =", np.round(M_TRS @ p, 6)) # 期望 [4.732051, 2, 0, 1]
print("SRT @ p =", np.round(M_SRT @ p, 6)) # 期望 [5.928203, 5.732051, 0, 1]
print("TRS == SRT ?", np.allclose(M_TRS, M_SRT))
# ---------- 3. 平移不改变方向向量(w = 0) ----------
d = np.array([1.0, 1.0, 0.0, 0.0]) # 方向向量,w = 0
print("\nT @ 点 =", np.round(T @ np.array([1.0, 1.0, 0.0, 1.0]), 6), " (点被平移)")
print("T @ 方向 =", np.round(T @ d, 6), " (方向不变)")
# ---------- 4. 法向量的逆转置变换 ----------
M = np.diag([1.0, 2.0, 1.0, 1.0]) # y 方向拉伸 2 倍
n = np.array([1.0, 1.0, 0.0, 0.0])
N = np.linalg.inv(M).T # 逆转置
print("\nM @ n =", np.round(M @ n, 6), " (错误做法)")
def normal_transform(M):
"""对 3x3 线性部分求逆转置,再嵌回 4x4。"""
A = M[:3, :3]
N3 = np.linalg.inv(A).T
N4 = np.eye(4)
N4[:3, :3] = N3
return N4
print("(M^-1)^T @ n =", np.round(normal_transform(M) @ n, 6), " (正确)")
t1 = np.array([1.0, -1.0, 0.0]) # 与 n 正交的切向量
t1p = (M[:3, :3] @ t1)
print("(N n).(M t1) =", round(float((normal_transform(M) @ n)[:3] @ t1p), 12), " 应为 0")
print("(M n).(M t1) =", round(float((M @ n)[:3] @ t1p), 12), " 非零 => 直接变换是错的")
# ---------- 5. 投影 ----------
P_ortho = np.eye(4)
P_ortho[2, 2] = 0.0 # 投影到 z = 0
print("\n正交投影 P^2 == P ?", np.allclose(P_ortho @ P_ortho, P_ortho))
print("det P_ortho =", round(np.linalg.det(P_ortho), 12), " (不可逆)")
P_persp = np.eye(4)
P_persp[3, 2] = 1.0 # 最后一行改成 (0,0,1,0)
print("det P_persp =", round(np.linalg.det(P_persp), 12))
q = P_persp @ np.array([2.0, 4.0, 5.0, 1.0]) # 深度 z = 5 的点
print("透视投影后齐次坐标 =", q, " -> 除以 w 得", q[:3] / q[3])
输出(本机 numpy 2.3.5 实测):
R e1 = [0.866025 0.5 0. 1. ] 理论 (cos30, sin30, 0) = (np.float64(0.866025), np.float64(0.5))
R e2 = [-0.5 0.866025 0. 1. ] 理论 (-sin30, cos30, 0) = (np.float64(-0.5), np.float64(0.866025))
R^T R = I ? True
det R = 1.0
TRS @ p = [4.732051 2. 0. 1. ]
SRT @ p = [5.928203 5.732051 0. 1. ]
TRS == SRT ? False
T @ 点 = [4. 2. 0. 1.] (点被平移)
T @ 方向 = [1. 1. 0. 0.] (方向不变)
M @ n = [1. 2. 0. 0.] (错误做法)
(M^-1)^T @ n = [1. 0.5 0. 0. ] (正确)
(N n).(M t1) = 0.0 应为 0
(M n).(M t1) = -3.0 非零 => 直接变换是错的
正交投影 P^2 == P ? True
det P_ortho = 0.0 (不可逆)
det P_persp = 1.0
透视投影后齐次坐标 = [2. 4. 5. 6.] -> 除以 w 得 [0.33333333 0.66666667 0.83333333]
读输出:全部与手算一致。特别注意第 4 组:,而 ✓——这是"非均匀缩放下必须用逆转置"的决定性证据。
三个容易读错的地方
1.
T @ 点给的是 。 因为 作用在 上: 分量 、 分量 。手算时别把平移量记错。2. 这里的
det P_persp = 1.0是代码里那个"最简透视矩阵"特有的:它把单位矩阵的第 4 行改成 ,含非零元的只有第 4 列与第 4 行,展开后 ,所以它可逆。但它丢失深度:输出里 恒成立, 与 的点给出完全相同的屏幕坐标 。换成本篇 4.4.2 节的真实投影矩阵,深度就由 保存下来(那个矩阵也可逆)——详见 4.4.2 节末尾的提示框。3.
除以 w 得 [0.333, 0.667, 0.833]是因为 ,三个分量全都除以 ,且第三个分量恒为 。" 就是深度"、深度越大屏幕坐标越靠近原点,这正是"近大远小"。
第二部分:密码学
七、应用
希尔密码(Hill cipher)
6.1 原理
希尔密码(Hill cipher,Lester Hill 1929)是最早的"用线性代数做密码"的方案。核心思想:把明文分块成向量,用矩阵乘法在模 下加密。
加密:把明文字母按 转成数字,每 个一组构成列向量 ,取一个 的密钥矩阵 ,计算
解密:用 在模 下的逆矩阵 :
因为 ——解密的正确性完全依赖 的存在。
这是本库最纯粹的"矩阵求逆"应用:
| 线性代数概念 | 希尔密码中的对应 |
|---|---|
| 矩阵 | 密钥 |
| 加密 | |
| 解密密钥 | |
| 可逆 | 密码可用(无损解密) |
| 奇异 | 密码不可用(信息丢失,无法解密) |
| 判据: | |
| 线性无关的列 | 密文空间的维数 = (无碰撞) |
6.2 完整数值例子
取 ,密钥矩阵
明文:MATH。
第 1 步:字母转数字():
| 字母 | M | A | T | H |
|---|---|---|---|---|
| 数字 | 12 | 0 | 19 | 7 |
第 2 步:分块成列向量。 (MA),(TH)。
第 3 步:检查密钥可逆性。
✓,故 在模 下可逆。
第 4 步:求 。
先求 在模 下的逆元——找一个 使 。试 :
所以 。(更系统的办法是扩展欧几里得算法,见 8.6 节代码。)
再用 逆矩阵公式(2-4-矩阵运算与逆矩阵):
逐个元素取模 :
验证 :
取模 :
第 5 步:加密。
第 6 步:数字转回字母(,,,):
第 7 步:解密验证。
取模 :,,即 MA ✓
取模 :,,即 TH ✓
恢复明文 MATH。加密—解密闭环成立。
6.3 为什么密钥矩阵必须在模 26 下可逆
定理 10.5.2(模 可逆的判据)
设 是整数矩阵,。则 在 上可逆(即存在整数矩阵 使 )当且仅当
证明思路
()由 两边取行列式,并用 (5-1-行列式的性质):
若 ,则 且 ,于是 且 任何 的倍数。设 ,则 且 ,相减得 ,矛盾()。故 。
()由 5-2-排列与代数余子式 中的伴随矩阵公式
其中 是伴随矩阵(adjugate,代数余子式矩阵的转置),其元素是 的 阶子式,全是整数。若 ,则 在 中有逆元 ,于是
就是 在 上的逆矩阵。
特例:。因此
也就是说 必须是奇数,且不能被 13 整除。
对 情形的具体说明: 矩阵在 上可逆 。
6.4 反例:不可逆的密钥
取一个"看起来很正常"的矩阵:
,不可逆。而且第 2 行 第 1 行,矩阵的两列/两行线性相关,秩为 1。
后果:加密不是单射,明文信息被永久丢失。 看几个具体例子:
注意最后一组:明文 (即字母对 AN)被加密成 (即 AA)——和明文 AA 得到完全相同的密文!两个不同的明文映射到同一个密文,解密时无法区分。更进一步, 是 在 上的零空间的非零元素(),零空间非平凡 矩阵不可逆——这是第 3 章 3-2-零空间与阶梯形 的直接应用。
一个更"隐蔽"的反例(行列式非零但与 26 不互质):
,但在模 下仍然不可逆(因为 在 中没有乘法逆元)。这说明:
"" 与 "模 下可逆" 不是一回事
- 在 上: 可逆;
- 在 上:需要更强的条件 。
时, 在 上既不是单射也不是满射。实践中选密钥矩阵必须先验证 。
6.5 希尔密码的安全性(与线性代数的关系)
希尔密码在 1929 年提出时相当强大,但今天极易被攻破,原因完全是线性代数的:
已知明文攻击(known-plaintext attack):若攻击者知道 组"明文—密文"对,把它们排成矩阵
由 ,只要 在模 下可逆,立刻得到
密钥被直接解出——只需 组已知的对应关系,而不需要暴力搜索 个密钥。
已知密文攻击(ciphertext-only):由于希尔密码是线性的,字母频率信息以线性组合的形式保留下来,用统计方法(频率分析)在密文足够长时即可破解。线性结构就是它的致命弱点:密文中每个字母都是明文字母的线性函数,没有引入任何非线性混淆。
现代分组密码(AES、DES)正是针对这一点设计的:反复交替使用非线性 S 盒与线性扩散层(在 AES 中,扩散层是 上的矩阵乘法!——线性代数仍然在里面,只是被非线性层保护了)。AES 的 MixColumns 步骤就是一个 的 矩阵乘法。
6.6 希尔密码的代码实现
以下示例只用 numpy(含手写的扩展欧几里得求模逆元)。
import numpy as np
def mod_inverse(a, m):
"""扩展欧几里得算法:求 a 在模 m 下的逆元。"""
a %= m
old_r, r = a, m
old_s, s = 1, 0
while r:
q = old_r // r
old_r, r = r, old_r - q * r
old_s, s = s, old_s - q * s
if old_r != 1:
raise ValueError(f"{a} 在模 {m} 下不可逆(gcd = {old_r})")
return old_s % m
def key_inverse(K, m=26):
"""求 2x2 矩阵 K 在模 m 下的逆矩阵。"""
det = int(round(np.linalg.det(K))) % m
det_inv = mod_inverse(det, m)
adj = np.array([[K[1, 1], -K[0, 1]],
[-K[1, 0], K[0, 0]]]) # 伴随矩阵
return (det_inv * adj) % m
def is_invertible(K, m=26):
det = int(round(np.linalg.det(K)))
return np.gcd(det, m) == 1
def encrypt(K, text, m=26):
nums = [ord(ch) - ord('A') for ch in text.upper()]
assert len(nums) % 2 == 0, "本条示范要求明文长度为偶数"
out = []
for i in range(0, len(nums), 2):
v = K @ np.array(nums[i:i + 2])
out.extend(int(t) % m for t in v)
return "".join(chr(t + ord('A')) for t in out)
def decrypt(K, text, m=26):
return encrypt(key_inverse(K, m), text, m)
# ---------- 例子 1:可逆密钥 ----------
K = np.array([[4, 3], [1, 11]])
print("det K =", int(round(np.linalg.det(K))), " 可逆?", is_invertible(K))
print("K^-1 mod 26 =\n", key_inverse(K))
print("K @ K^-1 mod 26 =\n", (K @ key_inverse(K)) % 26)
ct = encrypt(K, "MATH")
print("MATH ->", ct, "->", decrypt(K, ct))
# ---------- 例子 2:不可逆密钥(行列式为 0)----------
K_bad = np.array([[3, 4], [6, 8]])
print("\ndet K_bad =", int(round(np.linalg.det(K_bad))), " 可逆?", is_invertible(K_bad))
print("秩 =", np.linalg.matrix_rank(K_bad), "(秩 1 < 2,必然信息丢失)")
for pt in ["AA", "AN"]:
print(f" 明文 {pt} -> 密文 {encrypt(K_bad, pt)}")
# ---------- 例子 3:行列式非零但与 26 不互质 ----------
K2 = np.array([[1, 2], [3, 8]])
print("\ndet K2 =", int(round(np.linalg.det(K2))), " 可逆?", is_invertible(K2))
try:
key_inverse(K2)
except ValueError as e:
print(" 求逆失败:", e)
输出(本机 numpy 2.3.5 实测):
det K = 41 可逆? True
K^-1 mod 26 =
[[25 5]
[19 2]]
K @ K^-1 mod 26 =
[[1 0]
[0 1]]
MATH -> WMTS -> MATH
det K_bad = 0 可逆? False
秩 = 1 (秩 1 < 2,必然信息丢失)
明文 AA -> 密文 AA
明文 AN -> 密文 AA
det K2 = 2 可逆? False
求逆失败: 2 在模 26 下不可逆(gcd = 2)
读输出:例子 1 完整闭环;例子 2 中 AA 与 AN 加密后都是 AA,明文无法区分——这正是"不可逆密钥导致信息丢失"的直接证据;例子 3 的 与 不互质,逆元不存在。
7.2 RSA 与线性代数
9.1 RSA 的流程(简述)
RSA(Rivest–Shamir–Adleman, 1977)基于"大整数分解困难":
- 选两个大素数 ,令 ,计算 Euler 函数 ;
- 选公开指数 使 ;
- 计算私钥 (用扩展欧几里得,和 8.6 节的
mod_inverse完全一样); - 加密:;解密:。
注意第 3 步:求 就是求模 下的逆元——与希尔密码求 是同一个运算。区别在于 RSA 是模幂(非线性),希尔密码是模线性变换。
为什么能解密:由 Euler 定理,,故
9.2 中国剩余定理(CRT)的线性代数视角
中国剩余定理(Chinese Remainder Theorem, CRT):若 两两互质,则同余方程组
在模 下有唯一解。
线性代数视角:把"取模 "看成坐标投影
则 CRT 说:映射
是一个环同构(bijection + 保持加减乘)。用向量的语言: 可以分解成互不相干的坐标系,每个 是一个"坐标轴",且各坐标之间互不干扰(这正是"两两互质"的含义)。
这与本库的直和分解(第 3 章的子空间直和)在结构上完全同构:
| 线性代数 | CRT |
|---|---|
| (直和) | |
| 投影到子空间 | 取模 |
| 由各分量唯一重构整体向量 | 由中国剩余定理唯一重构 |
| 各分量互相独立 | 各模数两两互质 |
在 RSA 中的应用: 很小时可以分别算 与 (用更小的数,快得多),再用 CRT 拼回 。这就是"RSA 加速"(CRT-RSA)的原理。
9.3 模幂运算
RSA 的核心计算是 ,其中 可能有几千比特。用快速幂(平方—乘法,repeated squaring)只需 次模乘:
Python 内建支持:
# 只用 Python 标准库(不需要 numpy)
p, q = 61, 53
n = p * q # 3233
phi = (p - 1) * (q - 1) # 3120
e = 17
d = pow(e, -1, phi) # Python 3.8+ 直接求模逆元:d = 2753
print("n =", n, " phi =", phi, " d =", d)
print("e*d mod phi =", (e * d) % phi) # 应为 1
m = 65
c = pow(m, e, n) # 快速幂:加密
print("m =", m, " c =", c, " 解密 =", pow(c, d, n))
输出:
n = 3233 phi = 3120 d = 2753
e*d mod phi = 1
m = 65 c = 2790 解密 = 65
与线性代数的关系:模幂本身不是线性的(这正是 RSA 比希尔密码安全的原因),但它依赖的模逆元、同余方程组的可解性、CRT 的分解结构都是线性代数/初等数论中"解线性方程组"的同类问题。
7.3 格密码与 LWE:现代的线性代数联系
希尔密码的弱点在于线性——有了 组明文—密文对就能解出密钥。现代抗量子密码(post-quantum cryptography)的主流方向是格密码(lattice-based cryptography),它的出发点恰好就是"在一个线性问题上加上一点点噪声,求解就变难了"。
10.1 格
定义 10.5.3(格,lattice) 设 线性无关。由它们生成的格是
即整系数线性组合的全体。写成矩阵形式:,其中 。
与列空间的对比(这张表是本节的骨架):
| 项目 | 列空间 | 格 |
|---|---|---|
| 系数范围 | 实数 (连续) | 整数 (离散) |
| 几何形态 | 过原点的平坦子空间 | 离散的点阵("格子") |
| 基是否唯一 | 不唯一(任何基都可) | 不唯一,且基的"好坏"差别巨大 |
| 基本问题 | 解 (高斯消元) | 最短向量问题 SVP、最近向量问题 CVP |
| 难度 | 多项式时间 | 高维下极难(NP 难,且无已知量子算法) |
| 密码学用途 | —— | 抗量子加密、全同态加密 |
关键点:同一个格有无穷多组基,其中有些基向量又长又接近平行("坏基"),有些又短又接近正交("好基")。从坏基求出好基(格基约化,如 LLL 算法)在高维下极难——这就是格密码安全性的来源。
10.2 LWE 问题
LWE(Learning With Errors,带误差学习) 的核心问题是:给定
其中 公开, 是秘密, 是小噪声向量,要求恢复 。
与线性代数的对照:
- 若 : 就是一个普通的模 线性方程组,用高斯消元几秒钟就能解出 ——这正是希尔密码被攻破的原理;
- 若 (哪怕每个分量只是 的小噪声):问题变成"在所有可能的 中找那个使 最短的",即一个最近向量问题(CVP),在高维下极难。
这就是"在超平面的交上找精确解"与"在带噪声的超平面上找最近点"的天壤之别——前者是第 2 章的高斯消元,后者是格上的困难问题。本库第 4 章的最小二乘在实数域解 ,靠的是投影与法方程(多项式时间);LWE 是它在模 的整数格上的版本,失去了正交投影这个工具,于是变难。
一句话总结格密码
希尔密码 = 线性代数太"干净"了,所以被解掉;格密码 = 在同一个线性代数问题上撒一把噪声,让"干净的解"不复存在。 而它之所以是"后量子"的,是因为 SVP/CVP 目前没有已知的多项式时间量子算法。
10.3 现代密码学中仍然处处是线性代数
| 技术 | 用到的线性代数 |
|---|---|
| AES 的 MixColumns | 上的 矩阵乘法(可逆矩阵提供扩散) |
| 分组密码的线性层 | 二元矩阵(MDS 矩阵),保证差分/线性活跃 S 盒数最大化 |
| 椭圆曲线密码 | 有限域上的点加法构成群;标量乘法的快速算法 |
| 哈希函数(如基于矩阵的) | 模 上的稀疏矩阵乘法 |
| 秘密共享(Shamir) | 有限域上的多项式插值(范德蒙德矩阵可逆) |
| 纠错码(RS 码、LDPC) | 生成矩阵与校验矩阵 , 在 中 |
| 全同态加密 | LWE 的扩展,密文是格上的向量 |
纠错码尤其值得一提:一个线性码就是一个子空间 ,最小距离与校验矩阵 的零空间维数直接相关。这与第 3 章的四大子空间是同一套语言(见 3-5-四大子空间的维数)。
7.4 两部分的共同点:都在做"矩阵变换 + 可逆性判定"
把图形学和密码学并排放在一起看,会发现同一个骨架:
| 对比项 | 计算机图形学 | 密码学(希尔/RSA/格) |
|---|---|---|
| 基本对象 | 点、方向、法向量( 或 ) | 明文块( 或 ) |
| 操作 | 矩阵乘法 | 矩阵乘法(加模运算) |
| 一次操作 | 一次变换 | 一次加密(或解密) |
| 复合操作 | 矩阵相乘() | 矩阵相乘 |
| 可逆性要求 | 需要逆变换(撤销变换、求视图矩阵、法向量变换) | 需要解密(恢复明文) |
| 可逆的判据 | (实数域) | (模 域) |
| 不可逆的后果 | 信息丢失(正交投影丢掉一整维深度;透视投影在"除以 "时把一条视线压成一个像素) | 无法解密,密文碰撞 |
| 逆矩阵的求法 | 高斯—若尔当消元、 公式、LU | 伴随矩阵 + 模逆元、扩展欧几里得 |
| 顺序是否重要 | 极其重要(,) | 一般不关心(单次乘) |
| 维数 | 用 处理 维(齐次坐标) | 用 处理 元块 |
| 线性性的作用 | 优点(可以合并、可以硬件加速) | 缺点(希尔密码因此被攻破) |
一句话的共同点
两部分都在用矩阵在有限或几何空间里做变换,而正确性/安全性都归结为矩阵的可逆性。
- 图形学里,"可逆"意味着变换可以撤销(旋转可以逆转、视图矩阵可以求逆、法向量可以正确变换);"不可逆"也有用武之地——投影就是故意不可逆的降维。
- 密码学里,"可逆"意味着解密可行;"不可逆"是灾难(希尔密码)或特性(哈希函数无法从摘要恢复原文)。
而两者对线性性的态度恰好相反:图形学欢迎线性(可合并成一次矩阵乘法),密码学警惕线性(线性结构会被已知明文攻击直接解出)。这一对比本身就是对"线性代数为什么有用"的最好注解。
八、易错点
九个高频错误
1. 忘记齐次坐标,导致平移无法表示。 最常见的错误版本是:写了一个 的旋转/缩放矩阵,然后想"再加个平移向量就行了",于是代码里出现
p_new = R @ p + t的混合形式,结果无法把整条变换链合并成一个矩阵,也无法与使用 的库(OpenGL、DirectX、Unity、Blender)对接。统一用 齐次矩阵, 表示点、 表示方向向量。2. 矩阵乘法顺序写反。 三个层次:
- 概念层: 中,最右边的 最先作用,与书写顺序相反;
- 代码层:
M = T @ R @ S与数学写法一致(都是从右往左作用),但如果你在心里默念"先平移再旋转",就会写成M = S @ R @ T而得到完全不同的结果(本篇第三节的数值演示: vs );- 库层:某些库提供
translate/rotate/scale函数,其默认复合顺序与矩阵乘法不完全一致(有的提供"先作用"语义),以该库文档为准。3. 以为平移量不会被缩放放大。 在 中, 会放大 造成的位移;只有 时平移才"最后生效、不被缩放"。这是布局 bug 的常见来源。
4. 希尔密码忘记模运算(或只在最后取模)。 每一步乘法后都要取模,否则数字爆炸且结果错误。注意 Python 的
%对负数返回非负结果(-21 % 26 == 5),这对密码学正是想要的行为;但若换成 C/Java 的%(对负数返回负值),必须额外处理((x % 26) + 26) % 26。5. 希尔密码忘记处理非互质情形。 选密钥矩阵时必须验证 。两个陷阱:
- (如 )——矩阵秩不足,明文被压扁;
- 但与 不互质(如 或 )——在实数域"可逆",在 上不可逆。 必须是奇数且不是 13 的倍数。
6. 以为 就等于"模 下可逆"。 见上一条。模运算的世界里,"可逆"是一个更强的条件。
7. 用直接矩阵乘法变换法向量。 只在纯旋转或均匀缩放下碰巧正确,一旦有非均匀缩放或错切就错(本篇第四节:)。法向量用 。另外注意:若 奇异(投影矩阵),逆转置不存在,需要专门处理。
8. 混淆投影矩阵与正交矩阵、忘记投影不可逆。 投影矩阵 满足 、,但 、 不存在。对投影后的坐标做逆转置、求逆、或者"从屏幕坐标恢复三维坐标",都是不可能的(一条视线上的所有点压到了同一个像素)。见 4-2-投影与投影矩阵。
9. 忽略透视除法与 的符号。 齐次坐标 只有在除以 之后才是三维坐标。常见坑:
- 忘记除法,直接把 当坐标用;
- 的点(在相机背后)除以负数会"翻转"到屏幕正确的位置,造成"身后的物体出现在前面",必须在裁剪阶段剔除( 的判断);
- 对应无穷远点,直接除法会得到 inf/nan。
正确流程是:先裁剪(用齐次不等式 ),再做透视除法。
九、例题:六道完整的手算与实验
这一节与第六节的分工
第六节是"用代码跑一遍本篇的结论",本节是六道完整的题目:先手算到位,再用 numpy 核对。做题时请先自己推一遍再看解答。
例题 1(旋转 与关于 轴反射:顺序不同,结果不同)
题目
对点 依次做两件事:
(A) 先绕 轴逆时针旋转 ,再关于 平面反射;
(B) 先关于 平面反射,再绕 轴逆时针旋转 。
写出两个 矩阵,算出两个结果,并说明差距有多大。
第 1 步: 写出两个基本矩阵。绕 轴旋转(本篇 2.2 节,、):
关于 平面的反射(即把 换成 ):
第 2 步: 写出两个复合矩阵。按"从右往左作用"的规则:
第 3 步: 算 (先旋转、后反射)。
(乘法的做法: 把第一行照抄、第二行变号。逐行核对: 的第 1 行 乘 得 的第 1 行 ; 的第 2 行 乘 得 第 2 行的相反数 。)
第 4 步: 算 (先反射、后旋转)。
第 5 步: 作用在 上。
结果: 与 ——两者关于原点对称,相差方向 !
第 6 步: 为什么会差这么多?把 换成基向量看:
- 把 送回自己:反射到 ,再逆时针转 得 (因为 ,)。所以 是 的特征向量,特征值 。
- 把 送到 :先转 得 ,再反射得 。 是 的特征向量,特征值 。
两个矩阵连"把 固定还是翻转"都不一样。
第 7 步: 行列式与可逆性。,,故
两者都可逆(),但都改变手性()——三角形顶点的环绕顺序会被翻转(第二节 2.5 节的结论)。
这类题最常见的两个错
- 把矩阵顺序写反。 要"先旋转再反射",就应当写 (新做的写在左边),而不是 。记住:作用顺序与书写顺序相反。
- 以为"反射 + 旋转"总可以合并成"某个旋转"。 不行:旋转的行列式是 、反射是 ,复合后是 ,绝不可能是纯旋转。"镜像不能靠转动消除"就是这句话的几何版本。
例题 2(绕任意点缩放:质心不动,距离翻倍)
题目
三角形顶点为 、、。求"以 为中心放大 倍"的 矩阵 ,算出三个顶点的新位置,验证 不动、各点到 的距离恰好翻倍(图形相似)。
第 1 步: 把"绕任意点"拆成三步。以点 为中心缩放 :
读法从右往左:先把 搬到原点(),再以原点为中心缩放(),最后搬回去()。中间那一步才是"干净"的缩放,两侧的平移只是"换个观察点"。
第 2 步: 写出三个矩阵。
(在 方向不缩放,这样是"平面内的相似变换",且 坐标保持不动。)
第 3 步: 先算右边的乘积 。 是分块的 ,对 的作用是:缩放左上 块、缩放第 4 列("平移列")的前两个分量,最后一行不动:
第 4 步: 再左乘 (只改第 4 列的前两个分量,加上 ):
于是得到一条极其好用的结论:
(代入 、: ✓。)
第 5 步: 作用在三个顶点上。逐个算:
第 6 步: 验证"相似"——各点到 的距离必须恰好 。
变换前:;。
变换后: ✓; ✓。
三个点仍在以 为中心、半径翻倍的圆上,所以放大后的三角形与原三角形相似(这是"均匀缩放"与"非均匀缩放"的分水岭)。
第 7 步: 用"质心不动"再验一次。设质心为 :
而本题的缩放中心是 不是质心,所以质心会动:
(因为 是仿射映射,它把质心送到"以 为中心、 倍"的位置:。)
一条可以背下来的模板
绕任意点 / 任意轴做变换,标准模板都是"搬过去 — 变换 — 搬回来":
绕任意轴旋转同理,先把轴平移到过原点、再旋转对齐到坐标轴、绕坐标轴转、然后原路返回。这就是 模式最重要的一个特例(第三节 3.1 节末的"常见实践约定")。
例题 3(齐次坐标:点、方向与整条直线)
题目
已知直线 :(即 )上有两点 、,方向向量 。取平移 。
(a) 用 的齐次坐标验证方向向量不被平移;
(b) 验证平移后两点仍在同一条直线上,并写出新直线方程;
(c) 求"把直线 搬到过原点"的平移量。
第 1 步: (a) 方向向量的平移。把 写成 的齐次向量:
方向不变。代数原因:第 4 列的 乘的是第 4 分量 ,贡献为零。
第 2 步: 而点会被平移():
第 3 步: (b) 写出新直线。两个新点是 、。检验它们是否满足同一个线性方程 :
两者给出同一个常数 ,故新直线是
注意右边的 变成了 。 怎么算出来的?用"法向量变换"的正规做法:直线 的法向量是 ,平移不改变任何方向,所以法向量不变(用第三节的方法验证:对纯平移 有 ,因为 的左上 块是单位矩阵,逆转置还是单位矩阵)。于是新直线是 ,把 代进去定 :
第 4 步: (c) 把直线搬到过原点。直线 与 轴的交点(取 ):,即 。(与 轴的交点是 。)取
则 把 送到原点,而直线的方向向量 不受影响,故新直线过原点、方向仍为 ,方程为
验算: 正是"过原点、斜率为 "的直线 ✓。
这道题背后的三句话
1. 点在变换、方向不在变——这不是"特判",而是 分量自动产生的效果;
2. 平移把直线整体搬走,方向不变、截距改变;缩放把方向也改了,所以直线可能不再平行于原来的自己;
3. 法向量按 变换、方向向量按 变换——这是第四节结论的一次实际使用,也是"为什么光照里两个向量要用不同方式变换"(例题 4)的直接原因。
例题 4(法向量与光源方向: 分量与逆转置一起决定明暗)
题目
点光源放在 ,一块平面在点 处,其法向量 (朝向 ,正对光源)。现在把场景沿 方向拉伸 倍,。
(a) 求出变换后正确的法向量 (用 );
(b) 光源方向 应该按什么方式变换(用 还是用 , 取 还是 )?
(c) 算出"光源方向与法向量夹角的余弦"在变换前后的变化,说明如果 (a)(b) 都做错会发生什么。
第 1 步: 先算变换前的余弦。,,两者同向:
表面正对光源,最亮()。
第 2 步: (a) 变换后正确的法向量。 的对角元取倒数即逆:
方向仍是 (拉伸方向上的法向量分量被压缩,但方向没变,所以本例里"用 变换"恰好也不会错方向——这正是这类 bug 难被发现的原因)。
第 3 步: (b) 光源方向按 变换,且 。 是两点之差,是方向向量,所以必须用 :
为什么不能用 ? 若写成 的"点",平移部分就会作用在它身上:场景一旦沿 平移 ,光源方向就会变成 ,方向被平移量污染。方向平移后应当不变,这是物理要求。
第 4 步: (c) 变换后的余弦。
余弦不变(仍为 )——物理上必须如此:沿法向拉伸整个场景,光源与平面的相对几何关系没变,明暗当然不该变。这就是"法向量必须用逆转置"的物理含义:它让内积(角度)在变换下保持可解释。
第 5 步: 做一个"错法对照表"。取一个更一般的点, 处的法向量 、光方向 (此时余弦也是 ):
| 做法 | 变换后的 | 变换后的 | 余弦 |
|---|---|---|---|
| 全对: 用逆转置、 用 () | |||
| 也直接用 | (完全错) | ||
| 忘了用 (带上了平移) | —— | 被平移量污染 | 与平移量有关,错 |
| 用 但忘了 只在转置与求逆可交换时成立(它们总是可交换) | 同第一行 | 同第一行 | 正确 |
第 6 步: 由这张表得到两条实践规则。
- 法向量与光方向是"两类不同的对象",必须用两套变换规则。 法向量是余向量(它描述约束 ),按 变换;光方向与切向量是向量(描述位移),按 变换。
- 法向量与方向向量都必须用 ——它们都不是"位置"。用 是图形学里最隐蔽的一类错误(平移量小的时候看不出来)。
只在"非均匀缩放或错切"时才暴露
- 旋转:(因为 ),两种做法完全一样;
- 均匀缩放 :,只差长度、方向一样,光照看起来也对;
- 非均匀缩放 / 错切:方向真的会错(第四节 4.3 节手算过:)。
所以"我的渲染器一直好好的"不能证明代码是对的。 想暴露这个 bug,请务必用 这类各向异性缩放做测试。
例题 5(证明: 与 )
题目(证明)
设 是可逆实方阵, 是实数。证明:
(a) ;
(b) (即"求逆"与"转置"可交换);
(c) 用 (a)(b) 推出:若 是正交矩阵(),则对一切 ,。并解释这个结论在图形学里的含义。
第 1 步: 证明 (a)。按逆矩阵的定义,只需验证 确实是 的逆——即两个方向的乘积都等于 :
(每一步都只用了数乘与矩阵乘法的结合律/交换律(标量可以随便挪)与 。)由逆的唯一性, 就是 。
第 2 步: 证明 (b)。同样用"验证它是逆"的办法。注意 的定义是" 的逆",所以只需验证
用转置的乘积公式 (2-5-LU分解与转置置换),把左边的转置算出来:
(用了两次 。)现在两边同时转置(转置是自身的逆运算):
同理 。由逆的唯一性,
第 3 步: 证明 (c)。正交矩阵满足 (4-4-标准正交基与Gram-Schmidt)。用 (a)、(b) 逐步化简:
第 4 步: 这个结论的图形学含义。取 、,即"旋转 并均匀放大 倍",则
它与 只差一个正标量 。由于法向量的方向只由比例决定、长度无关紧要,所以
这就是为什么大量教程和引擎代码里写着"法向量就用同一个矩阵变换"却一直没出事——他们测试的场景恰好都是旋转与均匀缩放。
第 5 步: 什么时候会出事?只要 不是标量乘正交矩阵就会出事。判断方法很便宜:
即" 是数量矩阵"。用一次矩阵乘法就能判断自己的变换是否安全——这是本篇最实用的一条工程结论。
第 6 步: 顺带说清"投影阶段为什么不能这么用"。逆转置公式要求 可逆:(a)(b)(c) 三条恒等式全都建立在 存在之上。
- 4.4.2 节那个最简透视矩阵(把第 4 行改成 )、秩为 ,确实奇异,对它算不出 ;
- 而真实的投影矩阵(含 等)、可逆(见 4.4.2 节末的提示框),但它把三维点映到"二维屏幕坐标 + 深度",法向量的"垂直"在那一层已经没有三维内积的含义了。
所以两种情况下结论一致、理由不同:流水线里做光照,必须在投影之前,用模型视图矩阵左上 部分的逆转置换算法向量。
例题 6(numpy 数值实验:旋转、复合顺序、齐次坐标与希尔密码)
题目
只用 numpy 完成八组数值实验:旋转矩阵的推导与三条性质;缩放与平移是否交换;绕任意点缩放的 矩阵; 与 的区别;法向量的逆转置;反射与旋转不可交换;希尔密码 加密
SECRET再解密;坏密钥的两个反例。
代码(只用 numpy)
import numpy as np
# ---------- 4x4 变换矩阵构造器 ----------
def translate(a):
T = np.eye(4)
T[0:3, 3] = a
return T
def scale(sx, sy, sz=1.0):
S = np.eye(4)
S[0, 0], S[1, 1], S[2, 2] = sx, sy, sz
return S
def rot_z(deg):
th = np.radians(deg)
c, s = np.cos(th), np.sin(th)
R = np.eye(4)
R[0, 0], R[0, 1], R[1, 0], R[1, 1] = c, -s, s, c
return R
def normal_transform(M):
N = np.eye(4)
N[:3, :3] = np.linalg.inv(M[:3, :3]).T
return N
print("=== 1. 旋转 60 度:R e1, R e2 与三条性质 ===")
R = rot_z(60)
print("R @ e1 =", np.round(R @ [1, 0, 0, 1], 6), " 理论 (cos60, sin60, 0) = (0.5, 0.866025, 0)")
print("R @ e2 =", np.round(R @ [0, 1, 0, 1], 6), " 理论 (-sin60, cos60, 0) = (-0.866025, 0.5, 0)")
print("R^T R = I ?", np.allclose(R.T @ R, np.eye(4)), " det R =", round(np.linalg.det(R), 12))
print("R(60) @ R(-60) = I ?", np.allclose(rot_z(60) @ rot_z(-60), np.eye(4)))
print("\n=== 2. 缩放与平移是否交换 ===")
p = np.array([1.0, 2.0, 0.0, 1.0])
S = scale(2.0, 3.0)
T = translate([3.0, 1.0, 0.0])
print("S @ T @ p =", np.round(S @ T @ p, 6), " T @ S @ p =", np.round(T @ S @ p, 6))
print("S @ T == T @ S ?", np.allclose(S @ T, T @ S))
print("\n=== 3. 绕点 (3,4) 缩放 2 倍:T @ S @ T^-1 ===")
c = np.array([3.0, 4.0, 0.0])
M = translate(c) @ scale(2.0, 2.0) @ translate(-c)
print("M =\n", np.round(M, 6))
print("det M =", round(np.linalg.det(M), 6))
for q in [[3, 4, 0, 1], [5, 2, 0, 1], [1, 2, 0, 1], [1, 6, 0, 1]]:
q = np.array(q, dtype=float)
print(f" {q[:3]} -> {(M @ q)[:3]}")
print("\n=== 4. 齐次坐标:点被平移、方向不被平移 ===")
d = np.array([1.0, 1.0, 0.0, 0.0])
print("T @ 点(1,1,0,1) =", np.round(T @ [1, 1, 0, 1], 6))
print("T @ 方向(1,1,0,0) =", np.round(T @ d, 6))
print("T^-1 @ T @ 点 =", np.round(np.linalg.inv(T) @ T @ [1, 1, 0, 1], 6))
print("\n=== 5. 法向量:M 直接变换 vs (M^-1)^T ===")
M2 = scale(2.0, 0.5)
n = np.array([1.0, 1.0, 0.0])
t = np.array([1.0, -1.0, 0.0])
print("n.t =", float(n @ t), " (变换前正交)")
print("M @ n =", M2[:3, :3] @ n, " 与 M t 的内积 =", float((M2[:3, :3] @ n) @ (M2[:3, :3] @ t)))
nn = (normal_transform(M2) @ np.append(n, 0))[:3]
print("(M^-1)^T n =", np.round(nn, 6), " 与 M t 的内积 =", round(float(nn @ (M2[:3, :3] @ t)), 12))
print("\n=== 6. 反射与旋转不可交换(90 度旋转 + 关于 x 轴反射)===")
Rz = rot_z(90)
F = np.diag([1.0, -1.0, 1.0, 1.0])
v = np.array([1.0, 1.0, 0.0, 1.0])
print("R @ F @ v =", np.round(Rz @ F @ v, 6), " F @ R @ v =", np.round(F @ Rz @ v, 6))
print("R @ F == F @ R ?", np.allclose(Rz @ F, F @ Rz))
print("det R =", round(np.linalg.det(Rz), 12), " det F =", round(np.linalg.det(F), 12))
# ---------- 希尔密码 ----------
def mod_inv(a, m):
a %= m
r0, r1, s0, s1 = a, m, 1, 0
while r1:
q = r0 // r1
r0, r1 = r1, r0 - q * r1
s0, s1 = s1, s0 - q * s1
if r0 != 1:
raise ValueError(f"{a} 在模 {m} 下不可逆(gcd={r0})")
return s0 % m
def key_inv(K, m=26):
d = int(round(np.linalg.det(K))) % m
adj = np.array([[K[1, 1], -K[0, 1]], [-K[1, 0], K[0, 0]]])
return (mod_inv(d, m) * adj) % m
def invertible(K, m=26):
return np.gcd(int(round(np.linalg.det(K))), m) == 1
def hill(K, text, m=26):
nums = [ord(ch) - 65 for ch in text.upper()]
assert len(nums) % 2 == 0, "本示范要求明文长度为偶数"
out = []
for i in range(0, len(nums), 2):
v = K @ np.array(nums[i:i + 2])
out += [int(t) % m for t in v]
return "".join(chr(t + 65) for t in out)
print("\n=== 7. 希尔密码:K = [[3,3],[2,5]] 加密 SECRET 再解密 ===")
K = np.array([[3, 3], [2, 5]])
det = int(round(np.linalg.det(K)))
print("det K =", det, " gcd(det,26) =", np.gcd(det, 26), " 可逆?", invertible(K))
Ki = key_inv(K)
print("K^-1 mod 26 =\n", Ki)
print("K @ K^-1 mod 26 =\n", (K @ Ki) % 26)
ct = hill(K, "SECRET")
print("SECRET ->", ct, "->", hill(Ki, ct))
print("\n=== 8. 坏密钥与隐蔽的坏密钥 ===")
K3 = np.array([[5, 4], [10, 8]])
print("det K3 =", int(round(np.linalg.det(K3))), " 秩 =", np.linalg.matrix_rank(K3), " 可逆?", invertible(K3))
print("K3 @ (0,13) mod 26 =", (K3 @ np.array([0, 13])) % 26, " <-- 非零明文块映射到零密文块")
for pt in ["AA", "AN"]:
print(f" 明文 {pt} -> 密文 {hill(K3, pt)}")
K4 = np.array([[3, 1], [1, 3]])
print("det K4 =", int(round(np.linalg.det(K4))), " gcd =", np.gcd(int(round(np.linalg.det(K4))), 26),
" 可逆?", invertible(K4))
try:
key_inv(K4)
except ValueError as e:
print(" 求逆失败:", e)
输出(本机 numpy 2.3.5 实测)
=== 1. 旋转 60 度:R e1, R e2 与三条性质 ===
R @ e1 = [0.5 0.866025 0. 1. ] 理论 (cos60, sin60, 0) = (0.5, 0.866025, 0)
R @ e2 = [-0.866025 0.5 0. 1. ] 理论 (-sin60, cos60, 0) = (-0.866025, 0.5, 0)
R^T R = I ? True det R = 1.0
R(60) @ R(-60) = I ? True
=== 2. 缩放与平移是否交换 ===
S @ T @ p = [8. 9. 0. 1.] T @ S @ p = [5. 7. 0. 1.]
S @ T == T @ S ? False
=== 3. 绕点 (3,4) 缩放 2 倍:T @ S @ T^-1 ===
M =
[[ 2. 0. 0. -3.]
[ 0. 2. 0. -4.]
[ 0. 0. 1. 0.]
[ 0. 0. 0. 1.]]
det M = 4.0
[3. 4. 0.] -> [3. 4. 0.]
[5. 2. 0.] -> [7. 0. 0.]
[1. 2. 0.] -> [-1. 0. 0.]
[1. 6. 0.] -> [-1. 8. 0.]
=== 4. 齐次坐标:点被平移、方向不被平移 ===
T @ 点(1,1,0,1) = [4. 2. 0. 1.]
T @ 方向(1,1,0,0) = [1. 1. 0. 0.]
T^-1 @ T @ 点 = [1. 1. 0. 1.]
=== 5. 法向量:M 直接变换 vs (M^-1)^T ===
n.t = 0.0 (变换前正交)
M @ n = [2. 0.5 0. ] 与 M t 的内积 = 3.75
(M^-1)^T n = [0.5 2. 0. ] 与 M t 的内积 = 0.0
=== 6. 反射与旋转不可交换(90 度旋转 + 关于 x 轴反射)===
R @ F @ v = [1. 1. 0. 1.] F @ R @ v = [-1. -1. 0. 1.]
R @ F == F @ R ? False
det R = 1.0 det F = -1.0
=== 7. 希尔密码:K = [[3,3],[2,5]] 加密 SECRET 再解密 ===
det K = 9 gcd(det,26) = 1 可逆? True
K^-1 mod 26 =
[[15 17]
[20 9]]
K @ K^-1 mod 26 =
[[1 0]
[0 1]]
SECRET -> OEFLRZ -> SECRET
=== 8. 坏密钥与隐蔽的坏密钥 ===
det K3 = 0 秩 = 1 可逆? False
K3 @ (0,13) mod 26 = [0 0] <-- 非零明文块映射到零密文块
明文 AA -> 密文 AA
明文 AN -> 密文 AA
det K4 = 8 gcd = 2 可逆? False
求逆失败: 8 在模 26 下不可逆(gcd=2)
读输出(六条结论)
- 旋转矩阵的两列就是 与 ,数值与手算逐位一致;、、 全部成立。
- 缩放与平移不交换:同一个点 在 下变成 、在 下变成 ——差了一整个平移量的缩放。这正是"平移量被缩放放大"的 bug(第三节 3.2 节的同一现象)。
- 的数值形式确实是" 与平移列 ";中心 不动、其余三点各自向外翻倍,与例题 2 的手算完全一致。
- 的方向向量在平移下分毫不动,而 的点被平移; 把点原样送回——每个变换都可撤销(因为 )。
- 第 5 组是"逆转置"的决定性证据: 与 的内积是 ,而 与 的内积是 (到 )。
- 希尔密码闭环成立:(奇数、且不被 整除)⟹ 可逆;,;
SECRETOEFLRZSECRET。两个反例分别是 (秩 ,AA与AN撞成同一密文)与 (与 不互质,求模逆元直接失败)。
这份实验最容易踩的三个坑
-
np.linalg.det返回浮点数。 判断模可逆性时必须先int(round(...))再取 ,否则np.gcd会拿到一个浮点值而报错或给出错误结果。密钥元素大时浮点误差也可能让round出错——实践中应直接用整数公式 算行列式(见例题 6 代码里的hill与key_inv)。-
assert len(nums) % 2 == 0。 长度为奇数的明文必须先填充(常用X),否则最后一个字母会被丢掉。填充字符本身要能被接收方识别并去掉。- Python 的
%与 C/Java 不同。 Python 里-21 % 26 == 5(结果总取非负),正是密码学想要的行为;换成 C/Java 必须写((x % 26) + 26) % 26。
十、练习题
基础题 1 写出把点 绕 轴逆时针旋转 、再沿 方向平移 的 矩阵 ,并计算变换后的坐标。(先判断复合顺序: 还是 ?)
基础题 2 验证 是正交矩阵:直接计算 并证明它等于 ,并说明为什么 。
基础题 3 已知希尔密码密钥 (模 26)。判断 是否可逆;若可逆,求 ,并加密明文 HI、再解密验证。(提示:先算 ,再用 公式。)
进阶题 4 设 ( 方向拉伸 2 倍),平面法向量 ,切向量 。
(a) 计算 ,并验证它与 正交;
(b) 验证 与 不正交(算出内积的具体值);
(c) 画出(用文字描述)拉伸前后平面与法向量的几何关系,解释为什么法向量必须"反向调整"。
进阶题 5 证明:若 是 旋转矩阵(正交且 ),则对任意向量 有 。据此解释为什么"只做旋转时,用法向量直接用 变换也不会出错"。
进阶题 6 用扩展欧几里得算法求 (RSA 的一个小例子),并用 Python 的 pow(17, -1, 3120) 核对。
思考题 7 证明: 整数矩阵 在 上可逆 是奇数且 。并据此判断下列矩阵哪些可逆:,,,。
思考题 8 解释为什么"投影矩阵不可逆"与"透视投影下无法从屏幕坐标唯一恢复三维坐标"是同一件事的两种说法。用四大子空间的语言表述:屏幕坐标空间对应哪个子空间?丢失的信息对应哪个子空间?
思考题 9 LWE 问题中,若把噪声 设为 ,问题为什么变成多项式时间可解?请写出求解步骤(提示:模 下的高斯消元,需 的某 列在 下可逆)。这解释了为什么希尔密码不安全。
十、常见问题 FAQ
Q1:为什么一定要 ?用 加一个平移向量不行吗?
数学上当然可以——这叫仿射变换的"线性部分 + 平移部分"写法:
但它的缺点是不能复合:连续做两次得到
虽然也能写成"新线性部分 + 新平移",但每一步都要分开维护 与 、并且 这一项容易漏。齐次坐标把两者打包进一个矩阵,复合退化为纯粹的矩阵乘法,与第 8 章"线性变换的复合就是矩阵相乘"完全统一,硬件也只需实现一种运算。这是工程上的巨大简化。
Q2:齐次坐标为什么能表示透视投影?透视投影不是非线性的吗?
透视除法 确实非线性,但齐次坐标的技巧在于:把非线性的除法和线性的缩放分开。矩阵乘法先把 搬进第 4 分量(这一步是线性的),除法随后一次性完成(这是唯一非线性的一步,且在硬件里是逐顶点的固定操作)。这类似于射影几何的做法:在射影空间中,投影是线性的;只有回到欧氏坐标时才需要除法。
Q3:法向量变换为什么不用 的"直观解释"?
一个好的直观:法向量描述的是"约束方向"而不是"位移"。 想象把一张纸沿 方向拉伸 2 倍:纸面上一条 45° 的线会变得更陡(往 方向压),而垂直于纸面的方向(法向量)反而变得更平(往 方向压)。拉伸把法向量向"被压缩的方向"推,这就是"取逆"的几何含义;再取转置,是因为法向量是余向量(covector,线性泛函 的系数),而余向量的变换规则天然是逆转置。
Q4:希尔密码用矩阵,为什么反而不如现代的 AES 安全?矩阵不是很难破解吗?
难破解的是"给定 求 "这个问题本身——在只有 的情况下, 有无穷多候选( 的每个满足条件的 都对应某个 )。但密码学的威胁模型不允许这种"信息论不确定"就够了,必须抵抗已知明文攻击:攻击者通常能猜到或诱导出一些明文(比如邮件开头的 "Dear"),一旦拿到 组线性无关的明文—密文对, 一步算出。线性结构的致命之处在于: 组样本就足以完全确定密钥,无需搜索。 AES 用非线性 S 盒打断了这个线性关系,使攻击者必须面对指数级的搜索空间。
Q5:图形学里的矩阵和密码学里的矩阵,本质上有什么不同?
三处不同:
- 数域不同:图形学在 (或浮点近似)上工作,密码学在 或 上工作。后者没有"近似"——每一位都要精确,且"除法"要换成"乘模逆元";
- 可逆性的判据不同: vs ;
- 对线性的态度不同:图形学拥抱线性(可合并、可加速);密码学回避线性(线性结构可被代数攻击)。
但核心工具完全一样:矩阵乘法、逆矩阵、行列式、秩、零空间。这就是为什么 Strang 把这两节放在同一章——它们展示的是同一套线性代数在两个极端场景下的用法。
本篇小结
一页纸回顾
本篇把"矩阵做变换"这件事放在两个极端场景里看:
图形学:把点升到四维(齐次坐标) 平移也变成矩阵 整条流水线合并成 一次乘法;
密码学:把字母装成向量、把密钥装成矩阵 加密 、解密 ,正确性完全落在" 在模 下可逆"上。
两次都归结为同一句话:变换要能撤销,所以矩阵必须可逆。
逻辑链条(每一环都用上一环)
| 环节 | 命题 | 依据 |
|---|---|---|
| 1 | 平移 不是线性变换() | 定理 10.5.1 |
| 2 | 升到四维()后,平移成为 矩阵乘法 | 1.2 节验证 |
| 3 | 表示点(被平移)、 表示方向(不被平移) | 1.3 节 |
| 4 | 缩放、旋转、平移、错切、反射都有 矩阵;只有平移必需第 4 列 | 第二节总表 |
| 5 | 旋转矩阵的两列就是 、 | 2.6 节推导 |
| 6 | 、:旋转可逆、保长、保手性;反射 改变手性 | 例题 1 |
| 7 | 复合变换从右往左作用,顺序不同结果不同() | 第三节 + 例题 1、2 |
| 8 | 法向量按 变换,切向量/方向按 变换 | 第四节推导 + 例题 4 |
| 9 | 正交投影矩阵不可逆();真实的透视投影矩阵可逆,真正不可逆的是"除以 "这一步降维 | 4.4 节 |
| 10 | 希尔密码:、 | 6.1 节 + 例题 6 |
| 11 | 在 上可逆 | 定理 10.5.2 |
| 12 | 不可逆密钥使加密不是单射,不同明文撞成同一密文(零空间非平凡) | 6.4 节 + 例题 6 |
| 13 | 希尔密码被" 组已知明文"一击破解:;线性结构是致命弱点 | 6.5 节 |
必背公式清单
| 名称 | 公式 | 条件 |
|---|---|---|
| 平移 | ,唯一用到第 4 列的仿射变换 | |
| 缩放 | ||
| 绕 轴旋转 | ,; | |
| 绕 轴旋转 | :左上块换成 放在 位置 | |
| 绕 轴旋转 | 的 符号相反(右手系后果) | 见 2.2 节 warning |
| 错切 | ,保体积不保角 | |
| 反射(关于 平面) | ,改手性 | |
| 齐次坐标 | ,三维坐标是 | |
| 绕任意点缩放 | 一般模板 | |
| 法向量变换 | 必须可逆 | |
| 逆转置的两个恒等式 | , | , 可逆 |
| 安全判据 | ( 正交)时可放心中直接用 变换法向量 | 一次矩阵乘法即可检验 |
| 透视投影 | , 或 | ,不可逆 |
| 流水线 | 第 4 步是除法、不是矩阵 | |
| 希尔加密/解密 | , | 整数矩阵 |
| 模可逆判据 | ;对 : 为奇数且不被 整除 | 定理 10.5.2 |
| 模逆 | ||
| 已知明文攻击 | () | 在模 下可逆 |
| LWE | : 时高斯消元可解, 时困难 | 格上的 CVP |
易混概念对照表(本篇最容易搞错的八组)
| 易混的一对 | 关键区别 | 一句话记法 |
|---|---|---|
| 旋转 vs 反射 | 保手性; 改手性 | 镜像不能靠转动消除(行列式是障碍) |
| 点 vs 方向向量 | 的会被平移; 的不会被平移 | 位置用 ,方向用 ;法向量属于后者 |
| 法向量 vs 切向量 | 法向量按 ;切向量按 | 只有非均匀缩放/错切才暴露差别 |
| vs 模 下可逆 | 实数域只需 ; 上还要 | 在 上可逆、在 上不可逆 |
| 仿射 vs 射影 | 仿射最后一行 ;射影不是(例如 ) | 射影需要"透视除法"这一步 |
| 正交投影 vs 透视投影 | 正交投影矩阵 不可逆;真实透视投影矩阵 可逆,不可逆的是"除以 "这一步 | 两者都丢深度:正交投影丢在矩阵里,透视投影丢在除法里 |
| 加密方向 vs 解密方向 | 加密用 、解密用 ,都是矩阵乘法 | 顺序无所谓(单次乘),但不可逆就全盘失效 |
| 图形学欢迎线性 vs 密码学警惕线性 | 图形学要合并、要加速;密码学怕被 解出 | 同一个性质、两种态度 |
五个"必须会动手做"的动作
- 默写五种基本 矩阵(缩放、绕三轴旋转、平移、错切、反射),并说出各自的行列式与手性。
- 推导旋转矩阵:写出 、,用和角公式得到两列,再看 。
- 算一次 ,把结果化简成 ,并验证中心不动。
- 手算一次希尔密码:验证 、用 公式求 、验证 、加解密闭环。
- 构造一个不可逆密钥( 或 与 不互质),找出两组撞成同一密文的明文。
自测清单
- 能否证明"平移不是线性变换",并说明为什么"升到四维"能解决这个矛盾?
- 能否说清"齐次坐标为什么能表示透视投影"(哪一步线性、哪一步非线性)?
- 能否解释 与 的差别,并指出"平移量被缩放放大"出现在哪一种里?
- 能否推出 ,并说出旋转、均匀缩放下它为什么退化成 ?
- 能否判断"某组变换能否放心用 变换法向量"?判据是什么?
- 能否说出 与 上"可逆"的差别,并各举一个反例?
- 为什么希尔密码扛不住已知明文攻击?用一句话说清"线性结构"在这里的害处。
关联与后续用法
- 8-1-线性变换的思想:本篇图形学部分的全部推导都建立在"线性变换由它在基向量上的作用唯一确定"上——例题 1 与 2.6 节的旋转矩阵推导就是它的直接使用。
- 8-2-线性变换的矩阵表示: 是"换基(换观察点)后矩阵变成 "的一个具体例子;相似变换的语言能统一解释"绕任意点 / 任意轴"的模板。
- 2-4-矩阵运算与逆矩阵:希尔密码的解密、视图矩阵 、法向量的逆转置,全部依赖逆矩阵;例题 5 的两条恒等式也在这里的基础工具之上。
- 2-5-LU分解与转置置换:例题 5 的证明用到 与 ,转置的全部性质在那篇里。
- 4-2-投影与投影矩阵:正交投影 、、,与图形学投影矩阵是同一种对象;流水线中"投影阶段不能用逆转置"的原因也在那里。
- 4-4-标准正交基与Gram-Schmidt:旋转矩阵是正交矩阵(),例题 5 的 (c) 部分正是"正交 + 均匀缩放"这一特例。
- 5-1-行列式的性质: 既用于""(例题 1),也是模可逆判据证明的关键一步。
- 5-2-排列与代数余子式:伴随矩阵 是"模 下可逆"充分性证明的工具,也是 模逆公式的来源。
- 3-2-零空间与阶梯形:不可逆密钥使加密不是单射,本质是零空间非平凡(,例题 6 第 8 组复现了这一点)。
- 3-5-四大子空间的维数:纠错码的校验矩阵 与线性码子空间 用的就是四大子空间的语言(10.3 节)。
- 1-2-长度与点积:法向量与切向量的正交性是"点积为零";例题 4 的光照明暗完全由夹角余弦决定。
相关笔记
- 8-1-线性变换的思想 —— 本篇的图形学部分就是这篇的直接应用:变换由它在基向量上的作用确定(旋转矩阵的推导正是如此)。
- 2-4-矩阵运算与逆矩阵 —— 希尔密码的解密、视图矩阵 、法向量的逆转置,全部依赖逆矩阵; 求逆公式在希尔密码里被反复使用。
- 4-2-投影与投影矩阵 —— 正交投影矩阵 、、,与图形学的投影矩阵是同一种对象。
- 4-4-标准正交基与Gram-Schmidt —— 旋转矩阵是正交矩阵(,),是正交基变换的特例。
- 5-1-行列式的性质 —— 是"模 下可逆 "证明的关键一步。
- 3-2-零空间与阶梯形 —— 不可逆密钥导致密文碰撞,本质是零空间非平凡()。
参考来源
- Gilbert Strang, Introduction to Linear Algebra, 5th ed., Wellesley-Cambridge Press, 2016, Section 10.6 "Computer Graphics"(齐次坐标、 变换矩阵、透视投影)与 Section 10.7 "Linear Algebra for Cryptography"(希尔密码、RSA、模运算)。
- Introduction to Linear Algebra, 5th Edition 官方站点(教材目录,第 10 章 Application 各节)。
- MIT 18.06 Linear Algebra, Spring 2010(课程主页)。
- MIT 18.06 Readings(5th ed. 的 10.6/10.7 对应"线性变换与图像压缩"部分)。
- numpy.linalg.det 文档(计算 判断密钥可逆性)。
- numpy.linalg.matrix_power 文档(矩阵幂与逆幂,可用于验证变换的复合与撤销)。