信息安全数学基础环和域基础知识

信息安全数学基础环和域基础知识第一页，共四十八页，编辑于2023年，星期六环的定义环(Ring)

:一个非空集合S上有两种运算：加法“+”和乘法“∘”，如果这两种运算满足以下性质，就称为环：(R,+)是一个交换群，加法单位元记为0（称为零元）；R关于乘法“∘”满足结合律:(a∘b)∘c=a∘(b∘c),并有单位元,记为1；分配律成立:(a+b)∘c=a∘c+b∘c,c∘(a+b)=c∘a+c∘b.注：0是抽象的写法，不同于整数中的0.

“+”和“∘”是抽象的运算第二页，共四十八页，编辑于2023年，星期六环的例子（1）在通常的加法和乘法运算下，Z,Q,R和C都是环，加法单位元为0，乘法单位元为1。第三页，共四十八页，编辑于2023年，星期六环的例子（2）对任意n>0，在模n加法和模n乘法下，Zn是一个环。加法单位元为0，乘法单位元为1。第四页，共四十八页，编辑于2023年，星期六环的例子(3)多项式环Z[x]第五页，共四十八页，编辑于2023年，星期六环中的零元对于环中的任意元素a,都有0a=a0=0一般地，0与1不相等，否则1a=a,而0a=0，这表明环中只有一个元素，平凡情形，一般不考虑所以0关于乘法没有可逆元第六页，共四十八页，编辑于2023年，星期六环的几个性质设R是一个环,∀a,b∈R,有:a(-b)=(-a)b=-(ab)(-a)(-b)=ab

第七页，共四十八页，编辑于2023年，星期六交换环

类似于交换群的定义，如果一个环关于乘法运算具有可交换性，就称它为交换环。第八页，共四十八页，编辑于2023年，星期六无零因子环设R是一个环,如果存在a,b∈R,a≠0,b≠0,但ab=0,那么称R是有零因子环,否则称R是无零因子环.ab=0⇒a=0或b=0.第九页，共四十八页，编辑于2023年，星期六无零因子环的性质性质1.设R是无零因子环,那么若a≠0,ab=ac,则b=c;若a≠0,ba=ca,则b=c.性质2.设R是无零因子环,那么R中非零元的加法阶相等,或者为∞,或者为素数.第十页，共四十八页，编辑于2023年，星期六子环、理想和商环第十一页，共四十八页，编辑于2023年，星期六子环(subring)设R是一个环,S是R的非空子集,如果S关于R的运算也构成环,则称S是R的子环.第十二页，共四十八页，编辑于2023年，星期六理想(Ideal)设R是一个环,I是R的一个子环,

如果∀a∈I,

r∈R,有ra∈R,ar∈R,则称I是R的一个理想.第十三页，共四十八页，编辑于2023年，星期六理想的例子F[x]为数域F上的一元多项式环,I={a1x+a2x2+…+anxn|ai∈F,n∈N},

即I是由所有常数项为0的多项式构成的集合,

则I是F[x]的理想.第十四页，共四十八页，编辑于2023年，星期六主理想由R中一个元素a生成的理想称为主理想.第十五页，共四十八页，编辑于2023年，星期六商环设I是环R的理想,在加法商群R/I上定义如下乘法(x+I)(y+I)=(x+y)+I

则R/I关于加法和乘法构成一个环.第十六页，共四十八页，编辑于2023年，星期六环同态设R和R’是两个环,f是R到R’的一个映射,如果∀a,b∈R,均有f(a+b)=f(a)+f(b),f(ab)=f(a)f(b),

那么称f是R到R’的环同态映射.

如果f是满射,那么称R和R’同态;

如果f是双射,那么称R和R’同构.类似的有环同态基本定理第十七页，共四十八页，编辑于2023年，星期六概念的类比群环正规子群理想循环群主理想商群商环第十八页，共四十八页，编辑于2023年，星期六域的定义

域(Field)

非空集合F，若F中定义了加和乘两种运算，且满足：1)F关于加法构成阿贝尔群，加法恒等元记为02)F中所有非零元素对乘法构成阿贝尔群，乘法恒等元记为13)加法和乘法之间满足分配律则F与这两种运算构成域每一个非零元都是可逆元的有单位元的交换环如实数域\复数域\有理数域第十九页，共四十八页，编辑于2023年，星期六域的例子（1）

在通常的加法和乘法运算下，Q,R和C

都是域。第二十页，共四十八页，编辑于2023年，星期六域的例子（2）

令p是一个素数，在模p加法和模p乘法运算下，Zp是一个域.

也记为Fp或者GF(p).第二十一页，共四十八页，编辑于2023年，星期六

