数论相关基础知识.ppt

文档介绍：数论相关根底知识
提纲
群环域 ↓
模运算 ↓
欧几里德算法 ↓
有限域GF(p) ↓
多项式运算 ↓
有限域GF(2^n) ↓
Abstract Algebra
Algebraic structure
Semigroup
closure封闭性, associative 结合律
Group 
closure, associativity, identity单位元, inverse逆元
Ring 
+: associativity, commutativity交换律, identity, inverse 0
*: associativity, distributivity分配律
Field 
a ring
multiplicative inverse 乘法逆元
Lattice, Boolean
群环域
群 Group
集合，元素
二元运算 ·
封闭性、结合律
单位元、逆元
有限群、无限群
交换群〔Abel〕
循环群
生成元
环 Ring
环R
二元运算: 加法+、乘法×
(R, +)是交换群
乘法封闭性、乘法结合律
分配律 a(b+c) = ab+ac
交换环
乘法交换律
整环〔交换环且〕
乘法单位元1
无零因子: ab=0 a=0或b=0
域 Field
域F
F是整环
存在乘法逆元(0除外)
除法定义: a/b = a(b-1)
有理数域、实数域、复数域
有限域
Group >> Ring >> Field
域相关概念及定理
域的特征
- 任意元素a的n次累计和为0的最小的n；
域的特征要么是素数，要么是0(没有)；
素域：没有非{0}真子域的域；
有限域的阶是p^n〔其中p是素数〕；
有限域的乘法群是循环群；
可逆在加/解密中的重要性
加密的操作对象是比特分组，通常被看作整数
加密是对整数的变换。这种变换必须能恢复(解密时)，即可逆。如果加密是乘法，那么解密就是除法，而域上正好有除法---乘法逆元。
对于8bits字节，希望Z256是域，但它不是；于是转而寻求GF(2^8)，它是域。
AES的S盒是基于模2系数的模某8次不可约多项式的剩余类。
模运算
模运算即求余数〔C语言中的运算符％〕
x mod n＝a
其中0≤a<n, 且有证书k使kn＋a＝x
如 5％3＝2；8％7＝1；16％12＝4
同余关系
假设x mod n＝y mod n [＝ a]，那么说x和y是模n同余的，记x≡y mod n
如 13≡6 mod 7
20≡7 mod 13
因子≡0 mod 倍数