群、环、域、椭圆曲线

一、运算与群

1. 映射？笛卡尔积？
   设 A 和 B 是两个集合，R 是 A 和 B 之间的元素的对应关系，如果 R 满足：对于 A 中的每一个元素，通过 R 在 B 中都存在唯一一个元素与之对应，则称对应关系 R 为从集合 A 到 B 的映射，其中 A 称为原像集，B 称为像集。集合 A、B 的笛卡尔积为集合 A×B={(x, y)|x∈A, y∈B}。

2. 一元运算（本身映射到本身）；二元运算（笛卡尔积到本身的映射）；运算是一元运算还是二元运算的简称？定义域非空 P232

3. 什么是运算满足结合律？（要指出是对定义域中任意元素）什么是单位元？零元？什么是可逆元和逆元？（前提是要有单位元）负元？交换律？如何证明单位元是唯一的？ P232
   （假设存在两个单位元）

4. 群的定义（G 本质上是个集合吗）？乘群？加群？群 G 的阶 |G|？有限群和无限群？阿贝尔群？P233
   （非空集合中的运算满足结合律，单位元，可逆性）

5. 半群？交换半群？P232 半群中若有可逆元，则其逆元是唯一的。P233

6. 证明：(a₁…a_i1)…(a_ik+1…a_n)=a₁a₂…a_n-1a_n P238
   （涉及元素个数而且元素最少的时候容易证，可以对元素个数用数学归纳法和分类讨论）

7. 如何定义 aⁿ？如何定义 a⁰ 和 a^-n？P239

8. 什么是子群？符号？什么是平凡子群？（VS：显然因数）什么是真子群？P241
   （从定义域的子集出发）

9. 什么是 G=<a>？什么是 G 的生成元？什么是某元素在群中的阶？（元素的阶和群的阶符号不同）
   （某元素生成的循环子群的阶称为该元素在群中的阶）

二、环与域

1. 什么叫做环？什么叫做交换环？什么叫有单位元环？P267
   （环：有加法和乘法运算，对于加法构成交换群，对于乘法满足结合律，乘法对加法满足左右分配律，一个定义涵盖了交换、结合、分配三个词汇）（交换环、有单位元环都是针对乘法运算来说的，毕竟集合对于加法运算已经构成交换群了）

2. 什么是域？P271
   （交换环，有单位元环，非零元均为可逆元，即：对加法构成交换群，非零元对乘法构成交换群）

3. 域的详细定义？P271
   （即：从运算上展开说对于加法运算构成交换群，非零元对于乘法运算构成交换群，乘法对加法运算满足分配律）
4. 环的特征？P272
   （最小；不存在则为 0）
   群：加减 -> 环：乘 （整数环）-> 域：除（非零元）（有理数、实数、复数域）

三、椭圆曲线

1. 椭圆曲线的定义？P340
   （最高的两个三次方系数都是 1；左边有个 xy 混合，除此之外 y 在等号左边，x 在等号右边；奇数项在等号左边，偶数项在等号右边）（本质上是一系列点的集合，注意无穷远点的集合，注意定义域）

2. 有限域上的椭圆曲线上的加法运算满足结合律、单位元、可逆性、交换律，即椭圆曲线对于运算“⊕”构成一个交换群。

3. 椭圆曲线的离散对数问题：P、Q 为有限域上椭圆曲线点集 E_p(a, b) 中的元素，且 Q=kP，k 为正整数，对于给定的 k、P，计算 Q 比较容易，而对于给定的 P、Q，计算 k 比较困难。（参考这个回答中的动图以形象理解）

4. 有限域上椭圆曲线密码体制（ECC）的执行步骤：
   Alice（或 Bob）选择一个有限域上的椭圆曲线 E_p(a, b)；
   Bob 选择 E_p(a, b) 的元素 G 使得 G 的阶 m 是一个大素数，秘密选择整数 k。计算 P=kG，公开 (p, a, b, G, P)，保密 k。其中 k_b=P=kG 为 Bob 的公钥，k_b‘=k为 Bob 的私钥，Bob 将其公钥 k_b 发送给 Alice。
   Alice 加密：Alice 将消息 m 编码为 (x, y) 形式的点 P_m。随机选择一个正整数 r，对 P_m 产生密文 {rG, C_m=P_m+rK_b}。
   Bob 解密 C_m-k_b‘(rG)=P_m+rk_b-krG=P_m+r(kG)-rkG=P_m。
   （Bob 取椭圆曲线，计算公钥 k_b 为 G 的 k 次连加，Alice 计算公钥的 r 次连加和 G 的 r 次连加并把 G 的 r 次连加累加到明文上得到密文；Bob 把 Alice 发送的公钥的 r 次连加再连加 k 次，从密文中减去得出明文）（G K P P_m r C_m）