群、环、域

群G， {G，·}

满足公理：
- 封闭性
- 结合律
- 单位元
- 逆元
有限群，无限群，群的阶即G中元素的数量
交换群，满足交换律
循环群，G = {a^k}, a是生成元

环R，{R，+，*}

满足公理：
- *满足交换群
- +满足半群
- *对+满足分配率
- 无零因子：如果R中有a和b满足ab=0，则a=0且b=0

域F，{F，+，*}

满足公理：
- F是一个整环
- 乘法逆元
- 就是一个集合，在其上进行加减乘除不脱离该集合

模算数运算

因子

如果a=mb即b|a
以下关系成立：
- 如果a|1，则a=+-1
- 如果a b，则a=+-b
- 如果b g，且b h，则b (mg + nh)

同余

a mod n = b mod n，则a和b模n同余
同余是一种等价关系，满足自反，对称，可传递

加法逆元和乘法逆元

对每一个w，存在一个z能够让(w+z) mod n = 0，则z是加法逆元
同上，如果wz mod n = 1，注意不是0，则z是乘法逆元

欧几里得算法

gcd(a, b) = gcd(b, a%b)

辗转相除直到第一个参数能够整除第二个参数即可

这里不多赘述

有限域GF

有限域的阶(元素个数)必须是一个素数的幂p^n

两种特殊情况：GF(p), GF(2^n)

最简单的有限域：GF(2)

+ 0 1   x 0 1   w -w w^-1
0 0 1   0 0 0   0 0  
1 1 0   1 0 1   1 1  1

阶为p的有限域GF(p):

{0, 1, 2, 3, …., p - 1}

因为w与p互素，如果用w乘域中所有的数mod p得到的余数将会以不同的次序涵盖域中的所有数，即余数集合是{0, 1, …, p-1}的置换型

举个栗子：

p是11，w是9，GF(11)是{1, 2, …, 10}

置换后：

{9, 7, 5, 3, 1, 10, 8, 6, 4, 2}是原来的域的置换型

计算乘法逆元，扩展欧几里得算法

计算乘法逆元表示为：ax mod n = 1, 已知a，求x

引理：如果gcd(a, n) = 1，对每个i, j, 有i < j < n，则ai mod n 不会等于 aj mod n

定理：如果gcd(a, n) = 1, 一定存在整数x，满足ax mod n = 1，可以用扩展欧几里得算法求逆

ax + by = d = gcd(a, b)
如果gcd(a, b) = 1，则有ax + by = 1
将 1 mod a = 1 mod a的1用上式进行替换
    ( (ax mod a) + (by mod a) mod a) = 1 mod a
ax mod a = 0，所以：
    (by mod a) mod a = 1 mod a，所以：
    by mod a = 1
如果by mod a = 1，则y = b^-1

线性O(n)内求逆元代码：

for(int i = 2; i < MAXN; ++i){
    inv[i] = mul(inv[mod%i], mod - mod / i, mod);
}