有限域
域¶
域 𝐹 是定义了两个二元运算+,×的集合，分别称为加法和乘法，满足以下性质：
- 满足整环的性质（乘法封闭性、乘法结合律、分配率、乘法交换律、乘法单位元、无零因子）
- 多了一个乘法逆元的性质：对于∀𝑎∈𝐹，且𝑎≠0，𝐹中存在一个逆元元素，记为\(a^{-1}\)，使得\(a\times a^{-1}= 1\)
有限域基本结论¶
有限域的阶（元素个数）必须是一个素数的幂，即\(p^n\)，阶为\(p^n\)的有限域一般记为\(GF(p^n)\)
有两种有限域：
- \(n=1, GF(p)\)
- \(n>1, GF(p^n)\)，密码学中广泛使用
有限域\(GF(p)\)被定义为整数\(\{0,1,\dots,p-1\}\)的集合\(Z_p\)，其运算为模\(p\)的算术运算
当𝑝比较小的时候，求元素的乘法逆元很容易，可以通过构造乘法表的形式进行
多项式运算类型¶
- 使用代数基本运算的普通多项式运算
- 系数运算是模𝑝运算的多项式运算，即系数在有限域𝐺𝐹(𝑝)中
- 系数在有限域𝐺𝐹(𝑝)中，且多项式被定义为模一个𝑛次多项式𝑚(𝑥)的多项式运算
普通多项式运算¶
一个n次多项式的表达式为
\[f(x)=\sum_{i=0}^{n}a_ix^i\]
其中\(a_i\)为指数集\(S\)中的元素，称为系数集，且\(a_n\neq 0\)，称𝑓(𝑥)是定义在系数集𝑆上的多项式
系数在𝒁𝒑中的多项式运算¶
\(GF(2)\)上有多少个多项式？
考虑系数为域𝐹中元素的多项式，称之为域𝐹上的多项式
如果域𝐹上每个不同的多项式看成集合中的元素，则这个集合是一个环，称为多项式环（Polynomial Ring）
有限域中多项式的除法：给定𝑛次多项式𝑓(𝑥)和𝑚次多项式𝑔(𝑥)，𝑚≤n
如果用𝑔(𝑥)除𝑓(𝑥)，可得到一个商𝑞(𝑥)和余数𝑟(𝑥)，满足:𝑓(𝑥)=𝑞(𝑥)𝑔(𝑥)+𝑟(𝑥)