注意：整数环Z不是域；当n是合数时，Zn不是域。有限群、子群、商群和群的阶的概念可以直接推广到环和域中。第二十二页，共四十八页，编辑于2023年，星期六域的特征F是域，其特征char(F)定义为单位元1的加法阶,即使得的最小自然数n，如果不存在这样的自然数，那么记char(F)=∞.性质：如果char(F)有限，那么一定是素数.第二十三页，共四十八页，编辑于2023年，星期六域的例子（3）第二十四页，共四十八页，编辑于2023年，星期六构造方法

域上的多项式环不可约多项式第二十五页，共四十八页，编辑于2023年，星期六利用不可约多项式构造有限域ZZpF[x]F[x]/f(x)Fp=Zpp为素数F为p阶有限域f为n次不可约多项式F[x]/f(x)为pn阶有限域第二十六页，共四十八页，编辑于2023年，星期六域上的多项式的带余除法

设F是一个域，f,g是F[x]中的两个多项式，且g不为0，类似于整数的除法：

f=gq+r，其中，q,r是F[x]中的两个多项式，且deg(r)<deg(g).第二十七页，共四十八页，编辑于2023年，星期六带余除法的例子

f(x)=x5+x4+x3+x2+x+1∈F2[x]g(x)=x3+x+1∈F2[x]q=x2+x,r=x2+1第二十八页，共四十八页，编辑于2023年，星期六不可约多项式

定义:设F是一个域，f(x)∈F[x],f(x)的次数为正数，若f(x)=g(x)h(x)，其中f(x),h(x)∈F[x],则g(x)和h(x)中必有一个为常数多项式,那么称f(x)是不可约的.第二十九页，共四十八页，编辑于2023年，星期六

注意：多项式的可约性依赖于该多项式定义在什么样的代数结构上.一个多项式在一种代数结构上不可约，但可能在另一种代数结构上就是可约的.第三十页，共四十八页，编辑于2023年，星期六例

对于二次多项式f(x)=x2-2x+2：.（1）在复数域上可约；（2）在实数域上不可约；（3）在F3上不可约.第三十一页，共四十八页，编辑于2023年，星期六利用不可约多项式构造域定义:F[x]是域F上的多项式环,f,g,r∈F[x],g≠0,满足f=gq+r,deg(r)<deg(g),称r为f除以g的余式,记为r≡f(modg).考虑F[x]中所有多项式模g(x)的余式,将这些集合称为F[x]模g(x)的多项式,记为F[x]/g(x).第三十二页，共四十八页，编辑于2023年，星期六利用不可约多项式构造域

令F是一个域，f(x)是F[x]中的一个非零多项式，那么F[x]/f(x)是一个环，当且仅当f(x)在F上不可约时，F[x]/f(x)是一个域.第三十三页，共四十八页，编辑于2023年，星期六

f(x)是F[x]中的一个不可约多项式，当F是域时，F[x]/f(x)是一个域.将f(x)称为域F[x]/f(x)的定义多项式.第三十四页，共四十八页，编辑于2023年，星期六定理

令F为含有p个元素的域，f(x)是F上的n次不可约多项式，那么域F[x]/f(x)中元素的个数是pn.F[x]/f(x)是F[x]中所有次数小于deg(f)=n、系数取遍F中所有p个元素的多项式全体构成的集合.共有pn个这样的多项式.第三十五页，共四十八页，编辑于2023年，星期六

注意：在此定理中，并没有假设p是素数，事实上，F可以是任意域，称F[x]/f(x)为由基域F通过域扩张得到的扩域.第三十六页，共四十八页，编辑于2023年，星期六Pn阶域的存在性Zp是阶为p的域；对任意的有限域F和任意的正整数n，F[x]中一定存在n次不可约多项式.

推论

对于每一个素数p和每一个正整数n，都存在一个阶为pn的有限域.第三十七页，共四十八页，编辑于2023年，星期六域Fp[x]/f(x)中结构是很清楚的，它仅是所有次数小于n、系数在Fp的所有多项式的集合；在同构的意义下，这是唯一的阶为pn的有限域.第三十八页，共四十八页，编辑于2023年，星期六第三十九页，共四十八页，编辑于2023年，星期六例：由GF(2)上的既约多项式p(x)=x4+x+1扩成GF(24)4位向量形式多项式形式生成元幂形式指数形式

000000-∞00011a000010xa110100x2

a2

21000x3a330011x+1a440110x2+xa551100x3+x2a66第四十页，共四十八页，编辑于2023年，星期六4位向量形式多项式形式生成元幂形式指数形式

1011x3+x+1a770101x2+1a881010x3+xa990100x2

a10

100111x2+x+1

a11111110x3+x2+xa12121111x3+x2+x+1a13131101x3+x2+1