文档介绍：数论相关基础知识
提纲
群环域
模运算
欧几里德算法
有限域GF(p)
多项式运算
有限域GF(2^n
Abstract Algebra
Algebraic structure
Semigroup
closure封闭性, associative结合律
Group
→
closure, associativity, identity单位元, Inverse逆元
Ring
→
+: associativity, commutativity交换律, identity, Inverse0
associativity, distributivity分配律
Field
a ring
multiplicative inverse乘法逆元
Lattice. Boolean
群 Group
集合,元素
元运算
封闭性、结合律
单位元、逆元
有限群、无限群
交换群(Abel)x
循环群
生成元
环Ring
环R
二元运算:加法+、乘法x
(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
((。
(Al Closure undar additie
If a and b balong to S, the is also
(A2)Associativity of addition
a+(+c=(a+b)+c for alla, b, cmS
(A3)Additive identity
There is an element o in r such that
E-
at0=0+asaf all ain s
(A4)Additive inverse
For each a in s there is an element-a in S
such that a(-2)=(-2)+2=0
(A)Commutativity of addton: +6=6+a for alla, bns
Ml)Closure under multiplication: If a and b balong to S, then ab is alsonS
M2) Associativity of mutiplication: a(bc) =(abe for alla, b, cinS
MB) Ditmibuuve laws
a(b+c=ab t ac for , cinS
(a+b)=ac befor alla, b cmS
MM4)Commutativity of multiplication: ab =ba for alla, b in S
(M5)Multiplicative identity:
here is an element l in s such that
al=las afor all ain s
M6)No zero divisors
a b in saud ab=0 then either
Cor b=o
M门 Multiplicative inverse:
If a belones to s and a 0. there is an
element c-m ssuch that ad=c-a=l
域相关概念及定理
域的特征
任意元素a的n次累计和为0的最小的n
域的特征要么是素数,要么是0(没有);
素域:没有非{0}真子域的域;
有限域的阶是p^n(其中p是素数)
有限域的乘法群是循环群;
可逆在加/解密中的重要性
加密的操作对象是比特分组,通常被看作整数
加密是对整数的变换。这种变换必须能恢复(
解密时),即可逆。如果加密是乘法,则解密
就是除法,而域上正好有除法-乘法逆元。
对于8bts字节,希望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三