1群、环、域概念
A1：加法的封闭性：如果a 和b 属于G ，则a+ｂ也属于G
A2：加法结合律：对G 中的任意元素a,b,ｃ,ａ＋(b+c)=（a ＋ｂ)+c
A3:加法单位元:G 中存在一个元素0，使得对于G 中的任意元素ａ，有a+０=０+a
A4:加法逆元:对于Ｇ中的任意元素a ，G 中一定存在一个元素a,使得
? a+（-a)＝（－a)＋a ＝０
Ａ5：加法交换律:对于Ｇ中的任意元素a 和b ，有a+b=ｂ+a
M1:乘法的封闭性:如果a 和b 属于Ｇ,则ａｂ也属于G
M2:乘法结合律：对于G 中的任意元素a,b,ｃ有ａ(bc)＝(ab ）c
M3：乘法分配了:对于Ｇ中的任意元素a,b,ｃ,有a(b ＋c)＝ab+ac 和(a ＋ｂ)ｃ=ac+ｂc
M4：乘法交换律：对于G 中的任意元素a ，b 有a ｂ＝ba
M5:乘法单位元:对于G 中的任意元素a,在Ｇ中存在一个元素１，使得a1=１a ＝ａ
M6:无零因子:对于G 中的元素ａ,b,若ab=0，则必有a=0或ｂ=0
M7：乘法逆元：如果a 属于G ，且a 不为０,则G 中存在一个元素1-a ，使得 111==--a a aa
满足A1--－A ４称为群
满足A1--－Ａ5称为可交换群
满足Ａ1-－-M ３称为环
满足A1---M ４称为可交换换
满足A １---Ｍ６称为整环
满足A1－－-M ７称为域
2循环群：如果群中的每一个元素都是一个固定元素)(G a a ∈的幂k a （k 为整数), 则称群G 是循环群。我们认为元素a 生成了群G ，或者说ａ是群G 的
生成元。
循环群总是交换群
3模运算
)mod ()mod (n b n a =则称整数ａ和b 是模n 同余的，可以表示为：)(mod n b a ≡ 若b 整除ａ。则用符号：a |b 表示。其性质可表示如下：
①如果a|1,那么a=-1或1。
②如果ａ｜ｂ,且b|a ，那么a=b 或ａ=-b
③任何不等于零的数整除0
④如果b ｜g 且b|h ，那么对任意整数m,n 都有b ｜(mg ＋nh)
证明性质④：
如果b|g ，那么1g b g ?=,ｇ为整数。
如果b ｜h ，那么1h b h ?=，h 为整数。
于是：)(1111nh mg b nbh mbg nh mg +?=+=+
因此b 整除mg+nh.
同余的性质:
１如果ｎ|（ａ-b),,那么()n b a mod ≡
2()n b a mod ≡隐含()n a mod b ≡
3()n b a mod ≡,()n c b mod ≡隐含()n a mod c ≡
性质1证明：
如果)(|b a n -,那么k ?，k 为整数。使得()kn b a =-，
??则有()[]()n b n kn b n a kn b a mod mod )mod (=+=?+=
即得()n b a mod ≡。
性质２证明：
由()n b a mod ≡得：)mod ()mod (n b n a =即Z r k k ∈?,,21，满足
???+=+=r n k b r
n k a 21……① 由①可推出()n k k a b )(12-=-,由性质1可知()n a mod b ≡成立
则得证。
性质3证明:
由性质2证明过程知:Z r k k k ∈?,,,321满足:
()()?
??-=--=-n k k b c n k k a b )()(2312……② 由②可以推出()n k k c a )(21-=-，由性质1可知()n a mod c ≡
模算术运算有如下性质:
1()()[]()n b a n n b n a mod mod mod mod +=+
2()()[]()n b a n n b n a mod -mod mod -mod =
3()()[]()n b a n n b n a mod mod mod mod ?=?
性质１证明：
设()a r n a =mod ，()b r n =mod b 则Z k j ∈?,,使得??
?+=+=kn
r b jn r a b a 那么有: ()()()()()()()[]n
n b n a n
r r n n k j r r n
kn r jn r n b a b a b a b a mod mod mod mod mod mod mod +=+=+++=+++=+
即得证。
性质２证明:
由性质1证明过程知Z k j ∈?,使得?
?
?+=+=kn r b jn r a b a 那么有： ()()()()()()()[]n
n b n a n
r r n n k j r r n
kn r jn r n b a b a b a b a mod mod -mod mod -mod --mod --mod -==+=+=
性质3证明:
前半段证明如上，
()()()()()()[]n
n b n a n
r r n jkn n k r j r r r n
jkn kn r jn r r r n b a b a a b b a a b b a mod mod mod mod mod mod mod 22?==+++=+++=?
定义比n 小的非负整数集合为(){}1,,1,0-=n Z n 。这个集合称为剩余类集,或 模n 的剩余类。
n Z 中每一个整数都代表一个剩余类,我们可以将模n 的剩余类表示为：
]1[,],2[],1[],0[-n ，其中()}mod :{][n r a a a r ≡=是一个整数，。
如果()()()n c a b a mod +≡+，那么()n c b mod ≡
若a 与ｎ互素，如果()()()n c a b a mod ?≡?，那么()n c b mod ≡
n Z 中整数模运算性质：
交换律:()n w x n x w mod )(mod +=+
()n w x n x w mod )(mod ?=?
结合律：()()()n y w x n y x w mod )(mod ++=++
()()()n y x n y x w mod )w (mod ??=??
分配律：()()()()n y x y n y x w mod ))w (mod ?+?=?+
单位元：()n w n w mod mod 0=+
()n w n w mod mod 1=?
加法逆元(-ｗ)：对于n Z 中的任意w,存在一个z 使得n z w mod 0≡+
加法逆元：对每一个n Z ∈ω,存在一个u,使得ｗ+ｕ=0 mod n,记为u=-w,显然在模 n 下,-ｗ=n-w 。
如果n d c n b a mod ,mod ≡≡，则有
()()n d b c a mod ±≡±,
特例n c b c a mod ±≡±,
更一般式:()()n dy bx cy ax mod +≡+，()Z y x ∈,
n bd ac mod ≡
特例：n bc ac mod ≡
()()n b f a f mod ≡其中ｆ(x)为任意给定的一个整系数多项式
最大公约数:]||,max[),gcd(b k a k k b a 和满足=
欧几里得算法:对于任意非负整数ａ和任意正整数b 有)mod ,gcd(),gcd(b a b b a =
算法描述如下：设整数),(,0b a EUCLID b a >>
(1）b Y a X ←←;；
（２)如果Y=０,返回X=g ｃd(a,b)，否则继续;
（3)R=XmodY
(4）Y X ←；
（5)R Y ←；
（６）返回（2）
扩展的欧几里得算法描述如下：Extend ｅd ＥＵCLID （a,ｎ)
（1)()()n X X X ,01,,321，←;()()a Y Y Y ,1,0,,321←；
(２）如果03=Y ，返回),gcd(3n a X =,无逆元；否则继续;
（３)如果13=Y ，返回),gcd(3n a Y =;n a Y mod 12-=;
（4)??
????=33Y X Q ； (5）()()332211321,,,,QY X QY X QY X T T T ---←;
(6)()()321321,,,,Y Y Y X X X ←；
（7)()()321321,,,,T T T Y Y Y ←；
（8）返回(2)。
有限域GF(Ｐ):
阶为n p 的有限域一般记为()n
p GF ，GF 代表伽罗瓦域。 给定一个素数p,元素个数为p 的有限域GF （p ）被定义为整数{}1-p 1,0，， 的集合p Z ，其运算为模p 的算术运算。
乘法逆元()1-ω：任意p Z ∈ω，0≠ω，存在p Z z ∈使得p z mod 1≡?ω
求最大公因式：
我们可以通过定义最大公因式来扩展域上的多项式和整数运算之间的类比。如果：1.c(ｘ)能同时整除a(ｘ）和b(ｘ)。
2．a （x)和b(x)的任何因式都是c(x ）的因式。
就称多项式c(x)为a （x ）和b （x)的最大公因式。
此定义等价定义与:gcd[ａ(x ），b （x ）］是能同时整数a(x)和b(x)的多项式中次数最高的一个。
多项式模运算:
如果定义了合适的运算，那么每一个这样的集合S 都是一个有限域。定义由 如下几条组成：
1.该运算遵循基本代数规则中的普通多项式运算规则
2.系数运算以P 为模，即遵循有限域p Z 上的运算规则
3.如果乘法运算结果是次数大于n-1的多项式,那么必须将其除以某个次数为n 的既约多项式m(x ）并取余式。对于多项式ｆ（x),这个余式可表示为r(x)=ｆ(x) ｍod m(ｘ)
素数
任意整数1>a 都可以惟一地因子分解为:t t
p p p a ααα 2121=，其中t p p p ,,21均为素数,t p p p <<< 21且指数皆为正整数。
费马定理:p 是素数，a 是与p 互素的正整数，则
p a p mod 11≡-或者p a a p mod ≡
显然有Z k p a a p k k ∈≡-,mod )1mod(
欧拉函数:欧拉函数()n φ是一个定义在正整数集上的函数，()n φ的值等于小于ｎ 且与n 互素的正整数的个数。
欧拉函数有性质如下：
1.如果n 是素数，则()1-n =n φ
2.如果q p n ?=，p 和q 是素数,且p 不等于q 则
()()()()()()11--=?=?=q p q p q p n φφφφ
欧拉定理:对任何互素的两个整数a 和n,有()n a n mod 1≡φ。
欧拉定理有如下推论。
1.n 为素数时,有()n a a n n mod 11≡≡-φ,即费马定理。
2.由欧拉定理,有()n a a n mod 1≡+φ进一步有()n a a n k mod 1≡+φ,Z k ∈
3.若ｎ=ｐｑ，p 和q 是素数,p 不等于q ，则有()n a a a q p n mod 1)1)(1(1≡≡+--+φ。
4.若ｎ＝pq,ｐ和q 是素数,p 不等于q,而q p n a 或=),gcd(,仍有()n a a n mod 1≡+φ
中国剩余定理：设正整数k m m m ,,,21 两两互素，记∏==k
i i m M 1,则同余
?????????≡≡≡≡k
k m b x m b x m b x m b x mod mod mod mod 332211
在模M 同余的意义下，有唯一解∑==k
i i i i M y M b x 1mod ,其中:
k i m M y r i m M M i i i i
i ≤≤=≤≤=-1,mod 1,1；
如果()1,=n a ,则至少有一个整数m(即()n m φ=）满足n a m mod 1≡。
满足上式的最小正整数ｍ为模n 下a 的阶（又称次数）。
本原根：如果ａ的阶等于()n φ，则称ａ为ｎ的本原根(又称素根）
性质:如果ａ是ｎ的本原根,则()n a a a a φ,,,,32 在模n 下互不相同，且均与ｎ互素。
注意:模n 下的本原根并不具备唯一性,且并非所有的整数n 都有本原根,只有以下形式的整数才有本原根：a a p p 2,4,2，,其中a 为整数,ｐ为奇素数。
离散对数:
设p 为以素数,a 是p 的本原根,则在模p 下132,,,,-p a a a a 产生1到ｐ-1之间的所有值，且每一个值仅出现一次。因此:
对于任意{}1,,1-∈p b ，都存在唯一的正整数()11-≤≤p k k ,使得p a b k mod ≡
这样,模p 下ａ的方幂运算为:p a y x mod ≡，()11-≤≤p x
称x 为模p 下以ａ为底y 的对数,记为:()y ind x p a ,=,()11-≤≤p y
以上运算定义在模ｐ有限域上的，所以称为离散对数运算。
性质：
1.()11,-=p ind p a
2.()1,=a ind p a
3.()()()[]()p y ind x ind xy ind p a p a p a φmod ,,,+=
4.()
()[]()p x ind y x ind p a y p a φmod ,,?=
5.若n a a y x mod ≡,其中a ，n 互素，a 是n 的本原根，则有：()n y x φmod ≡。
平方剩余:
设ｐ是一素数,ａ小于ｐ,如果方程p a x mod 2≡有解,称ａ是模p 的平方剩余（也称二次剩余）,否则称为非平方剩余。
设p 是素数，ａ是一整数，a 是p 的平方剩余的充要条件是:()p a p mod 121≡- ａ是p 的非平方剩余的充要条件是：()p a p mod 1-21≡-