密码学数学基础（一）：集合、映射与二元运算
插画：原神官方
读密码学里的数学表达式，第一步不是记住复杂定理，而是知道：对象属于什么集合、映射把它送到哪里、运算能不能做、做完能不能还原。
本文整理《Number Theory and Algebra in Cryptography》Lecture 1 的知识部分。重点是概念的使用、具体计算和容易混淆的记号，不展开公理体系与长篇证明。
例如，看到下面的式子时，应该能判断它的输入范围、计算顺序，以及逆运算的顺序：
$$ E=g\circ f,\qquad E^{-1}=f^{-1}\circ g^{-1} $$1. 对数与指数：先确认底数
课件采用以下约定：
| 记号 | 含义 | 例子 |
|---|---|---|
| $\log x$ | 自然对数，也就是 $\ln x$ | $\log e=1$ |
| $\log_b x$ | 以 $b$ 为底的对数 | $\log_2 8=3$ |
| $e^x$、$\exp[x]$ | 自然指数函数 | $\exp[0]=1$ |
在实数范围内，$\log_b x$ 要求 $x>0$、$b>0$ 且 $b\ne1$。
对数回答的问题是：“底数乘方多少次，可以得到这个数？”
$$ 2^5=32\quad\Longleftrightarrow\quad\log_2 32=5 $$换底公式可以把不同底数的对数联系起来：
$$ \log_b x=\frac{\ln x}{\ln b} $$比如有 $2^8=256$ 种可能，那么 $\log_2 256=8$。长度为 8 的二进制串恰好也有 256 种，因为每个位置有两种选择。
不要混淆“可能性的数量”和“一个整数的二进制位数”。 对正整数 $n$，其二进制位数是：
$$ \lfloor\log_2 n\rfloor+1 $$因此整数 256 的二进制写法是 100000000，有 9 位；但表示从 0 到 255 的 256 种取值，只需要 8 位。
这里讨论的是普通实数对数。后续密码学中的“离散对数”是另一类问题，不能直接用普通的 log 函数求解。
2. 常见数集与自然数约定
| 数集 | 记号 | 元素示例 |
|---|---|---|
| 自然数 | $\mathbb N$ | $0,1,2,\ldots$ |
| 整数 | $\mathbb Z$ | $\ldots,-2,-1,0,1,2,\ldots$ |
| 有理数 | $\mathbb Q$ | 能写成 $a/b$ 的数，其中 $a,b\in\mathbb Z$、$b\ne0$ |
| 实数 | $\mathbb R$ | 有理数以及 $\sqrt2$、$\pi$ 等无理数 |
| 复数 | $\mathbb C$ | $a+bi$，其中 $a,b\in\mathbb R$、$i^2=-1$ |
它们满足：
$$ \mathbb N\subsetneq\mathbb Z\subsetneq\mathbb Q \subsetneq\mathbb R\subsetneq\mathbb C $$本文把 0 算作自然数。 有些教材从 1 开始定义自然数，所以遇到 $\mathbb N$ 时要先看作者的约定。
课件还列出了 Peano 公理。就后续读写算法而言，可以先抓住“从 0 开始，通过后继不断得到下一个自然数”的思路；第五条对应数学归纳法：先验证起点，再说明“对 $n$ 成立就对 $n+1$ 成立”。这里不展开公理化构造。
复数运算已经在复数与复变函数的基础文章中整理，本文不重复展开。
3. 集合：元素、子集与集合运算
3.1 属于和包含不是一回事
设：
$$ A=\{1,2,3\},\qquad B=\{2,3,4\} $$那么：
- $1\in A$：1 是集合 $A$ 的一个元素。
- $\{1\}\subseteq A$：集合 $\{1\}$ 的每个元素都属于 $A$。
- $\{1,2\}\subsetneq A$：它是 $A$ 的子集，但不等于 $A$，所以是真子集。
- $A\subseteq A$ 成立，但 $A\subsetneq A$ 不成立。
不能把 $1\in A$ 随意写成 $1\subseteq A$；前者讨论“元素与集合”，后者需要讨论“集合与集合”。
3.2 并、交、差分别在选什么
| 运算 | 选择规则 | 上面例子的结果 |
|---|---|---|
| $A\cup B$ | 属于 $A$ 或属于 $B$ | $\{1,2,3,4\}$ |
| $A\cap B$ | 同时属于 $A$ 和 $B$ | $\{2,3\}$ |
| $A\setminus B$ | 属于 $A$，但不属于 $B$ | $\{1\}$ |
| $B\setminus A$ | 属于 $B$，但不属于 $A$ | $\{4\}$ |
差集通常不满足交换律：$A\setminus B\ne B\setminus A$。
集合不保留重复次数，也不以书写顺序区分：
$$ \{1,1,2\}=\{1,2\}=\{2,1\} $$有限集合的元素个数叫作基数，记作 $|A|$。这里 $|A|=3$，$|A\cap B|=2$，因此：
$$ |A\cup B|=|A|+|B|-|A\cap B|=3+3-2=4 $$减去交集，是因为 2 和 3 在前两项中各被数了两次。
3.3 空集与“装着空集的集合”
$\varnothing$ 没有任何元素，所以 $|\varnothing|=0$。但 $\{\varnothing\}$ 有一个元素，这个元素恰好是空集，因此： $$ \varnothing\ne\{\varnothing\},\qquad |\{\varnothing\}|=1 $$空集是任何集合的子集，但不一定是任何集合的元素。例如对 $A=\{1,2,3\}$，有 $\varnothing\subseteq A$，却没有 $\varnothing\in A$。
4. 笛卡尔积：把多个选择组成有序输入
设：
$$ A=\{0,1\},\qquad B=\{a,b,c\} $$笛卡尔积是所有有序对的集合：
$$ A\times B=\{(0,a),(0,b),(0,c),(1,a),(1,b),(1,c)\} $$第一个位置从 $A$ 中选，第二个位置从 $B$ 中选，所以：
$$ |A\times B|=|A|\,|B|=2\times3=6 $$有序对和普通集合不同：$(0,1)\ne(1,0)$，因为位置代表不同角色。因此通常不能把 $A\times B$ 和 $B\times A$ 当作同一个集合。
4.1 多个位置组成元组
$S_1\times\cdots\times S_n$ 中的元素是 $(a_1,\ldots,a_n)$，其中每个 $a_i\in S_i$。课件专门使用 $S^{\times n}$ 表示 $n$ 份 $S$ 的笛卡尔积，以免和其他用途的 $S^n$ 混淆。于是：
$$ \{0,1\}^{\times3} =\{(0,0,0),(0,0,1),\ldots,(1,1,1)\} $$这个集合包含 $2^3=8$ 个三元组。更一般地，长度为 $n$ 的二进制串有 $2^n$ 种。
课件还用 $x^{\times n}$ 表示重复的元组 $(x,\ldots,x)$。例如 $1^{\times3}=(1,1,1)$，不是数值乘方 $1^3$。这是课件的特定记号，阅读时要看上下文。
5. 族与序列：保留“索引对应哪个对象”
设索引集合 $I=\{1,2,3\}$，并指定：
$$ x_1=5,\qquad x_2=5,\qquad x_3=9 $$这时有三个不同概念：
| 写法 | 关注什么 | 是否保留重复对应 |
|---|---|---|
| 集合 $\{x_i:i\in I\}=\{5,9\}$ | 出现过哪些值 | 不保留重复次数 |
| 族 $(x_i)_{i\in I}$ | 每个索引对应什么 | 保留 $x_1=x_2$ 这两个位置 |
| 序列 $(5,5,9)$ | 按索引顺序排列的值 | 保留顺序和重复 |
课件把族写成 $\{x_i\}_{i\in I}$。本文有时用圆括号 $(x_i)_{i\in I}$，只是为了在视觉上与普通集合区分。
族并不要求有顺序。 只有当索引集带有相应顺序时，才能按索引排列；由连续整数索引的族，就是这里讨论的序列。
还可以把族看成一个函数：
$$ f:I\to\{5,9\},\qquad f(1)=5,\ f(2)=5,\ f(3)=9 $$“族”和“函数”的对应关系很直接：索引是输入，被索引的对象是输出。
6. 集合族、两两不交与划分
6.1 多个集合的并与交
设：
$$ S_1=\{0,1,2\},\quad S_2=\{1,2,3\},\quad S_3=\{2,3,4\} $$则：
$$ \bigcup_{i=1}^{3}S_i=\{0,1,2,3,4\},\qquad \bigcap_{i=1}^{3}S_i=\{2\} $$- $x\in\bigcup_{i\in I}S_i$：至少存在一个 $i$，使 $x\in S_i$。
- $x\in\bigcap_{i\in I}S_i$：对每个 $i$，都有 $x\in S_i$。
课件讨论交集时要求 $I\ne\varnothing$。如果要讨论空索引族的交集，就需要额外说明所在的全集等约定，不在这里直接套用非空情形的直觉。
6.2 “两两不交”比“总交集为空”更强
$S_i\cap S_j=\varnothing$ 对任意不同的 $i,j$ 都成立，才叫两两不交。例如：
$$ T_1=\{1,2\},\quad T_2=\{2,3\},\quad T_3=\{1,3\} $$虽然 $T_1\cap T_2\cap T_3=\varnothing$，但 $T_1\cap T_2=\{2\}$，所以它们并非两两不交。
6.3 划分：每个元素恰好进入一个分组
要把集合 $S$ 划分成若干组，需要同时满足：
- 每组非空。
- 不同组两两不交。
- 所有组的并集等于 $S$，不能遗漏元素。
例如把 $S=\{0,1,\ldots,8\}$ 按除以 3 的余数分组：
$$ P_0=\{0,3,6\},\quad P_1=\{1,4,7\},\quad P_2=\{2,5,8\} $$
9 个元素全部出现，且每个只出现一次，因此这三个组构成 $S$ 的一个划分。模运算、等价类等后续知识，会反复使用这种“按规则分组”的思路。
7. 区间与无穷：边界属于不属于集合
对实数 $a\le b$：
| 区间 | 条件 | 端点情况 |
|---|---|---|
| $[a,b]$ | $a\le x\le b$ | 两端都包含 |
| $(a,b)$ | $a<x<b$ | 两端都不包含 |
| $[a,b)$ | $a\le x<b$ | 只包含左端 |
| $(a,b]$ | $a<x\le b$ | 只包含右端 |
例如 $2\in[2,5)$，但 $5\notin[2,5)$。区间描述的是实数范围，$[2,5)$ 不是只有整数 2、3、4，还包含 2.5 等实数。
还可以写 $[0,\infty)$ 或 $(-\infty,3]$。这里 $\pm\infty$ 不是实数元素，所以无穷一端不用表示“包含端点”的方括号。
在扩展实数的相应约定下，对有限实数 $x$，可以写 $x+\infty=\infty$，但不能把无穷当作普通数随意消去：
$$ \infty-\infty,\qquad 0\cdot\infty $$在这里都没有定义。若它们出现在极限问题中，是需要进一步分析的不定式，而不是已经算出了一个值。
8. 函数与映射：输入范围也是定义的一部分
写出：
$$ f:A\to B $$意味着对每个 $a\in A$，都有唯一一个 $f(a)\in B$。
- $A$ 是定义域：允许输入什么。
- $B$ 是陪域：声明输出属于哪个集合。
- $f(A)=\{f(a):a\in A\}$ 是像集，也常称实际值域：真正能得到哪些输出。
一定有 $f(A)\subseteq B$，但不一定等于 $B$。为了避免“值域”一词在不同教材中的用法差异，下面统一区分“陪域”和“像集”。
例如 $f:\mathbb R\to\mathbb R$、$f(x)=x^2$ 的像集是 $[0,\infty)$，不是整个陪域 $\mathbb R$。
8.1 单射：不同输入不碰到同一个输出
单射要求：
$$ f(a)=f(b)\Longrightarrow a=b $$等价地，$a\ne b$ 时必有 $f(a)\ne f(b)$。它不要求陪域的每个元素都被用上。
例：$A=\{0,1,2\}$、$B=\{a,b,c,d\}$，指定 $0\mapsto a$、$1\mapsto b$、$2\mapsto c$。这是单射，虽然没有输入映到 $d$。
8.2 满射：陪域里的每个元素都能被取到
满射要求 $f(A)=B$，即每个 $b\in B$ 都有至少一个原像。
例：$A=\{0,1,2\}$、$B=\{a,b\}$，指定 $0\mapsto a$、$1\mapsto b$、$2\mapsto a$。这是满射，但 0 和 2 碰到了同一个输出，因此不是单射。
8.3 双射：既不碰撞，也不遗漏
同时满足单射和满射，就叫双射。例如在 $A=\{0,1,2\}$、$B=\{a,b,c\}$ 之间，指定 $0\mapsto c$、$1\mapsto a$、$2\mapsto b$，便得到双射。
对元素数相等的两个有限集合，单射和满射等价；不能把“有限且元素数相等”的前提丢掉。例如 $f:\mathbb N\to\mathbb N$、$f(n)=n+1$ 是单射，却取不到 0，所以不是满射。
8.4 同一个公式，改变集合后性质会改变
仍用 $f(x)=x^2$：
| 定义域 → 陪域 | 单射？ | 满射？ | 原因 |
|---|---|---|---|
| $\mathbb R\to\mathbb R$ | 否 | 否 | $f(-1)=f(1)$，而负数取不到 |
| $\mathbb R\to[0,\infty)$ | 否 | 是 | 每个非负数都能取到，但正负输入仍会碰撞 |
| $[0,\infty)\to[0,\infty)$ | 是 | 是 | 非负输入与非负输出一一对应 |
因此，判断函数性质时，不能只看公式。
9. 逆映射、恒等映射、限制与扩张
9.1 逆映射不是倒数
若 $f:A\to B$ 是双射，才能在整个 $B$ 上定义双侧逆映射 $f^{-1}:B\to A$，使：
$$ f^{-1}(f(a))=a,\qquad f(f^{-1}(b))=b $$例如 $f:\mathbb R\to\mathbb R$、$f(x)=2x+1$，由 $y=2x+1$ 解出 $x$：
$$ f^{-1}(y)=\frac{y-1}{2} $$所以 $f(3)=7$、$f^{-1}(7)=3$。这里 $f^{-1}(y)$ 不是 $1/f(y)$。
单射但非满射的函数，可以在自己的像集上反向还原，却不能在声明的整个陪域上拥有双侧逆映射。
还有一种容易混淆的写法是集合的原像。即使 $f(x)=x^2$ 在 $\mathbb R$ 上没有逆函数，仍可以写 $f^{-1}(\{1\})=\{-1,1\}$；这里输入的是一个集合，表示“所有映到这个集合里的输入”，并不表示存在逆函数。
9.2 恒等映射与包含映射
恒等映射 $\operatorname{id}_A:A\to A$ 不改变元素：
$$ \operatorname{id}_A(a)=a $$若 $A'\subseteq A$，包含映射 $i:A'\to A$ 也规定 $i(a)=a$，但它把同一个元素视为更大集合中的元素。若 $A'\subsetneq A$，这个包含映射是单射，却不是满射。
9.3 限制与扩张：规则不变，允许的输入改变
给定 $f:A\to B$ 和 $A'\subseteq A$，把 $f$ 的输入限制在 $A'$ 上，得到：
$$ f|_{A'}:A'\to B,\qquad f|_{A'}(a)=f(a) $$例如把 $f:\mathbb R\to\mathbb R$、$f(x)=x^2$ 限制在 $A'=\{-2,-1,0,1,2\}$ 上，它的像集变成 $\{0,1,4\}$，但公式仍是平方。
反过来，如果一个更大定义域上的函数在原定义域内与旧函数一致，就叫旧函数的一个扩张。扩张只要求原来部分的值不变，不保证一定存在或唯一，也不自动要求连续等额外性质。
10. 函数复合：从右向左执行
若 $f:A\to B$、$g:B\to C$，复合映射为：
$$ g\circ f:A\to C,\qquad (g\circ f)(a)=g(f(a)) $$右边的函数先执行。 $g\circ f$ 是先做 $f$，再做 $g$。
设 $f(x)=x+1$、$g(x)=2x$，都在实数上定义，则：
$$ (g\circ f)(3)=g(4)=8,\qquad (f\circ g)(3)=f(6)=7 $$这说明函数复合一般不满足交换律。更一般地，要先确认前一步的实际输出能作为后一步输入；若集合接不上，连复合本身都可能无法按声明定义。
10.1 复合满足结合律，不意味着可以换顺序
当映射的定义域、陪域衔接时：
$$ (h\circ g)\circ f=h\circ(g\circ f) $$左右两边都是对输入先做 $f$，再做 $g$，最后做 $h$。改变括号不改变执行顺序，但把函数前后交换是另一回事。
10.2 复合的逆，要倒着撤销
若 $f$、$g$ 都是双射：
$$ (g\circ f)^{-1}=f^{-1}\circ g^{-1} $$上面的输入 3 经过“加 1，再乘 2”变成 8，还原时必须“先除以 2，再减 1”：
$$ 8\xrightarrow{g^{-1}}4\xrightarrow{f^{-1}}3 $$不能仍按正向顺序撤销，否则先减 1、再除以 2 会得到 3.5。
11. 映射的幂：重复执行，不是把输出乘方
当 $f:A\to A$ 时，可以反复把输出送回同一个函数：
$$ f^2=f\circ f,\qquad f^3=f\circ f\circ f,\qquad f^0=\operatorname{id}_A $$比如 $f(x)=x+1$：
$$ f^2(3)=f(f(3))=f(4)=5 $$而 $(f(3))^2=4^2=16$。映射的复合幂与函数值的数值乘方不同。
若 $f$ 是双射，还能重复执行逆映射，记作 $f^{-n}=(f^{-1})^n$。这里 $f^{-2}(3)=1$。
某些教材又会用 $\sin^2 x$ 表示 $(\sin x)^2$，因此看到上标时要结合作者约定；本文的 $f^n$ 沿用课件的复合幂含义。
12. 二元运算：两个输入，输出仍在同一个集合
集合 $S$ 上的二元运算，是一个映射：
$$ \star:S\times S\to S,\qquad (a,b)\mapsto a\star b $$这个定义同时要求：对 $S$ 中的每一对输入，结果都存在、唯一，并且仍属于 $S$。
| 集合与运算 | 是该集合上的二元运算吗？ | 原因 |
|---|---|---|
| 整数上的加法 | 是 | 任意两个整数相加仍是整数 |
| 整数上的减法 | 是 | 结果仍是整数，不要求交换律或结合律 |
| 自然数上的减法 | 否 | $1-2=-1\notin\mathbb N$ |
| 有理数上的除法 | 否 | 分母可以为 0，并非每一对输入都有结果 |
| 非零有理数上的除法 | 是 | 除数非零，结果也非零 |
12.1 结合律：允许改变括号
结合律要求：
$$ (a\star b)\star c=a\star(b\star c) $$加法满足结合律。但减法不满足：
$$ (5-3)-1=1,\qquad 5-(3-1)=3 $$因此不能因为减法是二元运算，就直接省略括号而不说明规则。
12.2 交换律：允许交换两个输入的位置
交换律要求 $a\star b=b\star a$。加法满足交换律，字符串拼接则不满足："ab" + "cd" 得到 "abcd"，交换后得到 "cdab"。
但字符串拼接满足结合律：无论先拼接前两个还是后两个，"a"、"b"、"c" 最后都得到 "abc"。这说明结合律与交换律是两个独立的问题。
反方向也有例子：在实数上定义 $a\star b=(a+b)/2$，这个运算满足交换律，却不满足结合律：
$$ (0\star0)\star2=1,\qquad 0\star(0\star2)=\frac12 $$12.3 子集的封闭性：缩小范围后还能不能一直算
假设 $\star$ 已经是 $S$ 上的二元运算。对 $S'\subseteq S$，若任意 $a,b\in S'$ 都有 $a\star b\in S'$，就称 $S'$ 对这个运算封闭。
例如在整数加法下：
- 偶数集合封闭，因为 $2m+2n=2(m+n)$ 仍是偶数。
- 奇数集合不封闭，因为 $1+3=4$ 不是奇数。
- $\{0,1\}$ 对加法不封闭，因为 $1+1=2$；但对乘法封闭，因为任意乘积仍是 0 或 1。
封闭性必须同时说明集合和运算。 只说“这个集合封闭”是不完整的。
13. 串联例子：一个有限集合上的可逆变换
下面是为本文补充的教学例子，用来串起集合、映射、复合、逆映射和封闭性。
13.1 确定输入和输出集合
取：
$$ S=\{0,1,2,3,4,5,6\} $$约定 $a\bmod7$ 是把整数 $a$ 除以 7 后，取 0 至 6 中的余数，例如 $12\bmod7=5$、$-2\bmod7=5$。
定义两个从 $S$ 到 $S$ 的映射：
$$ f(x)=3x\bmod7,\qquad g(x)=(x+2)\bmod7 $$列出全部输入，就能直接检查是否双射：
| $x$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| $f(x)$ | 0 | 3 | 6 | 2 | 5 | 1 | 4 |
| $g(x)$ | 2 | 3 | 4 | 5 | 6 | 0 | 1 |
| $E(x)=g(f(x))$ | 2 | 5 | 1 | 4 | 0 | 3 | 6 |
每行输出都恰好包含 $S$ 的 7 个元素，没有重复或遗漏，所以三个映射都是双射。
13.2 正向计算：先乘，再加
定义 $E=g\circ f$。输入 $m=4$：
$$ 4\xrightarrow{f}12\bmod7=5 \xrightarrow{g}7\bmod7=0 $$因此 $E(4)=0$。也可以合并写为 $E(x)=(3x+2)\bmod7$。
13.3 反向计算：先撤销加法，再撤销乘法
撤销 $g$ 很直接：$g^{-1}(c)=(c-2)\bmod7$。
撤销 $f$ 不能直接使用普通实数除法，因为取余丢掉了整数商；这里要利用：
$$ 3\times5=15\equiv1\pmod7 $$也就是说，模 7 意义下乘以 3 后再乘以 5，相当于不改变原来的余数。因此：
$$ f^{-1}(y)=5y\bmod7,\qquad D(c)=f^{-1}(g^{-1}(c))=5(c-2)\bmod7 $$对输出 $c=0$：
$$ 0\xrightarrow{g^{-1}}(-2)\bmod7=5 \xrightarrow{f^{-1}}25\bmod7=4 $$
最后回到原输入：$D(E(4))=4$。
13.4 为什么不能随便换一个乘数
把集合改成 $T=\{0,1,\ldots,7\}$，定义 $h(x)=2x\bmod8$，则：
$$ h(0)=0=h(4) $$它不是单射，像集只有 $\{0,2,4,6\}$。仅看到输出 0，无法判断原输入是 0 还是 4，因此不存在整个 $T$ 上的双侧逆映射。
这与前面“不同输入不能碰到同一个输出”的要求完全对应。可逆性是还原输入的条件，但可逆本身并不等于密码学安全。
14. 最容易混淆的记号
| 容易混淆的对象 | 应该怎样区分 |
|---|---|
| $x\in A$ 与 $X\subseteq A$ | 前者是元素属于集合，后者是集合包含关系 |
| $\varnothing$ 与 $\{\varnothing\}$ | 一个没有元素，一个有一个元素 |
| 集合、族、序列 | 分别关注不同的值、索引对应、按顺序的对应 |
| 总交集为空与两两不交 | 两两不交要求任意两个不同分组都无公共元素 |
| 陪域 $B$ 与像集 $f(A)$ | 声明的输出集合不一定全部被取到 |
| 单射与满射 | 单射不碰撞；满射不遗漏陪域元素 |
| $f^{-1}$ 与 $1/f$ | 逆映射与数值倒数不是一回事 |
| $g\circ f$ 与 $f\circ g$ | 复合从右向左执行，一般不能换顺序 |
| $f^n(x)$ 与 $(f(x))^n$ | 本文前者是反复执行映射，后者是数值乘方 |
| 结合律与交换律 | 一个改变括号，一个改变输入次序 |
| 封闭与可逆 | 输出留在集合里，并不保证能唯一还原输入 |
读完这一讲，应该能先看清集合与映射的范围，再讨论运算性质。后续学习整数、同余、欧几里得算法和群环域时，这些符号会一直使用；本篇先把它们的含义和计算方式固定下来。
15. 巩固练习
下面 10 道题按“记号辨析 → 映射计算 → 运算与可逆性”排列。建议先独立写出结果与理由，再查看第 16 节；
练习 1：可能性数量不等于整数位数
对应第 1、2、7 节。
- 长度为 6 的二进制串共有多少种？求这个数量的以 2 为底的对数。
- 正整数 64 的二进制表示需要多少位？为什么和上一问中的长度不同？
- 按本文约定，$0\in\mathbb N$ 是否成立？$\infty\in[0,\infty)$ 是否成立？
练习 2：元素、子集与集合运算
对应第 3 节。设：
$$ A=\{0,1,2\},\qquad B=\{1,2,3\},\qquad C=\{\varnothing,0\} $$- 求 $A\cup B$、$A\cap B$、$A\setminus B$，以及 $|A\cup B|$。
- 判断下面四个命题，并分别说明原因：
练习 3：有序对和重复位置
对应第 4、5 节。
- 设 $A=\{0,1\}$、$B=\{a,b\}$，列出 $A\times B$。其中有 $(a,0)$ 吗？
- 设 $I=\{1,2,3\}$，且 $x_1=4,x_2=4,x_3=7$。集合 $\{x_i:i\in I\}$ 有几个元素？序列 $(x_1,x_2,x_3)$ 有几个位置？
练习 4：哪些分组才是划分
对应第 6 节。设 $S=\{0,1,2,3,4,5\}$，判断下列三组分组方案是否构成 $S$ 的划分：
$$ \mathcal P=\big\{\{0,2,4\},\{1,3,5\}\big\} $$ $$ \mathcal Q=\big\{\{0,1,2\},\{2,3\},\{4,5\}\big\} $$ $$ \mathcal R=\big\{\{0,1\},\{2,3\}\big\} $$另外，$\mathcal Q$ 中三个分组的总交集是否为空？这能否说明它们两两不交？
练习 5：只改变集合，映射性质会怎样变化
对应第 8、9 节。设 $A=\{0,1,2\}$、$B=\{0,1,2,3\}$，定义 $f:A\to B$：
$$ f(0)=1,\qquad f(1)=3,\qquad f(2)=1 $$- 求像集 $f(A)$，判断它是否为单射、满射、双射。
- 保留原定义域和对应规则，只把陪域改成 $B'=\{1,3\}$，得到的新映射是否为双射？
- 在上一问基础上，再把定义域限制为 $A'=\{0,1\}$，得到 $h:A'\to B'$。它是否可逆？若可逆，写出全部逆向对应。
练习 6：原像存在，不代表逆函数存在
对应第 8.4、9.1 节。设 $f:\mathbb R\to\mathbb R$、$f(x)=x^2$。
- 求集合的原像 $f^{-1}(\{4\})$ 和 $f^{-1}(\{-1\})$。
- 为什么这不能说明 $f$ 有逆函数？
- 若定义 $q:[0,\infty)\to[0,\infty)$、$q(x)=x^2$，求 $q^{-1}(y)$，并用 $y=4$ 验证。
练习 7：先复合，再倒着还原
对应第 10 节。设 $f,g:\mathbb R\to\mathbb R$：
$$ f(x)=x+2,\qquad g(x)=3x,\qquad E=g\circ f $$- 分别计算 $(g\circ f)(1)$ 和 $(f\circ g)(1)$。
- 写出 $E(x)$ 和 $E^{-1}(y)$，计算 $E^{-1}(E(1))$。
- 如果错误地按 $g^{-1}\circ f^{-1}$ 的顺序还原 $E(1)$，会得到什么？
练习 8：映射的幂与数值的幂
对应第 11 节。本题规定 $f:\mathbb Z\to\mathbb Z$、$f(x)=x+2$，上标表示映射的复合幂。分别计算：
$$ f^0(1),\qquad f^2(1),\qquad f^{-2}(1),\qquad (f(1))^2 $$为什么 $f^2(1)$ 与 $(f(1))^2$ 这两种写法不能混用？
练习 9：新运算也要逐项检查性质
对应第 12 节。在整数集合上定义：
$$ a\star b=a+b+1 $$- 它是不是 $\mathbb Z$ 上的二元运算？
- 是否满足交换律和结合律？请对任意整数 $a,b,c$ 展开计算，而不是只试几个数。
- 偶数集合对这个运算是否封闭？它对普通加法的封闭性，能否直接用于这里？
练习 10：有限集合上的变换与还原
对应第 13 节。设 $S=\{0,1,2,3,4\}$，定义：
$$ E:S\to S,\qquad E(x)=(2x+1)\bmod5 $$- 按输入 0、1、2、3、4 的顺序列出输出，判断是否为双射。
- 利用 $2\times3\equiv1\pmod5$ 写出逆映射 $D$，并计算 $D(E(3))$。
- 若改为 $T=\{0,1,2,3,4,5\}$ 上的 $H(x)=2x\bmod6$，它是否仍可逆？给出一对碰撞输入。
- 一个变换是双射，是否就足以说明它具有密码学安全性？
16. 参考答案与解析
核对时重点看推理：否定一个“对所有输入成立”的性质，一个反例就够；肯定这种性质，则要覆盖全部输入，或给出一般性的计算依据。
练习 1 解析
长度为 6 的二进制串，每个位置有两种选择，所以共有 $2^6=64$ 种，且 $\log_2 64=6$。
整数 64 的二进制表示为 1000000，需要 7 位，也可以用 $\lfloor\log_2 64\rfloor+1=7$ 验证。6 位二进制串表示的是 0 至 63 共 64 种取值，不包含整数 64。
按本文约定，$0\in\mathbb N$ 成立；$\infty\in[0,\infty)$ 不成立。这个区间中的元素都是非负实数，无穷只是表示没有有限的上界，并不是一个被包含的实数端点。
练习 2 解析
$$ A\cup B=\{0,1,2,3\},\qquad A\cap B=\{1,2\},\qquad A\setminus B=\{0\},\qquad |A\cup B|=4 $$四个命题依次为：成立、成立、不成立、成立。
- $\varnothing\in C$：空集被直接列为 $C$ 的一个元素。
- $\varnothing\subseteq C$：空集是任何集合的子集。
- $\{0\}\notin C$：$C$ 的两个元素是空集和数 0，没有集合 $\{0\}$。
- $\{0\}\subseteq C$：左边集合唯一的元素 0 确实属于 $C$。
练习 3 解析
$$ A\times B=\{(0,a),(0,b),(1,a),(1,b)\} $$其中没有 $(a,0)$，因为第一个位置必须来自 $A$，第二个位置必须来自 $B$；它属于 $B\times A$。
集合 $\{x_i:i\in I\}=\{4,7\}$ 只有 2 个元素；序列 $(4,4,7)$ 有 3 个位置。前两个位置虽然取值相同，仍是两个不同的索引位置，不能合并。
练习 4 解析
- $\mathcal P$ 是划分：两组非空、互不相交，并且覆盖整个 $S$。
- $\mathcal Q$ 不是划分：元素 2 同时属于前两组，违反两两不交。
- $\mathcal R$ 不是划分：遗漏了 4 和 5，并集不等于 $S$。
练习 5 解析
原映射的像集是 $f(A)=\{1,3\}$。因为 $f(0)=f(2)=1$，它不是单射；因为陪域中的 0 和 2 都取不到，它也不是满射，因此不是双射。
只把陪域改为 $B'=\{1,3\}$ 后，新映射成为满射，但输入 0 和 2 的碰撞仍然存在，所以仍不是单射或双射。改变陪域只能消除这里的“遗漏”，不会消除碰撞。
再把定义域限制为 $A'=\{0,1\}$ 后，$h(0)=1,h(1)=3$。没有碰撞，也没有遗漏 $B'$ 中的元素，因此是双射，其逆映射为：
$$ h^{-1}:B'\to A',\qquad h^{-1}(1)=0,\qquad h^{-1}(3)=1 $$练习 6 解析
$$ f^{-1}(\{4\})=\{-2,2\},\qquad f^{-1}(\{-1\})=\varnothing $$这里求的是“所有能映到指定集合中的输入”，结果可以有多个元素，也可以为空，并不要求存在逆函数。原映射有 $f(-2)=f(2)=4$ 的碰撞，而且取不到任何负数，既非单射也非满射。
对 $q:[0,\infty)\to[0,\infty)$，每个非负输出恰好对应一个非负输入，所以：
$$ q^{-1}(y)=\sqrt y\quad(y\ge0),\qquad q^{-1}(4)=2,\qquad q(2)=4 $$注意，这里的逆函数值是数 2，不是集合 $\{-2,2\}$，也不是倒数 $1/q(4)=1/16$。
练习 7 解析
$$ (g\circ f)(1)=g(3)=9,\qquad (f\circ g)(1)=f(3)=5 $$正向先加 2 再乘 3，所以 $E(x)=3(x+2)=3x+6$。反向必须先除以 3，再减 2：
$$ E^{-1}(y)=(f^{-1}\circ g^{-1})(y)=\frac y3-2,\qquad E^{-1}(E(1))=\frac93-2=1 $$如果把撤销顺序写反，会得到：
$$ (g^{-1}\circ f^{-1})(9)=\frac{9-2}{3}=\frac73\ne1 $$练习 8 解析
$$ f^0(1)=1,\qquad f^2(1)=f(f(1))=f(3)=5 $$ $$ f^{-1}(x)=x-2,\qquad f^{-2}(1)=(1-2)-2=-3 $$ $$ (f(1))^2=3^2=9 $$复合幂表示连续执行同一个映射，因此本题 $f^n(x)=x+2n$；数值乘方则是把一次输出相乘。重复“加 2”和把输出“平方”显然是两种不同操作。
练习 9 解析
任意两个整数相加再加 1，结果存在、唯一，且仍是整数，所以这是 $\mathbb Z$ 上的二元运算。
对任意整数 $a,b,c$：
$$ a\star b=a+b+1=b+a+1=b\star a $$ $$ (a\star b)\star c=(a+b+1)+c+1=a+b+c+2 $$ $$ a\star(b\star c)=a+(b+c+1)+1=a+b+c+2 $$因此交换律、结合律都成立。这里用的是任意输入的一般计算，而不是用有限次试算代替证明。
偶数集合对这个运算不封闭：$0\star0=1$ 已经构成反例。一般地，$(2m)\star(2n)=2(m+n)+1$ 是奇数。偶数集合对普通加法封闭，不代表它对换过规则的新运算也封闭。
练习 10 解析
| $x$ | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| $E(x)$ | 1 | 3 | 0 | 2 | 4 |
全部输出恰好把 $S$ 中的元素各取到一次，因此是双射。先撤销加 1，再在模 5 意义下乘以 2 的逆元 3，得到：
$$ D(c)=3(c-1)\bmod5 $$ $$ E(3)=7\bmod5=2,\qquad D(2)=3(2-1)\bmod5=3 $$不仅这一对数能还原，对任意 $x\in S$，都有：
$$ D(E(x))\equiv3((2x+1)-1)=6x\equiv x\pmod5 $$因为 $D(E(x))$ 和 $x$ 都取 0 至 4 中的代表元，所以它们实际相等。类似地，$E(D(c))\equiv2\cdot3(c-1)+1\equiv c\pmod5$，也会还原任意 $c\in S$。
换成模 6 的映射后，$H(0)=H(3)=0$，两个不同输入发生碰撞，所以不存在整个 $T$ 上的双侧逆映射。
课件来源
本文根据《Number Theory and Algebra in Cryptography》Lecture 1: Introduction and preliminaries 整理。
